Clique percolation

Details Clique percolation Clique percolation

2008-04-05

arxiv.org/abs/0804.0867v2

Random Structures and Algorithms 35 (2009), 294--322

Mathematics

Probability

33 pages, 1 figure

Scientific paper

10.1002/rsa.20270

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'$.

Affiliated with

Also associated with

No associations

Rating

Clique percolation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Clique percolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clique percolation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-270532