Deriving an underlying mechanism for discontinuous percolation

Abstract

Understanding what types of phenomena lead to discontinuous phase transitions in the connectivity of random networks is an outstanding challenge. Here we show that a simple stochastic model of graph evolution leads to a discontinuous percolation transition and we derive the underlying mechanism responsible: growth by overtaking. 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 $k$ can be simply rejected provided the accepted fraction of edges never becomes smaller than a function which decreases with $k$ as $g(k)=1/2+(2k{)}^{-\beta }$. We show that if $\beta <1$ it is always possible to reject a sampled edge and the growth in the largest component is dominated by an overtaking mechanism leading to a discontinuous transition. If $\beta >1$, once $k\ge n^{1/\beta }$, there are situations when a sampled edge must be accepted leading to direct growth dominated by stochastic fluctuations and a "weakly" discontinuous transition. We also show that the distribution of component sizes and the evolution of component sizes are distinct from those previously observed and show no finite size effects for the range of $\beta$ studied.

6 pages. Final version appearing in EPL (2012)

References in corpus (13)

• Self-organized adaptation of a simple neural circuit enables complex robot behaviour
• Impact of Single Links in Competitive Percolation -- How complex networks grow under competition
• Explosive Percolation is Continuous, but with Unusual Finite Size Behavior
• Explosive percolation via control of the largest cluster
• Strongly discontinuous explosive percolation with multiple giant components
• Ordinary Percolation with Discontinuous Transitions
• Discontinuous Percolation Transitions in Epidemic Processes, Surface Depinning in Random Media and Hamiltonian Random Graphs
• Tricritical point in explosive percolation
• Continuity of the Explosive Percolation Transition
• Tricritical point in heterogeneous k-core percolation
• Suppression effect on explosive percolations
• Bohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition
• Discontinuous percolation transitions in real physical systems

Cited by in corpus (12)

• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Percolation on complex networks: Theory and application
• Explosive Phenomena in Complex Networks
• Explosive Percolation: Novel critical and supercritical phenomena
• Recent advances and open challenges in percolation
• Micro-transition cascades to percolation
• Explosive Percolation: Unusual Transitions of a Simple Model
• Unstable supercritical discontinuous percolation transitions
• Crossover phenomena of percolation transition in evolution networks with hybrid attachment
• Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
• Stacked triangular lattice: Percolation properties
• Degree product rule tempers explosive percolation in the absence of global information