Hamiltonian approach for explosive percolation

We present a cluster growth process that provides a clear connection between equilibrium statistical mechanics and an explosive percolation model similar to the one recently proposed by D. Achlioptas et al. [Science 323, 1453 (2009)]. We show that the following two ingredients are sufficient for obtaining an abrupt (first-order) transition in the fraction of the system occupied by the largest cluster: (i) the size of all growing clusters should be kept approximately the same, and (ii) the inclusion of merging bonds (i.e., bonds connecting vertices in different clusters) should dominate with respect to the redundant bonds (i.e., bonds connecting vertices in the same cluster). Moreover, in the extreme limit where only merging bonds are present, a complete enumeration scheme based on treelike graphs can be used to obtain an exact solution of our model that displays a first-order transition. Finally, the presented mechanism can be viewed as a generalization of standard percolation that discloses a family of models with potential application in growth and fragmentation processes of real network systems.

Figure 1

(Color online) Two ingredients for explosive percolation. Here we show a possible configuration for a growth process where, at each step, any unoccupied bond can be introduced in the graph. For instance, in this figure we show three bonds that could be added in the next step, namely, $\alpha$, $\beta$, and $\gamma$. The two ingredients for obtaining a sharp transition are the following: (i) bonds that keep the clusters approximately at the same size are favored over bonds that result in larger size discrepancies; and (ii) bonds that connect vertices in the distinct clusters (merging bonds) are favored over bonds that connect vertices in the same cluster (redundant bonds). Thus, among the bonds indicated, $\alpha$ has the smallest probability due to condition (ii), $\beta$ is not accepted due to condition (i), and the most probable is the $\gamma$ bond.

Figure 2

(Color online) Transition to explosive percolation. When the process favors redundant bonds, $\alpha =2.5$, the largest cluster follows a slow continuous growth for the largest cluster. When the merging bonds are favored, $\alpha =2.7$, the system displays an abrupt transition around a critical connectivity $k=2$. In this case the transition becomes sharper as the system size increases, suggesting a first-order transition type of behavior. The inset shows the total number of redundant bonds divided by the number of vertices in the network, $N_r=N_b/N$. For $\alpha =2.7$, redundant bonds are not included before $k=2$. In all simulations, we use $\beta =1.0$ and take an average over 1000 realizations of the growth process.

Figure 3

(Color online) Growth process when redundant bonds are favored. Here we show results for $\beta =1.0$ and $\alpha =2.0$. Since in this situation merging bonds are less likely to be included, the graph has to reach states where it splits in several fully connected subgraphs, before a new merging bond is introduced. When the merging bond is included, a new and larger cluster is created. This explains the presence of discontinuous jumps in the size of the largest cluster. Assuming that the system consists of only fully connected clusters of the same size, we obtain the dotted line shown in the inset, $S=k+1$. This condition corresponds to the minimum bound for the simulation results, that approximately follows this theoretical prediction. Since the largest cluster $S$ is finite for any finite connectivity $k$, the system does not display a percolation transition.

Figure 4

(Color online) Growth process when merging bonds are favored. For $\beta =1.0$ and $\alpha =3.0$, the system does not include redundant bonds and all clusters remain treelike until the critical point $k_c=2$ is reached. Supposing that the system comprises only clusters of the same size $S$, we have that $S=2/\left(2-k\right)$ for the case of trees. This relation works as a minimum bound for the simulation results, as shown in the inset on the left. Thus we have the critical condition $k_c=2$, where the size of the largest cluster diverges to occupy the whole network. For $k<k_c$ the largest cluster remains finite and its occupation fraction $P_{\infty }$ goes to zero as the system size grows, characterizing a typical first-order transition. The inset on the right shows the threshold connectivity $k_t$ to obtain a largest cluster greater than the square root of the system size, $S>N^{1/2}$ (black circles), and greater than half the system size, $S>N/2$ (red squares). The red line follows $k=2–4/N$, the expected behavior for the connectivity where $S=N/2$. The black line is a fit of the form $k=p_1+p_2\times N^{-p_3}$, with $p_1=1.99\pm 0.03$, $p_2=3.14\pm 0.02$, and $p_3=0.53\pm 0.05$. In the limit $N\to \infty$ both curves converge to $k\approx 2$, that is in the thermodynamic limit we observe at $k=2$ a discontinuous transition in the order parameter from a vanishing fraction, $P_{\infty }\sim N^{-1/2}$, to a finite fraction, $P_{\infty }=1/2$, confirming the approach to a first-order transition.