Abstract
The notion of -clique percolation in random graphs is introduced, where is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdős-Rényi graph of vertices we obtain that the percolation transition of -cliques takes place when the probability of two vertices being connected by an edge reaches the threshold . At the transition point the scaling of the giant component with is highly nontrivial and depends on . We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.
- Received 10 November 2004
DOI:https://doi.org/10.1103/PhysRevLett.94.160202
©2005 American Physical Society