Criticality and scaling behavior of percolation with multiple giant clusters under an Achlioptas process

Achlioptas processes, a class of percolation models which can lead to rich critical phenomena, including the well-known explosive percolation, have attracted much attention in recent years. In this paper, we show that, in a three-vertex Achlioptas process, two giant clusters emerge after the percolation transition with size fluctuations in different realizations, and the choice of the connecting vertex in the smaller cluster depends on a probability parameter $p$, the increase of which can make the transition sharper. Using finite-size scaling analysis, we can determine the critical point $r_c$ and critical exponents $\eta$, $1/\nu$, and $\beta$ through Monte Carlo simulations. Comparison of such exponents for different giant clusters indicates that their critical nature is always the same. However, when link choice is strongly biased, it is surprising that the scaling relation $\eta =\beta /\nu$ is violated, and the data collapse for scaling function diverges. Furthermore, by inspecting the variance of exponents with $p$, three distinct scaling phases are classified for different parameter intervals according to the divergence scaling function, which suggests an inconsistent scaling form in the critical window with the supercritical region. The study on the criticality and scaling behavior of multiple giant clusters in an Achlioptas process, in particular, the discovery of three scaling phases that depend on the parameter $p$, may help us in finding a complete scaling theory for the Achlioptas-process percolation and give insight into understanding the accelerating nature of the phase transition for Achlioptas processes once reaching criticality.

Figure 1

Sketch of the model. Every step, select three vertices and connect two of them. If any two vertices are in the same cluster, connect them. In (a), if three vertices $v_1,v_2,v_3$ are selected in three distinct clusters, then $v_1,v_2$ are chosen to be connected (solid line), since the size product of the clusters they belong to, $7\times 2=14$, is less than the square of the other one, $4^2=16$. In (b), if $v_1^{\prime },v_2^{\prime },v_3^{\prime }$ are selected, $v_1^{\prime },v_2^{\prime }$ are rejected to be connected (dotted line) since $5\times 6>3^2$, and then $v_3^{\prime }$ is connected to the smaller cluster with probability $p$ or the larger cluster with probability $1-p$.

Figure 2

(a) $C_1$ and $C_2$ versus $r$ in original model for $p=0,0.5,1$ respectively, showing two giant clusters emerging through the transitions. (b) The behavior of $C_1$ versus $r$ in the treelike version of our model at $p=0,0.5,1$ together with the basic PR model, where only one giant cluster exists. The system size is $N=1.6\times {10}^6$, and the results are averaged over ${10}^4$ simulations.

Figure 3

Empirical distributions in values of $C_1$ and $C_2$ at $r=1$ obtained over ${10}^4$ independent realizations under three different graph sizes, $N={10}^5,4\times {10}^5,1.6\times {10}^6$ for $p=0,0.5,1$, respectively. The inset in the top right panel is the dependence of the peaks in $P\left(C_1\right)$ and $P\left(C_2\right)$ at $p=0$ on graph size $N$.

Figure 4

Dependence of the mean and standard deviation of $C_1$, $C_2$ and $C_1+C_2$ extrapolated to infinite graph size at $r=1$ on the probability parameter $p$. The inset in each panel shows the dependence of the mean or standard deviation of $C_1$ on the graph size $N$, respectively; the corresponding parameter $p$ is $0,0.2,0.5,0.8,1$ from top to bottom.

Figure 5

[(a), (c), and (e)] The log-log plot of the reduced size $C_1$ versus $N$ at different $r$ for $p=0,0.5,1$ respectively. The curvature of $\ln C_1$ changes from negative to positive around $r_c$, and the slope of $\ln C_1$ with respect to $\ln N$ at $r_c$ (red circle) gives ${\eta }_1$. Inset: The log-log plot of the derivative $C_1^{\prime }{|}_r$ versus $N$ at $r_c$ shows a linear fit, from which we can get $1/{\nu }_1$ by the slope. [(b), (d), and (f)] Similar plot of the reduced size $C_2$ and the derivative $C_2^{\prime }{|}_r$ versus $N$ for $p=0,0.5,1$, respectively. Within the error bars, these two giant clusters have the same transition point $r_c$ and the same critical exponents for each $p$.

Figure 6

The log-log plot of $C_1$ versus $r-r_c$ at different system size $N$ for $p=0,0.5,1$, respectively. Curves for different $N$ coincide slightly beyond $r_c$ and are fitted by the dashed line, of which the slope gives the exponent ${\beta }_1$.

Figure 7

Data collapse for the universal scaling function of cluster $C_1$ according to the scaling form (2) in our model with $p=0,0.5,1$ and the ER model, respectively. All the plots are shown for the same critical region $[r_c-0.01,r_c+0.01]$ when $N=6.4\times {10}^6$.

Figure 8

Best data collapse for the scaling function in the supercritical region at $p=0$ or $p=1$, with the corresponding exponent $1/{\nu }^{\prime }$. Inset is the blowup of the region near the critical point for each plot.

Figure 9

(a) Dependence of the critical point on the parameter $p$. The error bars are smaller than the symbol. (b) Dependence of the critical exponents $\eta$ and $\beta$.

Figure 10

Dependence of the inconsistent inverse of exponent $1/\nu$ and $1/{\nu }^{\prime }$ on the parameter $p$. According to the relation of $1/\nu$ and $1/{\nu }^{\prime }$, we can classify the corresponding scaling into three phases.

Figure 11

The log-log plot of the largest finite cluster size versus $r-r_c$ for our model at $p=0,0.6,1$ and the ER model, respectively. In contrast to the conventional power-law scaling indicated by a straight line, there is a turning in the plot of our model, especially for the cases $p=0$ and $p=1$.