Percolation Transitions in Scale-Free Networks under the Achlioptas Process

It has been recently shown that the percolation transition is discontinuous in Erdős-Rényi networks and square lattices in two dimensions under the Achlioptas process (AP). Here, we show that when the structure is highly heterogeneous as in scale-free networks, a discontinuous transition does not always occur: a continuous transition is also possible depending on the degree distribution of the scale-free network. This originates from the competition between the AP that discourages the formation of a giant component and the existence of hubs that encourages it. We also estimate the value of the characteristic degree exponent that separates the two transition types.

Figure 1

Phase diagram of the percolation transition in the SFPR network. Here, $p=L/N$ is the edge density, and $\lambda$ is the control parameter corresponding to the degree exponent of non-PR SF networks. A second-order (first-order) PT is represented by a solid line (dashed line). The tricritical point is denoted as “TP.”

Figure 2

A schematic diagram of the selection rules in AP for cases (i)–(iii) defined in the text. In case (i), two intercomponent edges are drawn at random, and one of them is chosen to be connected according to the product rule (PR). In case (ii), one edge is intercomponent and the other edge is intracomponent. The latter is chosen. In cases (iii-a) and (iii-b), two intracomponent edges are drawn, and one is randomly chosen to be connected.

Figure 3

The fraction $G$ of the giant component versus the edge density $p$ for (a) the CL model under AP, and (b) the conventional CL model. Data were obtained for networks with various control parameters $\lambda$ [2.2, 2.4, 2.6, 2.8, 3.0, and 4.0 from left to right]. System size was fixed at $N={10}^7$.

Figure 4

(a) Same plot as Fig. 3 but for various system sizes $N={10}^5$, ${10}^6$, and ${10}^7$, from right to left. Control parameter $\lambda =2.2$. Inset: Plot of $p_c(N)$ versus $1/N$. The solid line is a guideline with slope 0.15, indicating that $p_c(\infty )\to 0$. (b) Plot of the jump $\delta G$ around $p_c(N)$ versus $1/N$. Solid line is a guideline with slope 0.23. (c) Susceptibility versus $p$. Inset: The peak value versus $1/N$. (d) Same as (a) for $\lambda =2.8$. Inset: Same as the inset of (a) for $\lambda =2.8$. Solid line is a guideline with slope 0.0, indicating that $p_c(\infty )$ is finite. (e) Scaling plot of $\Delta /N^{0.8}$ versus $N$ for $\lambda =2.8$, where $\Delta /N\equiv p_1-p_0$ with $p_1$ and $p_0$ being the edge densities when the fractions of the giant component reach $G=0.3$ and $G=N^{-1/2}$ for the first time, respectively. (f) Same as (c) for $\lambda =2.8$. Error bars in each data point are within symbol sizes.

Figure 5

Plot of $p_c(N)$ versus $1/N$ for $\lambda =2.3$ (○), 2.4 (◇), and 2.5 (□). Error bars in each data point are within symbol sizes. Inset: plot of successive slopes of $p_c(N)$ versus $1/N$. For $\lambda =2.4$ (◇) and 2.5 (□), the successive slopes approach zero, indicating that $p_c(\infty )$ is finite. For $\lambda =2.3$ (○), the successive slopes approach a finite negative value, indicating $p_c(\infty )=0$.

Figure 6

Plot of the degree distribution $P_d(k)$ of the SFPR network when $\lambda =2.2$. We find that the degree exponent ${\lambda }^{\prime }\approx 2.8$ when $p=0.234\approx p_c(N)$ (○), and ${\lambda }^{\prime }\approx 2.25$ when $p=0.8$ (◇). The degree distribution of the conventional CL network at $p=0.234$ is drawn (□) for comparison. The system size is fixed at $N={10}^7$. Inset: plot of the degree distributions of the SFPR network at $p_c(N)$ for various system sizes $N={10}^5$, ${10}^6$, and ${10}^7$ from left to right, showing the distributions’ insensitivity to system size. Data have been shifted vertically for clear view in the main panel, and for easier comparison in the inset.