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
Example with k=3
The presented graph contains the following cliques:
{1, 2, 3} {1, 3, 4} {4, 5, 6} {5, 6, 7} {5, 6, 8} {5, 7, 8} {6, 7, 8}
Each clique will represent a node in the clique graph and those node are connected each other if they share k-1 (2 in this case) nodes.
As a result, the clique graph presents two connected components containing {1,2,3,4} and {4,5,6,7,8}. The node 4 belongs to both communities. In other words, the graph contains two overlapping communities.
Description
Usage
- clique_percolation_method(graph, k = 3): Implementation of the Clique Percolation Method
Test
import CliquePercolationMethod as cpm
cpm.text()
# or
cpm.test_karate()
Arguments
- graph: the input graph (igraph object)
- k: the size of the clique (usually = 3)
Returns
- communities: a list of communities. Each element of this list is itself a list containing the nodes of such community.
Package Dependencies
This implementation requires igraph which can be installed by running:
pip install python-igraph
Project info
Github repository: https://github.com/angelosalatino/CliquePercolationMethod-Python
Issue tracker: Here
References
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818.
