All the algorithms we have studied so far have one point in common: each node is assigned to one and only one community. But this is not always representative of reality: a friend can also be a colleague, a colleague can also be a family member. Being able to detect the nodes belonging to several communities also brings up interesting information about the graph structure and community borders, as suggested by the following illustration.
One of the most famous algorithms for overlapping community detection is the Clique Percolation Method (CPM). A clique in graph theory is a subset of nodes where each node is connected to all other nodes. A k-clique is a clique containing k nodes. The simplest example of a clique is the 3-clique, which is a triangle made of three fully connected nodes. The CPM algorithm defines a community based on an adjacent k-clique, where two k-cliques are considered adjacent if they share k-1 nodes, which makes it possible for the...
