The clique percolation method[1] is a popular approach for analyzing the overlapping community structure of networks.
The term network community (also called a module, cluster or cohesive group) has no widely accepted unique definition and it is usually defined as a group of nodes that are more densely connected to each other than to other nodes in the network.
There are numerous alternative methods for detecting communities in networks,[2] for example, the Girvan–Newman algorithm, hierarchical clustering and modularity maximization.
The clique percolation method builds up the communities from k-cliques, which correspond to complete (fully connected) sub-graphs of k nodes.
Such communities can be best interpreted with the help of a k-clique template (an object isomorphic to a complete graph of k nodes).
[5] Clique percolation methods may be generalized by recording different amounts of overlap between the various k-cliques.
The Erdős–Rényi model shows a series of interesting transitions when the probability p of two nodes being connected is increased.
A similar phenomenon can be observed in many real networks as well: if k is large, only the most densely linked parts are accepted as communities, thus, they usually remain small and dispersed.
The clique percolation method was first implemented and popularized by CFinder [1] (freeware for non-commercial use) software for detecting and visualizing overlapping communities in networks.
[19] A parallel version of the clique percolation method was designed and developed by S. Mainardi et al..[20] By exploiting today's multi-core/multi-processor computing architectures, the method enables the extraction of k-clique communities from very large networks such as the Internet.
[21] The authors released the source code of the method under the GPL and made it freely available for the community.