cdlib.evaluation.modularity_density

modularity_density(graph: <Mock id='140619399400784'>, communities: object, lmbd: float = 0.5, **kwargs) → object

The modularity density is one of several propositions that envisioned to palliate the resolution limit issue of modularity based measures. The idea of this metric is to include the information about community size into the expected density of community to avoid the negligence of small and dense communities. For each community \(C\) in partition \(S\), it uses the average modularity degree calculated by \(d(C) = d^{int(C)} − d^{ext(C)}\) where \(d^{int(C)}\) and \(d^{ext(C)}\) are the average internal and external degrees of \(C\) respectively to evaluate the fitness of \(C\) in its network. Finally, the modularity density can be calculated as follows:

\[Q(S) = \sum_{C \in S} \frac{1}{n_C} ( \sum_{i \in C} 2 * \lambda * k^{int}_{iC} - \sum_{i \in C} 2 * (1 - \lambda) * k^{out}_{iC})\]

where \(n_C\) is the number of nodes in C, \(k^{int}_{iC}\) is the degree of node i within \(C\), \(k^{out}_{iC}\) is the deree of node i outside \(C\) and \(\lambda\) is a paramter that allows for tuning the measure resolution (its default value, 0.5, computes the standard modularity density score).

Parameters:
  • graph – a networkx/igraph object
  • communities – NodeClustering object
  • lmbd – resolution parameter, float in [0,1]. Default 0.5.
Returns:

FitnessResult object

Example:

>>> from cdlib.algorithms import louvain
>>> from cdlib import evaluation
>>> g = nx.karate_club_graph()
>>> communities = louvain(g)
>>> mod = evaluation.modularity_density(g,communities)
References:
  1. Zhang, S., Ning, XM., Ding, C. et al. Determining modular organization of protein interaction networks by maximizing modularity density. <https://doi.org/10.1186/1752-0509-4-S2-S10>`_ BMC Syst Biol 4, S10 (2010).