Local Cluster Aggregation Models of Explosive Percolation

We introduce perhaps the simplest models of graph evolution with choice that demonstrate discontinuous percolation transitions and can be analyzed via mathematical evolution equations. These models are local, in the sense that at each step of the process one edge is selected from a small set of potential edges sharing common vertices and added to the graph. We show that the evolution can be accurately described by a system of differential equations and that such models exhibit the discontinuous emergence of the giant component. Yet they also obey scaling behaviors characteristic of continuous transitions, with scaling exponents that differ from the classic Erdős-Rényi model.

Figure 1

Typical evolution of $C_1/n$ for Erdős-Rényi (ER), adjacent edge (AE), and triangle rule (TR), for $n={10}^6$. (Top inset: Example of three candidate edges for TR, and two candidate edges for AE.) [Bottom Inset: ${\Delta }_n(1/2,0.2)/n$ vs $n$ for AE and ${\Delta }_n(1/2,0.4)/n$ vs $n$ for TR. Each data point is the average over 50 iid realizations, with error bars smaller than symbols. Dashed lines are $\Delta /n=1.95n^{-0.323}$ for AE and $\Delta /n=1.84n^{-0.367}$ for TR.]

Figure 2

(a) Measuring the lower and upper boundaries of ${\Delta }_n(1/2,0.2)/n$ for AE and ${\Delta }_n(1/2,0.4)/n$ for TR. (b) Component density $n_i\sim i^{-2.1}$ shown for AE at $t_c$ (TR and product rule are similar). More interesting is the rank-size component distribution (inset for Erdős-Rényi and AE at $t_c$), showing the preponderance of large components for AE. Fitting for $50<j<50,000$ yields $C_j\sim j^{-\delta }$, with $\delta =-0.66$ for Erdős-Rényi and $\delta =-0.90$ for AE (TR and product rule are similar but more noisy). (c) $W$ versus $t$ for TR. Inset shows $W\sim (t_c-t{)}^{-\alpha }$ with the red line showing the best fit, attained with $\alpha =1.13$. The same red line is depicted in the main figure.