Given enough choice, simple local rules percolate discontinuously

Abstract

There is still much to discover about the mechanisms and nature of discontinuous percolation transitions. Much of the past work considers graph evolution algorithms known as Achlioptas processes in which a single edge is added to the graph from a set of $k$ randomly chosen candidate edges at each timestep until a giant component emerges. Several Achlioptas processes seem to yield a discontinuous percolation transition, but it was proven by Riordan and Warnke that the transition must be continuous in the thermodynamic limit. However, they also proved that if the number $k(n)$ of candidate edges increases with the number of nodes, then the percolation transition may be discontinuous. Here we attempt to find the simplest such process which yields a discontinuous transition in the thermodynamic limit. We introduce a process which considers only the degree of candidate edges and not component size. We calculate the critical point $t_c=(1-\theta (\frac{1}{k}))n$ and rigorously show that the critical window is of size $O(\frac{n}{k(n)})$. If $k(n)$ grows very slowly, for example $k(n)=\log n$, the critical window is barely sublinear and hence the phase transition is discontinuous but appears continuous in finite systems. We also present arguments that Achlioptas processes with bounded size rules will always have continuous percolation transitions even with infinite choice.

Accepted to European Physical Journal B

References in corpus (15)

• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Scaling and percolation in the small-world network model
• Epidemics and percolation in small-world networks
• "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 Percolation is Continuous, but with Unusual Finite Size Behavior
• Construction and Analysis of Random Networks with Explosive Percolation
• Avoiding a Spanning Cluster in Percolation Models
• Strongly discontinuous explosive percolation with multiple giant components
• A new route to Explosive Percolation
• Continuity of the Explosive Percolation Transition
• Achlioptas process phase transitions are continuous
• Phase transitions for modified Erdös-Rényi processes

Cited by in corpus (7)

• The Kuramoto model in complex networks
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Percolation on complex networks: Theory and application
• Explosive Phenomena in Complex Networks
• Genuine Non-Self-Averaging and Ultra-Slow Convergence in Gelation
• Degree product rule tempers explosive percolation in the absence of global information
• Adhesion-induced Discontinuous Transitions and Classifying Social Networks