Construction and Analysis of Random Networks with Explosive Percolation

The existence of explosive phase transitions in random (Erdös Rényi-type) networks has been recently documented by Achlioptas, D’Souza, and Spencer [Science 323, 1453 (2009)] via simulations. In this Letter we describe the underlying mechanism behind these first-order phase transitions and develop tools that allow us to identify (and predict) when a random network will exhibit an explosive transition. Several interesting new models displaying explosive transitions are also presented.

Figure 1

Transition diagrams for largest cluster (LC), Erdos-Renyi (ER), min-cluster (MC), min-cluster-3 (MC3), and smallest cluster (SC) rules. LC and ER display second-order transitions while the others are first order.

Figure 2

A log-log plot of $\Delta$ vs $n$ for ER, MC, and MC3 rules, for $\alpha =1/2$. (Markers are for individual realizations.)

Figure 3

Plot of $\frac{1}{n}F\mathbf{(}t(n^{0.5}),n^{0.4}\mathbf{)}$ as a function of $n$ for the Erdos-Renyi (ER) and min-cluster (MC) rules. All coefficients of regression are statistically significant ($p<{10}^{-3}$).