Introduction to Clique Percolation Method (CPM)

Clique Percolation Method is a community detection technique that identifies overlapping communities by connecting adjacent k-clique that share K - 1 common nodes.

Input : The social graph G, representing a network and a clique size K

Algorithm

• All k-clique present in G are extracted
• A new graph, the clique graph G' formed where each node representedan identified clique and two vertices in G' are connected by an edge if they have k-1 common vertices.
• Connected components in G' are identified
• Each connected component in G' represents a community
• Set C be the set of community formed for G

Output : Set of discovered communities C

1. Example : For k = 3, two triangle must share 2 common nodes

Here A,C,D and A,C,B are two triangle(Clique) sharing A,C so K-1 = 3 - 1 = 2, so two triangle must share 2 common node so this will form a community C = (A, B, C, D)

2. Example : Using CPM find communities, overlapping node and outlier by constructing 3-clique graph