Source code for easygraph.functions.community.modularity
from itertools import product
from easygraph.utils import *
__all__ = ["modularity"]
[docs]@not_implemented_for("multigraph")
def modularity(G, communities, weight="weight"):
r"""
Returns the modularity of the given partition of the graph.
Modularity is defined in [1]_ as
.. math::
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`,
.. math::
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 : float
The modularity of the partition.
References
----------
.. [1] M. E. J. Newman *Networks: An Introduction*, page 224.
Oxford University Press, 2011.
"""
# TODO: multigraph not included.
if not isinstance(communities, list):
communities = list(communities)
directed = G.is_directed()
m = G.size(weight=weight)
if directed:
out_degree = dict(G.out_degree(weight=weight))
in_degree = dict(G.in_degree(weight=weight))
norm = 1 / m
else:
out_degree = dict(G.degree(weight=weight))
in_degree = out_degree
norm = 1 / (2 * m)
def val(u, v):
try:
w = G[u][v].get(weight, 1)
except KeyError:
w = 0
# Double count self-loops if the graph is undirected.
if u == v and not directed:
w *= 2
return w - in_degree[u] * out_degree[v] * norm
Q = sum(val(u, v) for c in communities for u, v in product(c, repeat=2))
return Q * norm