Explosive Percolation in Random Networks

被引:503
作者
Achlioptas, Dimitris [2 ]
D'Souza, Raissa M. [1 ,3 ]
Spencer, Joel [4 ]
机构
[1] Univ Calif Davis, Dept Mech & Aeronaut Engn, Davis, CA 95616 USA
[2] Univ Calif Santa Cruz, Dept Comp Sci, Santa Cruz, CA 95064 USA
[3] Santa Fe Inst, Santa Fe, NM 87501 USA
[4] NYU, Courant Inst Math Sci, New York, NY 10012 USA
基金
欧洲研究理事会;
关键词
D O I
10.1126/science.1167782
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
Networks in which the formation of connections is governed by a random process often undergo a percolation transition, wherein around a critical point, the addition of a small number of connections causes a sizable fraction of the network to suddenly become linked together. Typically such transitions are continuous, so that the percentage of the network linked together tends to zero right above the transition point. Whether percolation transitions could be discontinuous has been an open question. Here, we show that incorporating a limited amount of choice in the classic Erdos-Renyi network formation model causes its percolation transition to become discontinuous.
引用
收藏
页码:1453 / 1555
页数:3
相关论文
共 6 条
  • [1] Product rule wins a competitive game
    Beveridge, Andrew
    Bohman, Tom
    Frieze, Alan
    Pikhurko, Oleg
    [J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2007, 135 (10) : 3061 - 3071
  • [2] ERDOS P, 1960, B INT STATIST INST, V38, P343
  • [3] KRIVELEVICH M, 2008, HAMILTONICITY THRESH
  • [4] Random graph models of social networks
    Newman, MEJ
    Watts, DJ
    Strogatz, SH
    [J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 : 2566 - 2572
  • [5] Fast Monte Carlo algorithm for site or bond percolation
    Newman, M.E.J.
    Ziff, R.M.
    [J]. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 2001, 64 (1 II): : 1 - 016706
  • [6] Birth control for giants
    Spencer, Joel
    Wormald, Nicholas
    [J]. COMBINATORICA, 2007, 27 (05) : 587 - 628