significance_communities(g_original: object, initial_membership: list = None, node_sizes: list = None) → cdlib.classes.node_clustering.NodeClustering

Significance_communities is a model where the quality function to optimize is:

\[Q = \sum_c \binom{n_c}{2} D(p_c \parallel p)\]

where \(n_c\) is the number of nodes in community \(c\), \(p_c = \frac{m_c}{\binom{n_c}{2}}\), is the density of community \(c\), \(p = \frac{m}{\binom{n}{2}}\) is the overall density of the graph, and finally \(D(x \parallel y) = x \ln \frac{x}{y} + (1 - x) \ln \frac{1 - x}{1 - y}\) is the binary Kullback-Leibler divergence. For directed graphs simply multiply the binomials by 2. The expected Significance in Erdos-Renyi graphs behaves roughly as \(\frac{1}{2} n \ln n\) for both directed and undirected graphs in this formulation.


This method is not suitable for weighted graphs.

Supported Graph Types

Undirected Directed Weighted
Yes No No
  • g_original – a networkx/igraph object
  • initial_membership – list of int Initial membership for the partition. If None then defaults to a singleton partition. Deafault None
  • node_sizes – list of int, or vertex attribute Sizes of nodes are necessary to know the size of communities in aggregate graphs. Usually this is set to 1 for all nodes, but in specific cases this could be changed. Deafault None

NodeClustering object

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.significance_communities(G)

Traag, V. A., Krings, G., & Van Dooren, P. (2013). Significant scales in community structure. Scientific Reports, 3, 2930. 10.1038/srep02930 <>


Reference implementation: