Explosive percolation: A numerical analysis

Percolation is one of the most studied processes in statistical physics. A recent paper by Achlioptas et al. [Science 323, 1453 (2009)] showed that the percolation transition, which is usually continuous, becomes discontinuous (“explosive”) if links are added to the system according to special cooperative rules (Achlioptas processes). In this paper, we present a detailed numerical analysis of Achlioptas processes with product rule on various systems, including lattices, random networks á la Erdös-Rényi, and scale-free networks. In all cases, we recover the explosive transition by Achlioptas et al. However, the explosive percolation transition is kind of hybrid as, despite the discontinuity of the order parameter at the threshold, one observes traces of analytical behavior such as power-law distributions of cluster sizes. In particular, for scale-free networks with degree exponent $\lambda <3$, all relevant percolation variables display power-law scaling, just as in continuous second-order phase transitions.

Figure 1

(Color online) Scheme of an Achlioptas process with product rule. One of the two links represented by dashed lines, which are selected at random among all possible pairs of nonadjacent nodes, has to be eventually added to the system. According to the product rule, the winner is the link that joins the pair of clusters with the smaller product size. In this case, the winning link is that between clusters $c_1$ and $c_2$, whose product size is $7\times 2=14$, which is smaller than the product of the sizes of clusters $c_3$ and $c_4$ $\left(4\times 4=16\right)$.

Figure 2

(Color online) Analysis of 2D lattices. (a) RG model. The percolation strength $P$ is plotted as a function of the lattice side $L$ for three different values of the occupation probability: $p=0.499$ (violet diamonds), $p=0.5$ (orange circles), and $p=0.501$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.5$, which allows to determine $\beta /\nu =0.11\left(1\right)$. (b) RG model. The average cluster size $S$ is plotted as a function of the lattice side $L$ for the same values of $p$ as those used in (a). Dashed line has slope $\gamma /\nu =1.76\left(1\right)$. (c) PR model. The percolation strength $P$ is plotted as a function of the lattice side $L$ for three different values of the occupation probability: $p=0.5256$ (violet diamonds), $p=0.5266$ (orange circles), and $p=0.5276$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.5266\left(2\right)$, which allows to determine $\beta /\nu =0.07\left(3\right)$. (d) PR model. $S$ is plotted as a function of the lattice side $L$ for the same values of $p$ used in (c). The dashed line has slope $\gamma /\nu =1.7\left(1\right)$. (e) Comparison between the cluster size distributions measured at the critical threshold for both growth models. For RG (orange circles) $\tau =2.05\left(1\right)$ (black dashed line), while for PR (gray squares) $\tau =1.9\left(1\right)$ (red dotted line). Simulations have been performed on systems with $L=4096$. (f) $\Delta p$ as a function of the system size $N$: $\alpha =0.15\left(1\right)$ (dashed black line) for RG (orange circles) and $\alpha =0.24\left(1\right)$ (dotted red line) for PR (gray squares). The first value is questionable, as the scaling should yield a plateau $\left(\alpha \sim 0\right)$, like we have indirectly verified (see text). To see the correct scaling, one should simulate much larger systems.

Figure 3

(Color online) Analysis of 3D lattices. (a) RG model. The percolation strength $P$ is plotted as a function of the lattice side $L$ for three different values of the occupation probability: $p=0.2478$ (violet diamonds), $p=0.2488$ (orange circles), and $p=0.2498$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.2488\left(3\right)$, which allows to determine $\beta /\nu =0.48\left(1\right)$. (b) RG model. The average cluster size $S$ is plotted as a function of the lattice side $L$ for the same values of $p$ used in (a). The dashed line has slope $\gamma /\nu =2.0\left(1\right)$. (c) PR model. The percolation strength $P$ is plotted as a function of the lattice side $L$ for three different values of the occupation probability: $p=0.3866$ (violet diamonds), $p=0.3876$ (orange circles) and $p=0.3886$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.3876\left(2\right)$, which allows to determine $\beta /\nu =0.02\left(2\right)$. (d) PR model. The average cluster size $S$ is plotted as a function of the lattice side $L$ for the same values of $p$ used in (c). The dashed line has slope $\gamma /\nu =2.1\left(1\right)$. (e) Cluster size distributions $n_s$ for 3D lattices at the critical point. For both percolation models, $n_s\sim s^{-\tau }$ as $s$ increases. For RG (orange circles) $\tau =2.20\left(1\right)$ (black dashed line), while for PR (gray squares) $\tau =1.99\left(4\right)$ (red dotted line). Simulations have been performed on systems with $L=256$. (f) We plot the quantity $\Delta p$ as a function of the system size $N$. For both models, $\Delta p$ decreases as a power law, $\Delta p\sim N^{-\alpha }$, as $N$ increases. In particular we have $\alpha =0.10\left(1\right)$ (dashed black line) for RG (orange circles) and $\alpha =0.30\left(1\right)$ (dotted red line) for PR (gray squares). The first value is questionable, as the scaling should yield a plateau $\left(\alpha \sim 0\right)$ like we have indirectly verified (see text). To see the correct scaling, one should simulate much larger systems.

Figure 4

(Color online) Analysis of ER random networks. (a) RG model. The percolation strength $P$ is plotted as a function of the system size $N$ for three different values of the occupation probability: $p=0.495$ (violet diamonds), $p=0.5$ (orange circles), and $p=0.505$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.5$, which allows to determine $\beta /\nu =0.33\left(1\right)$. (b) RG model. The average cluster size $S$ is plotted as a function of the network size $N$ for the same values of $p$ used in (a). The dashed line has slope $\gamma /\nu =0.34\left(1\right)$. (c) PR model. The percolation strength $P$ is plotted as a function of the network size $N$ for three different values of the occupation probability: $p=0.8872$ (violet diamonds), $p=0.8882$ (orange circles), and $p=0.8892$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.8882\left(2\right)$, which allows to determine $\beta /\nu =0.02\left(1\right)$. (d) PR model. The average cluster size $S$ is plotted as a function of the network size $N$ for the same values of $p$ used in (c). The dashed line has slope $\gamma /\nu =0.48\left(4\right)$. (e) Cluster size distributions $n_s$ for ER random networks at critical point. For both percolation models, $n_s\sim s^{-\tau }$ as $s$ increases. For RG (orange circles) $\tau =2.51\left(2\right)$ (black dashed line), while for PR (gray squares) $\tau =2.08\left(5\right)$ (red dotted line). Simulations have been performed on systems with $N=8192000$. (f) We plot the quantity $\Delta p$ as a function of the system size $N$. For both models, $\Delta p$ decreases as a power law, $\Delta p\sim N^{-\alpha }$, as $N$ increases. In particular, we have $\alpha =0.03\left(1\right)$ (dashed black line) for RG (orange circles) and $\alpha =0.36\left(1\right)$ (dotted red line) for PR (gray squares).

Figure 5

(Color online) Achlioptas process with PR on random SF networks. The plot shows the percolation threshold $p_c\left(N\right)$ as a function of the degree exponent $\lambda$ for various network sizes $N$. Black line represents the infinite-size limit extrapolation of the critical threshold, performed by applying Eq. (8). The percolation threshold becomes nonzero for $\lambda >{\lambda }_c\sim 2.3$. Reprinted figure with permission from Ref. [16].

Figure 6

(Color online) Percolation transition induced by an Achlioptas process with PR on SF networks. The degree exponent $\lambda =2.5$. (a) The percolation strength $P$ is plotted as a function of the system size $N$ for three different values of the occupation probability: $p=0.0529$ (violet diamonds), $p=0.0629$ (orange circles), and $p=0.0729$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.0629\left(1\right)$, which allows to determine $\beta /\nu =0.59\left(1\right)$. (b) The average cluster size $S$ is plotted as a function of the network size $N$ for the same values of $p$ used in (a). The dashed line has slope $\gamma /\nu =0.24\left(1\right)$.

Figure 7

(Color online) Percolation transition induced by an Achlioptas process with PR on SF networks. The degree exponent $\lambda =2.8$. (a) The percolation strength $P$ is plotted as a function of the system size $N$ for three different values of the occupation probability: $p=0.1229$ (violet diamonds), $p=0.1329$ (orange circles), and $p=0.1349$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.1329\left(1\right)$, which allows to determine $\beta /\nu =0.50\left(1\right)$. (b) The average cluster size $S$ is plotted as a function of the network size $N$ for the same values of $p$ used in (a). The dashed line has slope $\gamma /\nu =0.42\left(1\right)$.

Figure 8

(Color online) Rescaling of the percolation variables $P$ and $S$ near the percolation transition induced by an Achlioptas process with PR on SF networks with degree exponent $\lambda =2.8$. System size $N$ goes from $256000$ to $4096000$ via successive doublings.

Figure 9

(Color online) Achlioptas test for SF networks. (a) $\lambda =2.5$: we plot the quantity $\Delta p$ as a function of the system size $N$. For both percolation models, $\Delta p$ decreases as a power law, $\Delta p\sim N^{-\alpha }$, as $N$ increases. In particular, we have $\alpha =-0.04\left(1\right)$ (dashed black line) for RG (orange circles) and $\alpha =-0.26\left(3\right)$ (dotted red line) for PR (gray squares). We also consider the transition window $\Delta \tilde{p}$ (defined in Sec. 3), from which we obtain $\tilde{\alpha }=-0.06\left(1\right)$ (lower black dashed line) for RG (orange diamonds) and $\tilde{\alpha }=0.31\left(1\right)$ (lower red dotted line) for PR (gray triangles). (b) $\lambda =2.8$: same plot as the one of (a). The measured exponents are $\alpha =-0.04\left(1\right)$ (dashed black line) for RG (orange circles), $\alpha =0.04\left(1\right)$ (dotted red line) for PR (gray squares), $\tilde{\alpha }=-0.07\left(1\right)$ (lower black dashed line) for RG (orange diamonds), and $\tilde{\alpha }=0.32\left(1\right)$ (lower red dotted line) for PR (gray triangles).

Figure 10

(Color online) Analysis of SF networks with degree exponent $\lambda =3.5$. (a) RG model. The percolation strength $P$ is plotted as a function of the system size $N$ for three different values of the occupation probability: $p=0.074$ (violet diamonds), $p=0.078$ (orange circles), and $p=0.082$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.078\left(1\right)$, which allows to determine $\beta /\nu =0.38\left(1\right)$. (b) RG mode. The average cluster size $S$ is plotted as a function of the lattice side $L$ for the same values of $p$ used in (a). The dashed line has slope $\gamma /\nu =0.15\left(2\right)$. (c) PR model. The percolation strength $P$ is plotted as a function of the system size $N$ for three different values of the occupation probability: $p=0.2214$ (violet diamonds), $p=0.2224$ (orange circles), and $p=0.2234$ (gray squares). Dashed line stands for the best fit obtained at the critical point $p=p_c=0.2224\left(2\right)$, which yields $\beta /\nu =-0.06\left(3\right)$. (d) PR model. The average cluster size $S$ is plotted as a function of the network size $N$ for the same values of $p$ used in (c). The dashed line has slope $\gamma /\nu =0.40\left(9\right)$. (e) For both growth models, $n_s\sim s^{-\tau }$ as $s$ increases. For RG (orange circles) $p_c=0.078\left(1\right)$ and $\tau =2.94\left(1\right)$ (black dashed line), while for PR (gray squares) $p_c=0.2224\left(2\right)$ and $\tau =2.2\left(1\right)$ (red dotted line). Simulations have been performed on systems with $N=8192000$. (f) We plot the quantity $\Delta p$ as a function of the system size $N$. For both growth models, $\Delta p$ decreases as a power law, $\Delta p\sim N^{-\alpha }$, as $N$ increases. In particular we have $\alpha =-0.02\left(1\right)$ (upper dashed black line) for RG (orange circles) and $\alpha =0.34\left(1\right)$ (dotted red line) for PR (gray squares). We also consider the transition window $\Delta \tilde{p}={\tilde{p}}_2-p_1$, where ${\tilde{p}}_2$ is the minimal value of the occupation probability at which $P=0.2$. In this case, we find again a good power-law fit. For RG (orange diamonds), the decay exponent is unchanged since $\tilde{\alpha }=-0.02\left(1\right)$ (lower black dashed line). Similarly for PR (gray triangles) $\tilde{\alpha }=0.35\left(1\right)$.

Figure 11

(Color online) Achlioptas process with PR on SF networks. Distributions of the values of the order parameter $P$ at the pseudocritical point $p_c\left(N\right)$ for different degree exponents $\lambda$: (a) 2.1, (b) 2.5, (c) 2.8, and (d) 3.5. The main frame of each plot shows the values of $P$ for each of 1000 realizations. Insets display the distribution of the $P$ values (upper panel) and its cumulative (lower panel). The distributions are all bimodal, which indicates that the order parameter undergoes a discontinuous jump at the critical point. The network size is $N=8192000$ in all cases.

Figure 12

(Color online) Cluster size distributions $n_s$ for Achlioptas processes with PR at the critical point. The cluster size distributions scale as power laws (i.e., $n_s\sim s^{-\tau }$) for all systems analyzed in this paper. The Fisher exponents $\tau$ are very close to each other and all distributions collapse into a unique curve with the only exceptions of the ones obtained for SF networks with $\lambda =2.5$ and $\lambda =2.8$. Dashed black line is a power law with exponent $-2$ plotted as a useful reference. The lattice side $L=4096$ for 2D lattice and $L=256$ for 3D lattice. $N=8192000$ for all networks.

Figure 13

(Color online) Achlioptas process with PR on SF networks. Relation between the degree exponent $\lambda$ imposed through the starting degree sequence and the effective exponent ${\lambda }_{eff}$ of the degree distribution of the system when it is at the percolation threshold. The relation is linear with good approximation (black dashed line). The network size is $N=8192000$.