Clique percolation

Abstract

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^{\prime }$ 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^{\prime }$. 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^{\prime }$.

33 pages, 1 figure

References in corpus (5)

• Clique percolation in random networks
• The phase transition in inhomogeneous random graphs
• Directed network modules
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• The critical point of k-clique percolation in the Erdos-Renyi graph

Cited by in corpus (5)

• Percolation on complex networks: Theory and application
• Random geometric complexes
• Clique percolation in random graphs
• Asymptotic normality of the size of the giant component in a random hypergraph
• Clustering and percolation of point processes