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

## 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 societyNature, 435(7043), 814-818.