Clique Percolation Method in 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.


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.

Clique Graph
Clique Graph

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.



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


import CliquePercolationMethod as cpm

# or 


  • graph: the input graph (igraph object)
  • k: the size of the clique (usually = 3)


  • 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:
Issue tracker: Here


Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and societyNature, 435(7043), 814-818.