Proofs: Clique percolation method

The clique percolation method outputs the k-clique communities full

This proof shows: correctness, termination.

Let $G$ be a simple undirected graph and $k \ge 2$. Let $C$ be the list of line L1, which holds each $k$-clique of $G$ exactly once. A face of a $k$-clique $A$ is a set $A \setminus \{x\}$ with $x \in A$, so $A$ has exactly $k$ faces, each of size $k - 1$. Let $\sim$ be the equivalence relation on the cliques generated by adjacency, where $A$ and $B$ are adjacent when $|A \cap B| = k - 1$.

Termination. The list $C$ is finite, each clique has $k$ faces, and each UNION and each lookup in $H$ ends. Line L8 runs over the finitely many classes. So the algorithm stops.

Lemma 1 (faces and adjacency). Two distinct $k$-cliques $A$ and $B$ are adjacent if and only if they have a common face.

Proof. If $|A \cap B| = k - 1$, let $F = A \cap B$. Then $A = F \cup \{x\}$ for the one $x \in A \setminus B$, so $F = A \setminus \{x\}$ is a face of $A$, and in the same way a face of $B$. Conversely, a common face $F$ has $F \subseteq A \cap B$, so $|A \cap B| \ge k - 1$, and $A \ne B$ with $|A| = |B| = k$ gives $|A \cap B| \le k - 1$. $\square$

Write $c \equiv c'$ when the indices $c$ and $c'$ are in the same set of the union-find at the end.

Lemma 2 (the union-find classes). For all indices $c, c'$, $c \equiv c'$ if and only if $C[c] \sim C[c']$.

Proof. Each union joins equivalent cliques. Line L7 calls UNION$(c, H[F])$ only when $F$ is a face of $C[c]$ and $H[F]$ was stored for a clique with the face $F$ (line L7 stores $H[F] \leftarrow c''$ only for a face $F$ of $C[c'']$). The two indices differ, since a clique has distinct faces and $c$ is handled once, so by Lemma 1 the two cliques are adjacent. The relation $\equiv$ is the smallest equivalence that contains the pairs joined by UNION, and each such pair is in $\sim$, which is an equivalence. So $c \equiv c'$ implies $C[c] \sim C[c']$.

Adjacent cliques are joined. Let $C[c]$ and $C[c']$ be adjacent, with the common face $F$ by Lemma 1. The first index $c_0$ handled at line L4 among those whose clique has the face $F$ stores $H[F] = c_0$, and $H[F]$ never changes after that, since line L7 stores only for a face not in $H$. Every later index with the face $F$ meets $F \in H$ and is joined with $c_0$. So $c \equiv c_0 \equiv c'$. Since $\sim$ is generated by adjacency and $\equiv$ is an equivalence, $C[c] \sim C[c']$ implies $c \equiv c'$. $\square$

Theorem. CPM$(G, k)$ outputs, for each class $\mathcal{Q}$ of $\sim$, the set $\bigcup_{A \in \mathcal{Q}} A$, once, and nothing else.

Proof. By Lemma 2, the map $c \mapsto C[c]$ sends the classes of the union-find onto the classes of $\sim$, one to one, since $C$ lists each clique once. Line L8 visits each class $Q$ of the union-find once, and line L9 outputs $\bigcup_{c \in Q} C[c]$, which is the union of the cliques of the matching class of $\sim$. Every class of $\sim$ is the image of one class $Q$, so every $k$-clique community is output, and each output is one of them. $\blacksquare$