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