easygraph.functions.community.modularity module

easygraph.functions.community.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.\]

Parameters:

• G (easygraph.Graph or easygraph.DiGraph) –

• communities (list or iterable of set of nodes) – These node sets must represent a partition of G’s nodes.

• weight (string, optional (default : 'weight')) – The key for edge weight.

Returns:

Q – The modularity of the partition.

Return type:

float

References

[1]

M. E. J. Newman Networks: An Introduction, page 224. Oxford University Press, 2011.