CliquePercolationMethod-Python

Clique Percolation Method (CPM) is an algorithm for finding overlapping communities within networks, introduced by Palla et al. (2005, see references). This implementation in Python, firstly detects communities of size k, then creates a clique graph. Each community will be represented by each connected component in the clique graph.

Algorithm

The algorithm performs the following steps:

1- first find all cliques of size k in the graph
2- then create graph where nodes are cliques of size k
3- add edges if two nodes (cliques) share k-1 common nodes
4- each connected component is a community

Main Implementations

• clique_percolation_method(graph, k = 3): Implementation of the Clique Percolation Method

It requires igraph library:

pip install python-igraph

Run

In this version, the main script contains some test functionalities that help on how to get going with this algorithm.

import CliquePercolationMethod as cpm

cpm.text()
# or 
cpm.test_karate()

Parameters

• graph : igraph object The igraph object containing the graph.
• k : int, optional Size of the clique. The default is 3.
• workers : int, optional Number of threads to allocate for running this algorithm. The default is 1.
• attribute : str, optional The attribute of the vertices to use for displaying nodes within the communities. For displaying purposes, if vertices have names, the latter can be quite handy to figure out which node belongs to a certain community. If no attribute is given, the algorithm will display their id. The default is None.
• verbose : bool, optional If set to True it shows status updates. The default is False.

Reference

Palla, Gergely, Imre Derényi, Illés Farkas, and Tamás Vicsek. "Uncovering the overlapping community structure of complex networks in nature and society." Nature 435, no. 7043 (2005): 814-818.