cdlib.algorithms.cpm

cpm(g_original: object, initial_membership: list = None, weights: list = None, node_sizes: list = None, resolution_parameter: float = 1) → cdlib.classes.node_clustering.NodeClustering

CPM is a model where the quality function to optimize is:

\[Q = \sum_{ij} \left(A_{ij} - \gamma \right)\delta(\sigma_i, \sigma_j)\]

where \(A\) is the adjacency matrix, \(\sigma_i\) denotes the community of node \(i\), \(\delta(\sigma_i, \sigma_j) = 1\) if \(\sigma_i = \sigma_j\) and 0 otherwise, and, finally \(\gamma\) is a resolution parameter.

The internal density of communities

\[p_c = \frac{m_c}{\binom{n_c}{2}} \geq \gamma\]

is higher than \(\gamma\), while the external density

\(p_{cd} = \frac{m_{cd}}{n_c n_d} \leq \gamma\) is lower than \(\gamma\). In other words, choosing a particular \(\gamma\) corresponds to choosing to find communities of a particular density, and as such defines communities. Finally, the definition of a community is in a sense independent of the actual graph, which is not the case for any of the other methods.

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
  • weights – list of double, or edge attribute Weights of edges. Can be either an iterable or an edge attribute. 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
  • 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. Deafault 1
Returns:

NodeClustering object
Example: 
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.cpm(G)
References:

Traag, V. A., Van Dooren, P., & Nesterov, Y. (2011). Narrow scope for resolution-limit-free community detection. Physical Review E, 84(1), 016114. 10.1103/PhysRevE.84.016114

Note

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