Abstract
The location and nature of the percolation transition in random networks is a subject of intense interest. Recently, a series of graph evolution processes have been introduced that lead to discontinuous percolation transitions where the addition of a single edge causes the size of the largest component to exhibit a significant macroscopic jump in the thermodynamic limit. We investigate whether the location of the largest jump coincides with the percolation threshold for a range of processes. We find that the largest jump asymptotically occurs at the percolation transition for Erdős-Rényi and other processes exhibiting global continuity. However, for percolation processes exhibiting genuine discontinuities, such as "staircase" models, the largest discontinuity generically does not coincide with the percolation transition. Distinct parameter regimes in the supercritical regime feature unstable discontinuous transitions—a novel and unexpected phenomenon in percolation.
Introduction
Percolation theory traditionally describes how a system transitions from isolated clusters to a state of global connectivity (a "giant component") as edges are added. This transition is typically viewed as a single critical event occurring at a threshold $p_c$. Recent discoveries of "explosive" percolation—transitions that appear nearly instantaneous—have sparked debate over whether these transitions are truly discontinuous or merely steep continuous curves. While most research focuses on behavior at the threshold, this study investigates the "supercritical" regime to determine if the largest jump in connectivity always coincides with the initial percolation threshold.
Methodology
The researchers employed large-scale numerical simulations and scaling analysis across several random network models:
- Erdős-Rényi (ER): The baseline model with random edge addition.
- Achlioptas Processes (AP): Models using edge competition rules (e.g., $PR_{max}$, $PR_{min}$).
- Staircase Models: Including the "Devil’s Staircase" (DS), Nagler-Gutch (NG), and modified ER (mER) models, which favor merging components of similar sizes.
- Bohman-Frieze-Wormald (BFW) Model: A model where component growth is restricted by a parameter $\alpha$.
Synthetic networks were generated with system sizes up to $N = 10^7$ nodes. The timing of the largest jump ($t_\Delta$) relative to the percolation threshold ($t_c$) was tracked to observe convergence in the thermodynamic limit ($N \to \infty$).
Results
Convergence in Continuous and Explosive Models
In globally continuous models like ER and certain explosive models (e.g., Product Rule models), the largest jump in the size of the largest component ($C_1$) acts as a precursor that eventually aligns with the percolation threshold as the network size increases.
As shown in Figure 1, the distance $(t_\Delta - t_c)/N$ scales as $N^{-\gamma}$ with exponents ranging from approximately 0.22 to 0.45, indicating that the jump and threshold coincide in the infinite system limit.
Supercritical Discontinuities and Staircase Transitions
In contrast, models exhibiting a "staircase" of jumps (DS, NG, mER) show that the largest jump generically does not coincide with the initial threshold. Instead, the system undergoes massive merges well into the supercritical regime.
Figure 4 demonstrates that the gap between the first jump ($p_1$) and subsequent jumps (e.g., $p_2$) converges to a non-zero constant. This confirms that the staircase of jumps is a permanent feature of these systems rather than a finite-size artifact.
BFW Phase Diagram and Unstable Coexistence
The BFW model reveals a complex phase diagram dependent on the parameter $\alpha$. The model can enter a "stable" regime where multiple giant components coexist or an "unstable" regime where these giants eventually collide in a massive, supercritical jump. For instance, at $\alpha = 0.530$, two giant components emerge simultaneously but are unstable, merging in a second, larger transition later.
Conclusion
This work demonstrates that seemingly and genuinely discontinuous percolation transitions involve rich behavior in the supercritical regime, which has been largely ignored. While the largest jump coincides with the threshold in continuous models, it is often a separate supercritical event in discontinuous models due to the unstable coexistence of multiple giant components. Future work is needed to fully understand the mechanisms behind the periods of stability between jumps and to explore these phenomena in real-world infrastructure or biological networks.
Summary updated