Clique Percolation in Random Networks

The notion of $k$-clique percolation in random graphs is introduced, where $k$ is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdős-Rényi graph of $N$ vertices we obtain that the percolation transition of $k$-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold $p_{\mathrm{c}}(k)=[(k-1)N{]}^{-1/(k-1)}$. At the transition point the scaling of the giant component with $N$ is highly nontrivial and depends on $k$. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.

Figure 1

Sketches of two ER graphs of $N=20$ vertices and with edge probabilities $p=0.13$ (left one) and $p=0.22$ (right one, generated by adding more random edges to the left one). In both cases all the edges belong to a “giant” connected component, because the edge probabilities are much larger than the threshold ($p_{\mathrm{c}}\equiv 1/N=0.05$) for the classical ER percolation transition. However, in the left one $p$ is below the 3-clique (triangle) percolation threshold, $p_{\mathrm{c}}(3)\approx 0.16$, calculated from Eq. (1); therefore, only two small 3-clique percolation clusters (distinguished by black and dark gray edges) can be observed. In the right graph, on the other hand, $p$ is above this threshold and, as a consequence, most 3-cliques accumulate in a giant 3-clique percolation cluster (black edges). This graph also exhibits an overlap (half black, half dark gray vertex) between two 3-clique percolation clusters (black and dark gray).

Figure 2

Simulation results for the order parameter $\Phi$ averaged over several runs (the statistical error is smaller than the symbol size). (a) The convergence of $\Phi$ as a function of $p/p_{\mathrm{c}}(k)$ to a step function in the $N\to \infty$ limit is illustrated for $k=4$. (b) The width of the steps follows a power law, $\sim N^{-\alpha }$, as the steps collapse onto a single curve if we stretch them out by $N^{\alpha }$ horizontally. The data for $k=4$ and 5 are shifted upward by 0.4 and 0.8, respectively, for clarity.

Figure 3

The order parameter $\Psi$ for the same simulations as in Fig. 2. (a) As illustrated for $k=4$, $\Psi$ as a function of $p/p_{\mathrm{c}}(k)$ converges to a limit function (which is 0 for $p/p_{\mathrm{c}}(k)<1$ and grows continuously to 1 above $p/p_{\mathrm{c}}(k)=1$) in the $N\to \infty$ limit. (b) The order parameter at the threshold, ${\Psi }_{\mathrm{c}}$, scales as a negative power of $N$, in good agreement with expression (6).