modularity

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

Returns the modularity of the given partition of the graph.

Modularity is defined in [1] as

$$Q=\frac{1}{2m}\sum _{ij}(A_{ij}-\gamma \frac{k_i{k}_j}{2m})\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$, $\gamma$ is the resolution parameter, and $\delta (c_i,c_j)$ is 1 if $i$ and $j$ are in the same community else 0.

According to [2] (and verified by some algebra) this can be reduced to

$$Q=\sum _{c=1}^n[\frac{L_c}{m}-\gamma {\left(\frac{k_c}{2m}\right)}^2]$$

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$, and $\gamma$ is the resolution parameter.

The resolution parameter sets an arbitrary tradeoff between intra-group edges and inter-group edges. More complex grouping patterns can be discovered by analyzing the same network with multiple values of gamma and then combining the results [3]. That said, it is very common to simply use gamma=1. More on the choice of gamma is in [4].

The second formula is the one actually used in calculation of the modularity. For directed graphs the second formula replaces $k_c$ with $k_c^{in}{k}_c^{out}$.

Parameters

GNetworkX Graph

communitieslist or iterable of set of nodes

These node sets must represent a partition of G’s nodes.

weightstring 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.

resolutionfloat (default=1)

If resolution is less than 1, modularity favors larger communities. Greater than 1 favors smaller communities.

Returns

Qfloat

The modularity of the paritition.

Raises

NotAPartition

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

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.” Phys. Rev. E 70.6 (2004). <https://arxiv.org/abs/cond-mat/0408187>

3

Reichardt and Bornholdt “Statistical Mechanics of Community Detection” Phys. Rev. E 74, 016110, 2006. https://doi.org/10.1103/PhysRevE.74.016110

4

M. E. J. Newman, “Equivalence between modularity optimization and maximum likelihood methods for community detection” Phys. Rev. E 94, 052315, 2016. https://doi.org/10.1103/PhysRevE.94.052315

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