I'm programming an implementation of the Clique-Percolation algorithm, but I have many doubts about some corner cases.

Imagine we want to find the communities of a graph using $k=4$. We are lucky and every node in the graph belongs at least to one k-clique (with $k \geq 4$). So it's trivial to apply the algorithm by hand (slow, but trivial).

Now imagine we add three more nodes to the graph, creating a 3-clique, and connecting this clique to the previous existing nodes with only 1 edge.

It's here where I have problems to understand what's expected of the Clique Percolation algorithm.

I have to add a new community for each new node? Only a new non-overlapping community matching the 3-clique? Nothing (not considering the new nodes in any community)?

Example initial graph: $$ A \leftrightarrow B \\ A \leftrightarrow C \\ A \leftrightarrow D \\ B \leftrightarrow C \\ B \leftrightarrow D \\ C \leftrightarrow D \\ $$

Modified graph: $$ A \leftrightarrow B \\ A \leftrightarrow C \\ A \leftrightarrow D \\ B \leftrightarrow C \\ B \leftrightarrow D \\ C \leftrightarrow D \\ D \leftrightarrow E \\ E \leftrightarrow F \\ E \leftrightarrow G \\ F \leftrightarrow G $$

thanks for your time.


1 Answer 1


Finally, I've found that the answer is that exists the possibility of leaving out many nodes out of any resulting community. There isn't any specified way in the original CPM algorithm to deal with them.

For anyone interested on a possible way to handle the left out nodes, there is an interesting article explaining an extension of CPM to do that:

It seems that the modularity score obtained with this extension is usually better than the produced by the original CPM, but it comes with a price: it's slower.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.