Clique-Percolation Algorithm's "corner cases" 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.
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:


Extended Clique percolation method to detect overlapping community structure : http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6968420&amp;pageNumber%3D33268%26rowsPerPage%3D100


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.