modularity#
- modularity(G, communities, weight='weight', resolution=1)[source]#
Returns the modularity of the given partition of the graph.
Modularity is defined in [1] as
where
is the number of edges (or sum of all edge weights as in [5]), is the adjacency matrix ofG
, is the (weighted) degree of , is the resolution parameter, and is 1 if and are in the same community else 0.According to [2] (and verified by some algebra) this can be reduced to
where the sum iterates over all communities
, is the number of edges, is the number of intra-community links for community , is the sum of degrees of the nodes in community , and 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
with .- 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 partition.
- Raises:
- NotAPartition
If
communities
is not a partition of the nodes ofG
.
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
[5]Blondel, V.D. et al. “Fast unfolding of communities in large networks” J. Stat. Mech 10008, 1-12 (2008). https://doi.org/10.1088/1742-5468/2008/10/P10008
Examples
>>> G = nx.barbell_graph(3, 0) >>> nx.community.modularity(G, [{0, 1, 2}, {3, 4, 5}]) 0.35714285714285715 >>> nx.community.modularity(G, nx.community.label_propagation_communities(G)) 0.35714285714285715