networkx.algorithms.community.quality.modularity

modularity(G, communities, weight='weight')

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

float

Raises

NotAPartition – If communities is not a partition of the nodes of G.

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>