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.
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