cdlib.algorithms.rb_pots¶
-
rb_pots
(g_original: object, initial_membership: list = None, weights: list = None, resolution_parameter: float = 1) → cdlib.classes.node_clustering.NodeClustering¶ Rb_pots is a model where the quality function to optimize is:
\[Q = \sum_{ij} \left(A_{ij} - \gamma \frac{k_i k_j}{2m} \right)\delta(\sigma_i, \sigma_j)\]where \(A\) is the adjacency matrix, \(k_i\) is the (weighted) degree of node \(i\), \(m\) is the total number of edges (or total edge weight), \(\sigma_i\) denotes the community of node \(i\) and \(\delta(\sigma_i, \sigma_j) = 1\) if \(\sigma_i = \sigma_j\) and 0 otherwise. For directed graphs a slightly different formulation is used, as proposed by Leicht and Newman :
\[Q = \sum_{ij} \left(A_{ij} - \gamma \frac{k_i^\mathrm{out} k_j^\mathrm{in}}{m} \right)\delta(\sigma_i, \sigma_j),\]where \(k_i^\mathrm{out}\) and \(k_i^\mathrm{in}\) refers to respectively the outdegree and indegree of node \(i\) , and \(A_{ij}\) refers to an edge from \(i\) to \(j\). Note that this is the same of Leiden algorithm when setting \(\gamma=1\) and normalising by \(2m\), or \(m\) for directed graphs.
Supported Graph Types
Undirected Directed Weighted Yes Yes Yes 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 - weights – list of double, or edge attribute Weights of edges. Can be either an iterable or an edge attribute. Deafault None
- resolution_parameter – double >0 A parameter value controlling the coarseness of the clustering. Higher resolutions lead to more communities, while lower resolutions lead to fewer communities. Default 1
Returns: NodeClustering object
Example: >>> from cdlib import algorithms >>> import networkx as nx >>> G = nx.karate_club_graph() >>> coms = algorithms.rb_pots(G)
References: Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74(1), 016110. 10.1103/PhysRevE.74.016110
Leicht, E. A., & Newman, M. E. J. (2008). Community Structure in Directed Networks. Physical Review Letters, 100(11), 118703. 10.1103/PhysRevLett.100.118703