networkx.algorithms.community.quality.modularity¶
-
modularity(G, communities, weight='weight')[source]¶ Returns the modularity of the given partition of the graph.
Modularity is defined in 1 as
\[Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_ik_j}{2m}\right) \delta(c_i,c_j)\]where \(m\) is the number of edges, \(A\) is the adjacency matrix of
G, \(k_i\) is the degree of \(i\) and \(\delta(c_i, c_j)\) is 1 if \(i\) and \(j\) are in the same community and 0 otherwise.According to 2 (and verified by some algebra) this can be reduced to
\[Q = \sum_{c=1}^{n} \left[ \frac{L_c}{m} - \left( \frac{k_c}{2m} \right) ^2 \right]\]where the sum iterates over all communities \(c\), \(m\) is the number of edges, \(L_c\) is the number of intra-community links for community \(c\), \(k_c\) is the sum of degrees of the nodes in community \(c\).
The second formula is the one actually used in calculation of the modularity.
- Parameters
G (NetworkX Graph)
communities (list or iterable of set of nodes) – These node sets must represent a partition of G’s nodes.
weight (string or None, optional (default=”weight”)) – The edge attribute that holds the numerical value used as a weight. If None or an edge does not have that attribute, then that edge has weight 1.
- Returns
Q – The modularity of the paritition.
- Return type
- Raises
NotAPartition – If
communitiesis not a partition of the nodes ofG.
Examples
>>> import networkx.algorithms.community as nx_comm >>> G = nx.barbell_graph(3, 0) >>> nx_comm.modularity(G, [{0, 1, 2}, {3, 4, 5}]) 0.35714285714285715 >>> nx_comm.modularity(G, nx_comm.label_propagation_communities(G)) 0.35714285714285715
References
- 1
M. E. J. Newman Networks: An Introduction, page 224. Oxford University Press, 2011.
- 2
Clauset, Aaron, Mark EJ Newman, and Cristopher Moore. “Finding community structure in very large networks.” Physical review E 70.6 (2004). <https://arxiv.org/abs/cond-mat/0408187>