Volume 100, Number 6, December 2012
|Number of page(s)||6|
|Section||Condensed Matter: Structural, Mechanical and Thermal Properties|
|Published online||08 January 2013|
Deriving an underlying mechanism for discontinuous percolation
1 School of Mathematical Sciences, Peking University - No. 5 Yiheyuan Road, Haidian, Beijing 100871, China
2 Institute of Computing Technology, Chinese Academy of Sciences - No. 6 KeXueYuanNanLu, Haidian, Beijing 100190, China
3 University of California - One Shields Avenue, Davis, CA 95616, USA
4 Beihang University - No. 37 Xueyuan Road, Haidian, Beijing 100191, China
5 Santa Fe Institute - 1399 Hyde Park Road, Santa Fe, NM 87501, USA
Received: 8 September 2012
Accepted: 27 November 2012
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)−β. 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 ⩾ n1/β, 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.
PACS: 64.60.ah – Percolation / 64.60.aq – Networks / 05.70.Ln – Nonequilibrium and irreversible thermodynamics
© EPLA, 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.