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>