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

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