title: Clique percolation in random networks.
abstract: 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 Erdos-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(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.
authors.affiliation: Department of Biological Physics, Eötvös University, Pázmány P. stny. 1A, H-1117 Budapest, Hungary.
authors.forename: Imre
authors.initials: I
authors.lastname: Derényi
authors.forename: Gergely
authors.initials: G
authors.lastname: Palla
authors.forename: Tamás
authors.initials: T
authors.lastname: Vicsek
mesh_terms: D019058:Community Networks; D003626:Data Display; D007255:Information Services; D008962:Models, Theoretical