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 KullbackLeibler divergence. For directed graphs simply multiply the binomials by 2. The expected Significance in ErdosRenyi 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
Returns: NodeClustering object
Example: >>> from cdlib import algorithms >>> import networkx as nx >>> G = nx.karate_club_graph() >>> coms = algorithms.significance_communities(G)
References: 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