Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 13 March 2009:
Vol. 323. no. 5920, pp. 1453 - 1455
DOI: 10.1126/science.1167782
Prev | Table of Contents | Next

Reports

Explosive Percolation in Random Networks

Dimitris Achlioptas,1 Raissa M. D'Souza,2,3* Joel Spencer4

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.

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

Read the Full Text

To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)