Explosive Percolation in Random Networks
- 1 Department of Computer Science, University of California at Santa Cruz, Santa Cruz, CA 95064, USA.
- 2 Department of Mechanical and Aeronautical Engineering, University of California at Davis, Davis, CA 95616, USA.
- 3 Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA.
- 4 Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA.
- ↵* To whom correspondence should be addressed. E-mail: raissa{at}cse.ucdavis.edu
Abstract
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 Erdös-Rényi network formation model causes its percolation transition to become discontinuous.
- Received for publication 28 October 2008.
- Accepted for publication 16 January 2009.
