cdlib.evaluation.newman_girvan_modularity

newman_girvan_modularity(graph: <Mock id='139918925490960'>, communities: object, **kwargs) → object

Difference the fraction of intra community edges of a partition with the expected number of such edges if distributed according to a null model.

In the standard version of modularity, the null model preserves the expected degree sequence of the graph under consideration. In other words, the modularity compares the real network structure with a corresponding one where nodes are connected without any preference about their neighbors.

\[Q(S) = \frac{1}{m}\sum_{c \in S}(m_S - \frac{(2 m_S + l_S)^2}{4m})\]

where \(m\) is the number of graph edges, \(m_S\) is the number of community edges, \(l_S\) is the number of edges from nodes in S to nodes outside S.

Parameters:
  • graph – a networkx/igraph object
  • communities – NodeClustering object
Returns:

FitnessResult object

Example:

>>> from cdlib.algorithms import louvain
>>> from cdlib import evaluation
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = evaluation.newman_girvan_modularity(g,communities)
References:
  1. Newman, M.E.J. & Girvan, M. Finding and evaluating community structure in networks. Physical Review E 69, 26113(2004).