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 NodeClustering object
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.rb_pots(G)


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