2010/11/30 by Wei Chen, Raissa M. D'Souza, Raissa M. D’Souza · 2 citations
Biochemistry, Genetics and Molecular Biology · Mathematics · Physics and Astronomy · #Combinatorics #Complex Network Analysis Techniques #Connected component #Critical point (mathematics) #Diffusion and Search Dynamics #Explosive material #Frieze #Geometry #Giant component #Graph #Mathematics #Percolation (cognitive psychology) #Physics #Random graph #Statistical physics #Stochastic processes and statistical mechanics #cond-mat.dis-nn
paper · pdf · doi:10.1103/physrevlett.106.115701
published as Phys. Rev. Lett. 106, 115701 (2011) · Final version appearing in PRL
openalex publication_date 2011/03/15 · arxiv created 2011/03/29 · arxiv updated 2011/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 α=1/2. We show that multiple giant components appear simultaneously in a strongly discontinuous percolation transition and remain distinct. Furthermore, tuning the value of α determines the number of such components with smaller α 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.