Explosive Percolation in Scale-Free Networks

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 $\lambda$ 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 $\lambda >{\lambda }_c\sim 2.2$. More interestingly, the transition is continuous when $\lambda \le 3$ but becomes discontinuous when $\lambda >3$. This may have important consequences for both the structure of networks and for the dynamics of processes taking place on them.

Figure 1

Scheme of the construction process of a network via an Achlioptas process with product rule (PR). Two pairs of stubs are taken at random (each pair is indicated by the dotted lines), and the products of the sizes of each pair of clusters merged by joining the stubs are computed. The stubs that are finally joined are those minimizing the product of the corresponding cluster sizes. In the case illustrated, one would join the nodes $i_1$ and $j_1$, which yield a smaller product cluster size than $i_2$ and $j_2$ ($2\times 5=10$ versus $3\times 4=12$).

Figure 2

Explosive percolation transition in scale-free networks. For $\lambda =2.5$, the transition is continuous. In (a) and (b), we show the percolation strengths corresponding to different system sizes and their rescaling $S^{(1)}{N}^{\beta /\nu }$, respectively. The validity of Eq. (1) can be proved by plotting $S^{(1)}{N}^{\beta /\nu }$ versus $(p-p_c)N^{1/\nu }$ (c). The peak of the susceptibility $\chi$ moves gradually towards $p_c$ as the system size increases (d). Instead, for $\lambda =3.5$ the transition is discontinuous: percolation strengths corresponding to different system sizes do not have a scaling form (e). The location of the peaks of the susceptibility is essentially the same for any system size (f). The network sizes go from 256 000 to 16 384 000 via successive doublings.

Figure 3

Percolation threshold $p_c(N)$ as a function of the degree exponent $\lambda$ for various network sizes $N$. The black line represents the infinite size limit extrapolation of the critical threshold. This extrapolation is made by using Eq. (3) for $\lambda \le 3$, while for $\lambda \ge 3$ one uses the value of the plateau to which the pseudocritical points converge.

Figure 4

Critical exponents’ ratios $\beta /\nu$ and $\gamma /\nu$ as a function of the degree exponent $\lambda$. The insets show the scaling at $p_c$ of the quantities $S^{(1)}\sim N^{-\beta /\nu }$ [inset (a)] and $\chi \sim N^{\gamma /\nu }$ [inset (b)] for $\lambda =2.5$, 3.0, and 3.5 (from bottom to top).