Clique percolation in random graphs

Ming Li, Youjin Deng, Bing-Hong Wang

Published 2015-08-08Version 1

As a generation of the classical percolation, clique percolation focuses on the connection of cliques in a graph, where the connection of two $k$-cliques means they share at leat $l<k$ vertices. In this paper, we develop a theoretical approach to study clique percolation in Erd\H{o}s-R\'enyi graphs, which can give the exact solutions of the order parameter and the critical point. We find that the fraction of cliques in the giant clique cluster always takes a continuous phase transition as the classical percolation. However, the fraction of vertices in the giant clique cluster demonstrates an unnormal phase transitions for $k>3$ and $l>1$, i.e., the fraction of vertices in the giant clique cluster always takes value $1$ above the critical point, however, a size-independent constant at the critical point. Together with the analysis of the finite size scaling and cluster number distribution, we give a theoretical support and clarification for previous simulation studies of the clique percolation.