Local cluster aggregation models of explosive percolation

Abstract

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 Erdos-Renyi model.

Final version as appearing in PRL

References in corpus (6)

• Explosive percolation in scale-free networks
• Percolation Transitions in Scale-Free Networks under Achlioptas Process
• Construction and Analysis of Random Networks with Explosive Percolation
• Explosive percolation: a numerical analysis
• Cluster aggregation model for discontinuous percolation transition
• Kinetic Theory of Random Graphs: from Paths to Cycles

Cited by in corpus (75)

• Recent advances in percolation theory and its applications
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Percolation on complex networks: Theory and application
• "Explosive Percolation" Transition is Actually Continuous
• Impact of Single Links in Competitive Percolation -- How complex networks grow under competition
• Self-organized adaptation of a simple neural circuit enables complex robot behaviour
• Explosive Phenomena in Complex Networks
• Explosive Percolation is Continuous, but with Unusual Finite Size Behavior
• Explosive percolation via control of the largest cluster
• Explosive Percolation: Novel critical and supercritical phenomena
• Recent advances and open challenges in percolation
• Strongly discontinuous explosive percolation with multiple giant components
• Scaling behavior of explosive percolation on the square lattice
• 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
• Achlioptas process phase transitions are continuous
• Solution of the explosive percolation quest: Scaling functions and critical exponents
• Statistical properties of the quantum internet
• Anomalous discontinuity at the percolation critical point of active gels
• Finite-size scaling theory for explosive percolation transitions
• Using explosive percolation in analysis of real-world networks
• Crackling Noise in Fractional Percolation -- Randomly distributed discontinuous jumps in explosive percolation
• Gaussian model of explosive percolation in three and higher dimensions
• Suppression effect on explosive percolations
• Bohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition
• Achlioptas processes are not always self-averaging
• Deriving an underlying mechanism for discontinuous percolation
• Solution of the explosive percolation quest. II. Infinite-order transition produced by the initial distributions of clusters
• Transport on exploding percolation clusters
• Functional Control of Oscillator Networks
• Discontinuous percolation transitions in real physical systems
• Explosive Percolation: Unusual Transitions of a Simple Model
• Unstable supercritical discontinuous percolation transitions
• Correlated percolation and tricriticality
• Explosive Percolation Obeys Standard Finite-Size Scaling in an Event-based Ensemble
• Criterion for explosive percolation transitions on complex networks
• Explosive percolations on the Bethe Lattice
• Critical exponents of the explosive percolation transition
• Two Types of Discontinuous Percolation Transitions in Cluster Merging Processes
• Jigsaw percolation: What social networks can collaboratively solve a puzzle?
• Choice-Driven Phase Transition in Complex Networks
• Non-Local Product Rules for Percolation
• Percolation in a distorted square lattice
• Explosive percolation in graphs
• Transmission of packets on a hierarchical network: Statistics and explosive percolation
• Social Climber attachment in forming networks produces phase transition in a measure of connectivity
• Inverting the Achlioptas rule for explosive percolation
• Watersheds and Explosive percolation
• Explosive percolation in finite dimensions
• Explosive Ising
• Information entropy of classical versus explosive percolation
• Genuine Non-Self-Averaging and Ultra-Slow Convergence in Gelation
• Criticality and Continuity of Explosive Site Percolation in Random Networks
• Product-Sum universality and Rushbrooke inequality in explosive percolation
• Analysis on the evolution process of BFW-like model with explosive percolation of multiple giant components
• Explosive percolation on scale-free multifractal weighted planar stochastic lattice
• Discontinuous percolation in diffusion-limited cluster aggregation
• Scaling relations and finite-size scaling in gravitationally correlated lattice percolation models
• Degree product rule tempers explosive percolation in the absence of global information
• Scaling behavior of information entropy in explosive percolation transitions
• Convergence of Achlioptas processes via differential equations with unique solutions
• Link rewiring with local information--induced hybrid percolation transitions
• The Atlas for the Aspiring Network Scientist
• Universality class of explosive percolation in Barabási-Albert networks
• Bohman-Frieze processes at criticality and emergence of the giant component
• Percolation Transitions in Growing Networks Under Achlioptas Processes: Analytic Solutions
• Explosive percolation on the Bethe lattice is ordinary
• Universality of percolation at dynamic pseudocritical point
• Discontinuous percolation via suppression of neighboring clusters in a network
• A Novel Approach to Discontinuous Bond Percolation Transition
• Complex networks of interacting stochastic tipping elements: cooperativity of phase separation in the large-system limit
• Discontinuous emergence of a giant cluster in assortative scale-free networks
• Kinetics of Aggregation with Choice