Clique percolation
Derenyi, Palla and Vicsek introduced the following dependent percolation model, in the context of finding communities in networks. Starting with a random graph G generated by some rule, form an auxiliary graph G whose vertices are the k cliques of G, in which two vertices are joined if the corresponding cliques share k 1 vertices. They considered in particular the case where G G(n, p) and found heuristically the threshold function p p(n) above which a giant component appears in G. Here we give a rigorous proof of this result, as well as many extensions. The model turns out to be very interesting due to the essential global dependence present in G. 1 Cliques sharing vertices Fix k 2 and 1 l k 1. Given a graph G, let G be the graph whose vertex set is the set of all copies of Kk in G, in which two vertices are adjacent if the corresponding copies of Kk share at least l vertices. Starting from a random graph G G(n, p) our aim is to study percolation in the corresponding graph G p i.e. to find for which values of p there is a 'giant' component in G k,l p containing a positive fraction of the vertices of G p For l k 1, this question was proposed by Derenyi, Palla and Vicsek [10] motivated by the study of 'communities' in real world networks, but independent of the motivation, we consider it to be an extremely natural question in the theory of random graphs. Indeed, it is perhaps the most natural example of dependent percolation arising out of the model G(n, p) As we shall see in a moment, it is not too hard to guess the answer; simple heuristic derivations based on the local analysis of G p were given in [10] and by Palla, Derenyi and Vicsek [17] (For a survey of related work see [16] Note, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, UK University of Memphis, Memphis TN 38152, USA Research supported in part by NSF grants DMS 0505550, CNS 0721983 and CCF0728928, and ARO grant W911NF 06 1 0076 Mathematical Institute, University of Oxford, 24 29 St Giles' Oxford OX1 3LB, UK
Random Struct. Algorithms