Clique percolation

Journal article

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 for a giant component to appear 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'$.

Authors: Bollobas, B; Riordan, O

• Publication status: Published
• Journal: Random Structures and Algorithms 35 (2009), 294--322
• Volume: 35
• Issue: 3
• Pages: 294-322
• Publication date: 2008-04-05
• DOI: 10.1002/rsa.20270
• EISSN: 1098-2418
• ISSN: 1042-9832
• Language: English
• Keywords: math.CO; math.PR; 05C80; 60K35