# cdlib.algorithms.significance_communities¶

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.

Warning

This method is not suitable for weighted graphs.

Supported Graph Types

Undirected Directed Weighted
Yes No No
Parameters: 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 <http://doi.org/10.1038/srep02930>

Note

Reference implementation: https://github.com/vtraag/leidenalg