Article,
Deriving an underlying mechanism for discontinuous percolation
EPL (Europhysics Letters), (Dec 1, 2012)
DOI: 10.1209/0295-5075/100/66006
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 + (2 k ) − β . We show that if β < 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 β > 1, once k ≥ n 1/ β , 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 β studied.
