"""Modularity matrix of graphs. """ import networkx as nx from networkx.utils import not_implemented_for __all__ = ["modularity_matrix", "directed_modularity_matrix"] @not_implemented_for("directed") @not_implemented_for("multigraph") def modularity_matrix(G, nodelist=None, weight=None): r"""Returns the modularity matrix of G. The modularity matrix is the matrix B = A - , where A is the adjacency matrix and is the average adjacency matrix, assuming that the graph is described by the configuration model. More specifically, the element B_ij of B is defined as .. math:: A_{ij} - {k_i k_j \over 2 m} where k_i is the degree of node i, and where m is the number of edges in the graph. When weight is set to a name of an attribute edge, Aij, k_i, k_j and m are computed using its value. Parameters ---------- G : Graph A NetworkX graph nodelist : list, optional The rows and columns are ordered according to the nodes in nodelist. If nodelist is None, then the ordering is produced by G.nodes(). weight : string or None, optional (default=None) The edge attribute that holds the numerical value used for the edge weight. If None then all edge weights are 1. Returns ------- B : Numpy matrix The modularity matrix of G. Examples -------- >>> k = [3, 2, 2, 1, 0] >>> G = nx.havel_hakimi_graph(k) >>> B = nx.modularity_matrix(G) See Also -------- to_numpy_array modularity_spectrum adjacency_matrix directed_modularity_matrix References ---------- ..  M. E. J. Newman, "Modularity and community structure in networks", Proc. Natl. Acad. Sci. USA, vol. 103, pp. 8577-8582, 2006. """ if nodelist is None: nodelist = list(G) A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr") k = A.sum(axis=1) m = k.sum() * 0.5 # Expected adjacency matrix X = k * k.transpose() / (2 * m) return A - X @not_implemented_for("undirected") @not_implemented_for("multigraph") def directed_modularity_matrix(G, nodelist=None, weight=None): """Returns the directed modularity matrix of G. The modularity matrix is the matrix B = A - , where A is the adjacency matrix and is the expected adjacency matrix, assuming that the graph is described by the configuration model. More specifically, the element B_ij of B is defined as .. math:: B_{ij} = A_{ij} - k_i^{out} k_j^{in} / m where :math:k_i^{in} is the in degree of node i, and :math:k_j^{out} is the out degree of node j, with m the number of edges in the graph. When weight is set to a name of an attribute edge, Aij, k_i, k_j and m are computed using its value. Parameters ---------- G : DiGraph A NetworkX DiGraph nodelist : list, optional The rows and columns are ordered according to the nodes in nodelist. If nodelist is None, then the ordering is produced by G.nodes(). weight : string or None, optional (default=None) The edge attribute that holds the numerical value used for the edge weight. If None then all edge weights are 1. Returns ------- B : Numpy matrix The modularity matrix of G. Examples -------- >>> G = nx.DiGraph() >>> G.add_edges_from( ... ( ... (1, 2), ... (1, 3), ... (3, 1), ... (3, 2), ... (3, 5), ... (4, 5), ... (4, 6), ... (5, 4), ... (5, 6), ... (6, 4), ... ) ... ) >>> B = nx.directed_modularity_matrix(G) Notes ----- NetworkX defines the element A_ij of the adjacency matrix as 1 if there is a link going from node i to node j. Leicht and Newman use the opposite definition. This explains the different expression for B_ij. See Also -------- to_numpy_array modularity_spectrum adjacency_matrix modularity_matrix References ---------- ..  E. A. Leicht, M. E. J. Newman, "Community structure in directed networks", Phys. Rev Lett., vol. 100, no. 11, p. 118703, 2008. """ if nodelist is None: nodelist = list(G) A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, format="csr") k_in = A.sum(axis=0) k_out = A.sum(axis=1) m = k_in.sum() # Expected adjacency matrix X = k_out * k_in / m return A - X