Explosive Percolation Is Continuous

被引:227
作者
Riordan, Oliver [1 ]
Warnke, Lutz [1 ]
机构
[1] Univ Oxford, Math Inst, Oxford OX1 3LB, England
基金
英国工程与自然科学研究理事会;
关键词
EMERGENCE; BIRTH;
D O I
10.1126/science.1206241
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
"Explosive percolation" is said to occur in an evolving network when a macroscopic connected component emerges in a number of steps that is much smaller than the system size. Recent predictions based on simulations suggested that certain Achlioptas processes (much-studied local modifications of the classical mean-field growth model of Erdos and Renyi) exhibit this phenomenon, undergoing a phase transition that is discontinuous in the scaling limit. We show that, in fact, all Achlioptas processes have continuous phase transitions, although related models in which the number of nodes sampled may grow with the network size can indeed exhibit explosive percolation.
引用
收藏
页码:322 / 324
页数:3
相关论文
共 29 条
[1]   Explosive Percolation in Random Networks [J].
Achlioptas, Dimitris ;
D'Souza, Raissa M. ;
Spencer, Joel .
SCIENCE, 2009, 323 (5920) :1453-1555
[2]   Error and attack tolerance of complex networks [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 2000, 406 (6794) :378-382
[3]  
[Anonymous], 1990, Random Structures and Algorithms, DOI [10.1002/rsa.3240010305, DOI 10.1002/RSA.3240010305]
[4]  
[Anonymous], 2003, Internet Math., DOI [10.1080/15427951.2004.10129080, DOI 10.1080/15427951.2004.10129080]
[5]   Balanced allocations [J].
Azar, Y ;
Broder, AZ ;
Karlin, AR ;
Upfal, E .
SIAM JOURNAL ON COMPUTING, 1999, 29 (01) :180-200
[6]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[7]   MEMORYLESS RULES FOR ACHLIOPTAS PROCESSES [J].
Beveridge, Andrew ;
Bohman, Tom ;
Frieze, Alan ;
Pikhurko, Oleg .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (02) :993-1008
[8]   Creating a giant component [J].
Bohmam, Tom ;
Kravitz, David .
COMBINATORICS PROBABILITY & COMPUTING, 2006, 15 (04) :489-511
[9]   Avoiding a giant component [J].
Bohman, T ;
Frieze, A .
RANDOM STRUCTURES & ALGORITHMS, 2001, 19 (01) :75-85
[10]   Emergence of Connectivity in Networks [J].
Bohman, Tom .
SCIENCE, 2009, 323 (5920) :1438-1439