overlapping_modularity#

overlapping_modularity(G, communities, *, weight='weight', resolution=1)[source]#

Returns Shen et al.’s extended modularity for an overlapping cover.

Standard modularity assumes each node belongs to exactly one community. Shen et al. [1] extend modularity to overlapping communities by discounting each node’s contribution by the number of communities it belongs to:

\[EQ = \frac{1}{2m} \sum_{i} \sum_{v \in C_i, w \in C_i} \frac{1}{O_v O_w}\!\left[ A_{vw} - \gamma\,\frac{k_v k_w}{2m}\right]\]

where the outer sum runs over communities \(C_i\) in the cover, \(A_{vw}\) is the (weighted) adjacency, \(k_v\) is the (weighted) degree of \(v\), \(O_v\) is the number of communities to which \(v\) belongs, \(m\) is the total (weighted) edge count, and \(\gamma\) is the resolution parameter.

The factor \(1 / (O_v O_w)\) discounts contributions from nodes that belong to many communities: a node in 3 communities contributes 1/3 of its modularity share to each.

The resolution parameter \(\gamma\) is not part of the original Shen definition; it is added for consistency with modularity(). Setting \(\gamma = 1\) recovers Shen’s EQ exactly.

Implementation uses the equivalent community-sum form

\[EQ = \sum_{i}\!\left[\frac{\tilde{L}_{C_i}}{m} - \gamma\!\left(\frac{\tilde{k}_{C_i}}{2m}\right)^{\!2}\right]\]

where \(\tilde{L}_{C_i} = \sum_{(v,w) \in L_{C_i}} 1/(O_v O_w)\) is the overlap-discounted intra-community edge count and \(\tilde{k}_{C_i} = \sum_{v \in C_i} k_v / O_v\) is the overlap-discounted degree sum. When the cover is actually a partition (\(O_v = 1\) for all \(v\)), \(EQ\) reduces to the standard modularity \(Q\).

Parameters:

GNetworkX Graph: An undirected graph.
communitiesiterable of sets of nodes: A cover of G’s nodes: every node must appear in at least one set, but sets may overlap. Accepts the output of any NetworkX overlapping community-detection algorithm such as k_clique_communities().
weightstring or None, optional (default=”weight”): Edge attribute holding the numerical edge weight. If None, or if an edge does not have the attribute, that edge has weight 1.
resolutionfloat, optional (default=1): Resolution parameter \(\gamma\). As in standard modularity, values smaller than 1 favor larger communities and values greater than 1 favor smaller communities. The degree of overlap in the cover is independent of \(\gamma\), since \(\gamma\) rescales only the null-model term.

Returns:

EQfloat: The extended modularity of the cover.

Raises:

NetworkXError: If communities is not a valid cover of the nodes of G (some node in G does not belong to any community).
NetworkXNotImplemented: If G is directed. Shen’s formulation is for undirected graphs.

See also

modularity
is_cover

References

[1]

Shen, H., Cheng, X., Cai, K., & Hu, M. B. (2009). “Detect overlapping and hierarchical community structure in networks.” Physica A, 388(8), 1706-1712. https://doi.org/10.1016/j.physa.2008.12.021

[2]

Lancichinetti, A., Fortunato, S., & Kertesz, J. (2009). “Detecting the overlapping and hierarchical community structure in complex networks.” New J. Phys. 11, 033015. (Cover definition.)

Examples

On a partition, EQ equals standard modularity (up to floating-point summation order):

>>> G = nx.barbell_graph(3, 0)
>>> partition = [{0, 1, 2}, {3, 4, 5}]
>>> Q = nx.community.modularity(G, partition)
>>> EQ = nx.community.overlapping_modularity(G, partition)
>>> abs(Q - EQ) < 1e-12
True

Evaluate an overlapping cover produced by k_clique_communities. Two K_5 cliques sharing nodes 3 and 4 yield a 2-community cover:

>>> G = nx.complete_graph(5)
>>> G.add_edges_from(nx.complete_graph(range(3, 8)).edges())
>>> cover = list(nx.community.k_clique_communities(G, 4))
>>> round(nx.community.overlapping_modularity(G, cover), 3)
0.158