<p>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.</p>

<p>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:</p>

<ul>
<li><strong>Extended Clique percolation method to detect overlapping community structure</strong> : <a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6968420&amp;pageNumber%3D33268%26rowsPerPage%3D100" rel="nofollow">http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6968420&amp;pageNumber%3D33268%26rowsPerPage%3D100</a></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2015-05-12T08:15:36.623Z
2015-05-12T08:15:36.623Z
castarco
<p>I'm programming an implementation of the Clique-Percolation algorithm, but I have many doubts about some corner cases.</p>

<p>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).</p>

<p>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.</p>

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

<p>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)?</p>

<p>Example initial graph:
$$
A \leftrightarrow B \\
A \leftrightarrow C \\
A \leftrightarrow D \\
B \leftrightarrow C \\
B \leftrightarrow D \\
C \leftrightarrow D \\
$$</p>

<p>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 
$$</p>

<p>thanks for your time.</p>

<graph-algorithms><clique><percolation>
Clique-Percolation Algorithm's "corner cases"
castarco
# Clique-Percolation Algorithm's "corner cases"

(Asked by: username_0 on 2015-05-08)

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.

**Tags:** graph-algorithms, clique, percolation


---

## 1 answers

### Answer by username_0 on 2015-05-12. Score: 1 | Accepted answer

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&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.


---

