Slow convergence tunes onset of strongly discontinuous explosive percolation

Wei Chen, Raissa M. D’SouzaarXiv 2011 · arXiv

Abstract: Contrary to initial beliefs, random graph evolution under an edge competition process with fixed choice (an Achlioptas process) seems to lead to a continuous transition in the thermodynamic limit. Here we show that a simpler model, which examines a single edge at a time, can lead to a strongly discontinuous transition and we derive the underlying mechanism. Starting from a collection of $n$ isolated nodes, potential edges chosen uniformly at random from the complete graph are examined one at a time while a cap, $k$, on the maximum allowed component size is enforced. Edges whose addition would exceed size $k$ can be simply rejected provided the accepted fraction of edges never becomes smaller than a decreasing function, $g(k) = 1/2 + (2k)^{-\beta}$. If the rate of decay is sufficiently small ($\beta < 1$), troublesome edges can always be rejected, and the growth in the largest component is dominated by an overtaking mechanism leading to a strongly discontinuous transition. If $\beta > 1$, once the largest component reaches size $n^{1/\beta}$, troublesome edges must often be accepted, leading to direct growth dominated by stochastic fluctuations and a “weakly” discontinuous transition.

Introduction

Percolation theory provides the theoretical underpinning for analyzing properties of networks, including epidemic thresholds and system resilience. Traditionally, the emergence of a "giant component" in random graphs is a continuous process. However, the discovery of "explosive percolation" in 2009 suggested that these transitions could be discontinuous. Subsequent research revealed that many such models actually revert to continuous transitions in the thermodynamic limit ($n \to \infty$). This paper addresses the challenge of identifying a simple model that remains truly discontinuous for infinite networks and derives the physical mechanism—growth by overtaking—that drives this behavior.

Methods

The researchers analyzed a modified version of the Bohman, Frieze, Wormald (BFW) algorithm. Starting with $n$ isolated nodes, potential edges are sampled one by one. A cap $k$ is maintained on the maximum allowed component size. An edge that would create a component larger than $k$ can be rejected, but only if the fraction of accepted edges remains above a threshold function: $g(k) = 1/2 + (2k)^{-\beta}$. The parameter $\beta$ controls how quickly the requirement to accept edges relaxes as $k$ grows. The study utilized numerical simulations with system sizes up to $n = 10^8$ nodes and analytical derivations to track the evolution of the largest components ($C_1, C_2, C_3$).

The Overtaking Mechanism

The fundamental insight of this work is the distinction between "direct growth" and "growth by overtaking." In standard percolation, the giant component grows by absorbing smaller clusters. In the BFW model with small $\beta$, the rejection rule prevents the largest component from growing too large directly. Instead, multiple medium-sized components grow in parallel. Eventually, two of these components merge and suddenly "overtake" the previous leader. This overtaking event creates the abrupt, discontinuous jump in the size of the giant component.

Evolution of the largest components $C_1$ and $C_2$ for (a) $\beta=0.5$ and (b) $\beta=2.0$. The insets show the detailed step-like growth near the transition point.

Scaling and the Thermodynamic Limit

A critical test for true discontinuity is whether the size of the jump in connectivity vanishes as the system size $n$ increases. The authors found that $\beta$ acts as a tuning knob for this behavior:

  • Strongly Discontinuous ($\beta < 1$): The rejection rule is strong enough to consistently prevent direct growth. For $\beta = 0.5$, the largest jump in the giant component ($\Delta C_{max}$) remains constant regardless of $n$, proving the transition is fundamentally discontinuous.
  • Weakly Discontinuous ($\beta > 1$): The rule is weak; once components reach size $n^{1/\beta}$, the algorithm is forced to accept edges that lead to direct growth. For $\beta = 2.0$, the jump size shrinks following a power law ($\Delta C_{max} \approx 0.285n^{-0.0068}$), indicating it would eventually vanish in an infinite system.
Scaling of the maximum jump size $\Delta C_{max}$ as a function of system size $n$. For $\beta=0.5$, the jump size remains constant, while for $\beta=2.0$, it decays as a power law.

Conclusion

By identifying the "growth by overtaking" mechanism, this research provides a clear physical basis for strongly discontinuous transitions in network evolution. The model demonstrates that simple size constraints and minimum density requirements can lead to abrupt phase transitions that persist even in the thermodynamic limit. Future work may apply this framework to real-world competitive systems, such as industrial growth or ecological niche evolution, to identify similar abrupt transitions.

Summary updated

Abstract

Contrary to initial beliefs, random graph evolution under an edge competition process with fixed choice (an Achlioptas process) seems to lead to a continuous transition in the thermodynamic limit. Here we show that a simpler model, which examines a single edge at a time, can lead to a strongly discontinuous transition and we derive the underlying mechanism. Starting from a collection of n isolated nodes, potential edges chosen uniformly at random from the complete graph are examined one at a time while a cap, k, on the maximum allowed component size is enforced. Edges whose addition would exceed size k can be simply rejected provided the accepted fraction of edges never becomes smaller than a decreasing function, g(k) = 1/2 + (2k)−β. If the rate of decay is sufficiently small (β &amp;lt; 1), troublesome edges can always be rejected, and the growth in the largest component is dominated by an overtaking mechanism leading to a strongly discontinuous transition. If β&amp;gt; 1, once the largest component reaches size n1/β, troublesome edges must often be accepted, leading to direct growth dominated by stochastic fluctuations and a “weakly ” discontinuous transition. PACS numbers: 64.60.ah, 64.60.aq, 89.75.Hc, 02.50.Ey Percolation is a theoretical underpinning for analyz-ing properties of networks, including epidemic thresholds,
BibTeX
@misc{chen2011slow,
  author = {Wei Chen and Raissa M. D’Souza},
  title = {{Slow convergence tunes onset of strongly discontinuous explosive percolation}},
  year = {2011},
  eprint = {1106.2088},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1106.2088},
}
Figure