Explosive Percolation in Scale-Free Networks
Physical Review Letters, 103 (16):
168701+ (October 2009)DOI: 10.1103/physrevlett.103.168701
Abstract
We study scale-free networks constructed via a cooperative Achlioptas growth process. Links between nodes are introduced in order to produce a scale-free graph with given exponent λ for the degree distribution, but the choice of each new link depends on the mass of the clusters that this link will merge. Networks constructed via this biased procedure show a percolation transition which strongly differs from the one observed in standard percolation, where links are introduced just randomly. The different growth process leads to a phase transition with a nonvanishing percolation threshold already for λ>λc∼2.2. More interestingly, the transition is continuous when λ≤3 but becomes discontinuous when λ>3. This may have important consequences for both the structure of networks and for the dynamics of processes taking place on them.