Clique percolation in random graphs

Abstract

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 that they share at least $l<k$ vertices. In this paper, we develop a theoretical approach to study clique percolation in Erdős-Rényi graphs, which gives not only the exact solutions of the critical point, but also the corresponding order parameter. Based on this, we prove theoretically that the fraction $\psi$ of cliques in the giant clique cluster always makes a continuous phase transition as the classical percolation. However, the fraction $\varphi$ of vertices in the giant clique cluster for $l>1$ makes a step-function-like discontinuous phase transition in the thermodynamic limit and a continuous phase transition for $l=1$. More interesting, our analysis shows that at the critical point, the order parameter ${\varphi }_c$ for $l>1$ is neither $0$ nor $1$, but a constant depending on $k$ and $l$. All these theoretical findings are in agreement with the simulation results, which give theoretical support and clarification for previous simulation studies of clique percolation.

6 pages, 5 figures

References in corpus (13)

• Uncovering the overlapping community structure of complex networks in nature and society
• Quantifying social group evolution
• Clique percolation in random networks
• Recent advances in percolation theory and its applications
• Weighted network modules
• Random graphs containing arbitrary distributions of subgraphs
• Recent advances and open challenges in percolation
• Directed network modules
• Bond percolation on a class of clustered random networks
• Spectral and network methods in the analysis of correlation matrices of stock returns
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Cascades on clique-based graphs
• Triangle percolation in mean field random graphs -- with PDE

Cited by in corpus (4)

• Percolation on complex networks: Theory and application
• Percolation on networks with weak and heterogeneous dependency
• Network Properties for Robust Multilayer Infrastructure Systems: A Percolation Theory Review
• Emergence of biconnected clusters in explosive percolation