Strongly discontinuous explosive percolation with multiple giant components

Abstract

We generalize the random graph evolution process of Bohman, Frieze, and Wormald [T. Bohman, A. Frieze, and N. C. Wormald, Random Struct. Algorithms, 25, 432 (2004)]. Potential edges, sampled uniformly at random from the complete graph, are considered one at a time and either added to the graph or rejected provided that the fraction of accepted edges is never smaller than a decreasing function asymptotically approaching the value alpha = 1/2. We show that multiple giant components appear simultaneously in a strongly discontinuous percolation transition and remain distinct. Furthermore, tuning the value of alpha determines the number of such components with smaller alpha leading to an increasingly delayed and more explosive transition. The location of the critical point and strongly discontinuous nature are not affected if only edges which span components are sampled.

Final version appearing in PRL

References in corpus (15)

• Epidemic spreading in scale-free networks
• Epidemics and percolation in small-world networks
• "Explosive Percolation" Transition is Actually Continuous
• 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 in scale-free networks
• Explosive percolation via control of the largest cluster
• Percolation Transitions in Scale-Free Networks under Achlioptas Process
• Construction and Analysis of Random Networks with Explosive Percolation
• Local cluster aggregation models of explosive percolation
• Scaling behavior of explosive percolation on the square lattice
• Cluster aggregation model for discontinuous percolation transition
• A new route to Explosive Percolation
• Explosive Percolation in the Human Protein Homology Network
• Percolation with Multiple Giant Clusters

Cited by in corpus (53)

• 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 is Continuous, but with Unusual Finite Size Behavior
• Explosive Percolation: Novel critical and supercritical phenomena
• Recent advances and open challenges in percolation
• Avoiding a Spanning Cluster in Percolation Models
• Discontinuous Percolation Transitions in Epidemic Processes, Surface Depinning in Random Media and Hamiltonian Random Graphs
• Are Percolation Transitions always Sharpened by Making Networks Interdependent?
• Robustness and Assortativity for Diffusion-like Processes in Scale-free Networks
• Continuity of the Explosive Percolation Transition
• Stability of a Giant Connected Component in a Complex Network
• Percolation framework to describe El Niño conditions
• Solution of the explosive percolation quest: Scaling functions and critical exponents
• Micro-transition cascades to percolation
• Percolation with long-range correlated disorder
• Crackling Noise in Fractional Percolation -- Randomly distributed discontinuous jumps in explosive percolation
• Gaussian model of explosive percolation in three and higher dimensions
• 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
• Explosive site percolation with a product rule
• Critical phenomena in heterogeneous k-core percolation
• Robustness and modular structure in networks
• Explosive Percolation: Unusual Transitions of a Simple Model
• Unstable supercritical discontinuous percolation transitions
• Crossover phenomena of percolation transition in evolution networks with hybrid attachment
• Correlated percolation and tricriticality
• Two Types of Discontinuous Percolation Transitions in Cluster Merging Processes
• Weakly Explosive Percolation in Directed Networks
• Stacked triangular lattice: Percolation properties
• Scaling of Clusters near Discontinuous Percolation Transitions in Hyperbolic Networks
• Non-Local Product Rules for Percolation
• The winner takes it all -- How to win network globalization
• A percolation model with continuously varying exponents
• How to share underground reservoirs
• Transmission of packets on a hierarchical network: Statistics and explosive percolation
• Kinetics of Ring Formation
• Method for estimating critical exponents in percolation processes with low sampling
• Unified framework for hybrid percolation transitions based on microscopic dynamics
• Given enough choice, simple local rules percolate discontinuously
• Explosive percolation in finite dimensions
• Watersheds and Explosive percolation
• Criticality and Continuity of Explosive Site Percolation in Random Networks
• Analysis on the evolution process of BFW-like model with explosive percolation of multiple giant components
• Spectral Anlysis on Explosive Percolation
• Degree product rule tempers explosive percolation in the absence of global information
• Bohman-Frieze processes at criticality and emergence of the giant component
• Crossover behavior of conductivity in a discontinuous percolation model
• Network-Growth Rule Dependence of Fractal Dimension of Percolation Cluster on Square Lattice
• Universality in boundary domain growth by sudden bridging
• Kinetics of Aggregation with Choice
• Evolution of autocatalytic sets in a competitive percolation model