Skip to main content
SpringerLink
Log in
Book cover

Encyclopedia of Complexity and Systems Science pp 1–26Cite as

Bootstrap Percolation

  • Living reference work entry
  • First Online:

Definition of the Subject

In bootstrap percolation, we start with a lattice configuration of occupied and vacant sites. Occupied sites that have less than a certain prescribed number of occupied neighbors are rendered vacant, and as new occupied sites are found to satisfy the same condition, these are also rendered vacant. The process is iterated until eventually no more sites can be removed (if any exist). Bootstrap percolation endeavors to determine whether any occupied sites will survive the culling process and what the macroscopic geometrical properties of the occupied ensembles are. In essence, it is a generalization of conventional percolation which has led to many fruitful insights. A complementary view, which emphasizes the dynamical aspect of the bootstrap process, treats the vacant sites as invasive units and occupied sites as inert ones. Inert sites that are surrounded by too many invasive sites will become irreversibly infected and will start themselves to invade others. At...

This is a preview of subscription content, log in via an institution.

Abbreviations

Bethe lattice:

A graph of nodes (sites) each being linked to exactly z other nodes in the graph (z is the coordination number). The Bethe lattice is an infinite object such that there is no boundary and each node has an identical topology. Given any two nodes, there is only one unique set of links connecting them, so there are no closed loops. This is a regular graph with connectivity z. The Cayley tree, also a loopless graph with connectivity z, differs from the Bethe lattice in that a finite fraction of nodes leads to dead ends at a boundary (where they have connectivity 1).

Bootstrap percolation:

Also known as k-core percolation, is defined as follows. Given a collection of occupied (or active) and vacant (inactive) sites on a lattice, subsets might exist with the following property: Elements in each subset must be occupied and have at least k occupied neighbors, each of those occupied neighbor in turn belonging to the same subset. Bootstrap percolation occurs if any subset exists that spans the system from one end to the other.

Cluster:

Any subset of occupied sites, each having k or more occupied sites belonging to the same subset. The emergence of a spanning cluster underlies the bootstrap percolation transition.

Culling process:

Starting from an initial configuration, culling means that occupied sites with less than k neighbors are rendered vacant, i.e., “culled,” and the same operation is iterated a sufficient number of times as to achieve a final configuration with no more sites that are candidates for culling. The culling process is a practical protocol that leads to identify all the relevant subsets (i.e., clusters) in bootstrap percolation.

Lattice:

A collection of points (“sites”) generated from linear combinations with integral coefficients of some basis vectors. A d-dimensional lattice is generated from d basis vectors. Therefore, a d-dimensional lattice is a d-dimensional array or regularly spaced points. A lattice of finite size is such that all the integral coefficients have lower and upper bounds. The coordination number z is the number of sites (called the nearest neighbors) of equal least distance to any given site.

Random network:

A network (or graph) of nodes (sites) linked to other randomly chosen nodes. The network is characterized by the distribution of the degree (the number of neighbors of a node). We will discuss bootstrap percolation (or k-core percolation) on simple random, uncorrelated networks with arbitrary degree distribution (we consider always undirected networks).

Regular lattice:

A regular lattice is a lattice generated from basis vectors that are Cartesian basis vectors, i.e., it is the set of points or a bounded proper subset of points in Zd. A square lattice is the two-dimensional regular lattice whose basis vectors are a(1,0) and a(0,1); a simple cubic lattice has basis vectors a(1,0,0), a(0,1,0), and a(0,0,1). A hypercubic lattice is a regular lattice of dimensionality \( d>3 \). The coordination number z of a regular lattice equals 2d. The length a is called the lattice spacing (it is set to unity here for practical purposes).

Bibliography

  • Adler J (1991) Bootstrap percolation. Phys A 171(3):453–470

    Article  Google Scholar 

  • Adler J, Aharony A (1988) Diffusion percolation. I. Infinite time limit and bootstrap percolation. J Phys A Math Gen 21(6):1387–1404

    Article  ADS  MathSciNet  Google Scholar 

  • Adler J, Lev U (2003) Bootstrap percolation: visualisations and applications. Braz J Phys 33:641

    Article  ADS  Google Scholar 

  • Adler J, Stauffer D (1990) Evidence for non-universal exponents in bootstrap percolation. J Phys A Math Gen 23:L1119

    Article  ADS  Google Scholar 

  • Adler J, Palmer RG, Meyer H (1987) Transmission of order in some unusual dilute systems. Phys Rev Lett 58(9):882–885

    Article  ADS  MathSciNet  Google Scholar 

  • Adler J, Stauffer D, Aharony A (1989) Comparison of bootstrap percolation models. J Phys A Math Gen 22:L297

    Article  ADS  Google Scholar 

  • Aizenman M, Lebowitz JL (1988) Metastability effects in bootstrap percolation. J Phys A Math Gen 21:3801–3813

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Alvarez-Hamelin JI, Dall’Asta L, Barrat A, Vespignani A (2005) k-Core decomposition: a tool for the analysis of large scale internet graphs. eprint arXiv:cs/0504107

    Google Scholar 

  • Balogh J, Bollobás B (2003) Sharp thresholds in bootstrap percolation. Phys A Stat Mech Appl 326(3–4):305–312

    Article  MATH  Google Scholar 

  • Balogh J, Bollobás B (2006) Bootstrap percolation on the hypercube. Probab Theory Relat Fields 134(4):624–648

    Article  MathSciNet  MATH  Google Scholar 

  • Balogh J, Pete G (1998) Random disease on the square grid. Random Struct Algoritm 13(3–4):409–422

    Article  MathSciNet  MATH  Google Scholar 

  • Balogh J, Pittel BG (2007) Bootstrap percolation on the random regular graph. Random Struct Algoritm 30(1–2):257–286

    Article  MathSciNet  MATH  Google Scholar 

  • Balogh J, Bollobás B, Morris R (2007) Majority bootstrap percolation on the hypercube. Arxiv preprint mathCO/0702373

    Google Scholar 

  • Balogh J, Bollobás B, Duminil-Copin H, Morris R (2012) The sharp threshold for bootstrap percolation in all dimensions. Trans Am Math Soc 364(5):2667–2701

    Article  MathSciNet  MATH  Google Scholar 

  • Bollobás B (2001) Random graphs. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  • Branco NS (1993) Probabilistic bootstrap percolation. J Stat Phys 70:1035–1044

    Article  ADS  MATH  Google Scholar 

  • Branco NS, Silva CJ (1999) Universality class for bootstrap percolation with m = 3 on the cubic lattice. Int J Mod Phys C 10:921–930

    Article  ADS  Google Scholar 

  • Branco N, Dos Santos R, de Queiroz S (1984) Bootstrap percolation: a renormalization group approach. J Phys C 17:1909–1921

    Article  Google Scholar 

  • Bringmann K, Mahlburg K (2012) Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation. Trans Am Math Soc 364(7):3829–3859

    Article  MathSciNet  MATH  Google Scholar 

  • Cerf R, Cirillo E (1999) Finite size scaling in three-dimensional bootstrap percolation. Ann Probab 27(4):1837–1850

    Article  MathSciNet  MATH  Google Scholar 

  • Cerf R, Manzo F (2002) The threshold regime of finite volume bootstrap percolation. Stoch Process Appl 101:69–82

    Article  MathSciNet  MATH  Google Scholar 

  • Chalupa J, Leath PL, Reich GR (1979) Bootstrap percolation on a Bethe lattice. J Phys C Solid State Phys 12(1):L31–L35

    Article  ADS  Google Scholar 

  • Chaves C, Koiller B (1995) Universality, thresholds and critical exponents in correlated percolation. Phys A 218(3):271–278

    Article  Google Scholar 

  • De Gregorio P, Lawlor A, Bradley P, Dawson KA (2004) Clarification of the bootstrap percolation paradox. Phys Rev Lett 93:025501

    Article  ADS  Google Scholar 

  • De Gregorio P, Lawlor A, Bradley P, Dawson KA (2005) Exact solution of a jamming transition: closed equations for a bootstrap percolation problem. Proc Natl Acad Sci 102:5669–5673

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • De Gregorio P, Lawlor A, Dawson KA (2006) New approach to study mobility in the vicinity of dynamical arrest; exact application to a kinetically constrained model. Europhys Lett 74:287–293

    Article  ADS  Google Scholar 

  • Dorogovtsev SN, Goltsev AV, Mendes JFF (2006) k-Core organization of complex networks. Phys Rev Lett 96:040601

    Article  ADS  MATH  Google Scholar 

  • Duarte J (1989) Simulation of a cellular automat with an oriented bootstrap rule. Phys A 157(3):1075–1079

    Article  Google Scholar 

  • Ertel W, Frobröse K, Jäckle J (1988) Constrained diffusion dynamics in the hard-square lattice gas at high density. J Chem Phys 88:5027–5034

    Article  ADS  Google Scholar 

  • Fernholz D, Ramachandran V (2003) The giant k-core of a random graph with a specified degree sequence. manuscript, UT-Austin

    Google Scholar 

  • Fredrickson GH, Andersen HC (1984) Kinetic Ising model of the glass transition. Phys Rev Lett 53(13):1244–1247

    Article  ADS  Google Scholar 

  • Goltsev AV, Dorogovtsev SN, Mendes JFF (2006) k-Core (bootstrap) percolation on complex networks: critical phenomena and nonlocal effects. Phys Rev E 73:056101

    Article  ADS  MathSciNet  Google Scholar 

  • Gravner J, Griffeath D (1996) First passage times for threshold growth dynamics on Z2. Ann Probab 24(4):1752–1778

    Article  MathSciNet  MATH  Google Scholar 

  • Gravner J, Holroyd A (2008) Slow convergence in bootstrap percolation. Ann Probab 18(3):909–928

    Article  MathSciNet  MATH  Google Scholar 

  • Gravner J, Holroyd A (2009) Local bootstrap percolation. Electron J Probab 14(14):385–399

    Article  MathSciNet  MATH  Google Scholar 

  • Gravner J, McDonald E (1997) Bootstrap percolation in a polluted environment. J Stat Phys 87(3):915–927

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Harris A, Schwarz J (2005) 1/d expansion for k-core percolation. Phys Rev E 72(4):46123

    Article  ADS  Google Scholar 

  • Holroyd A (2003) Sharp metastability threshold for two-dimensional bootstrap percolation. Probab Theory Relat Field 125(2):195–224

    Article  MathSciNet  MATH  Google Scholar 

  • Holroyd A (2006) The metastability threshold for modified bootstrap percolation in d dimensions. Electron J Probab 11:418–433

    Article  MathSciNet  MATH  Google Scholar 

  • Holroyd A, Liggett T, Romik D (2004) Integrals, partitions and cellular automata. Trans Am Math Soc 356:3349–3368

    Article  MathSciNet  MATH  Google Scholar 

  • Ising E (1925) Beitrag zur Theorie des Ferromagnetismus. Z Phys 31:253–258

    Article  ADS  Google Scholar 

  • Jäckle J, Krönig A (1994) A kinetic lattice-gas model for the triangular lattice with strong dynamic correlations: I. cself-diffusion. J Phys Condens Matter 6:7633–7653

    Article  Google Scholar 

  • Jeng M, Schwarz JM (2007) Comment on “jamming percolation and glass transitions in lattice models”. Phys Rev Lett 98(12):129601

    Article  ADS  Google Scholar 

  • Kirkpatrick S, Wilcke W, Garner R, Huels H (2002) Percolation in dense storage arrays. Phys A Stat Mech Appl 314(1–4):220–229

    Article  MathSciNet  MATH  Google Scholar 

  • Kob W, Andersen HC (1993) Kinetic lattice-gas model of cage effects in high-density liquids and a test of mode-coupling theory of the ideal-glass transition. Phys Rev E 48:4364–4377

    Article  ADS  Google Scholar 

  • Kogut PM, Leath PL (1981) Bootstrap percolation transitions on real lattices. J Phys C 14(22):3187–3194

    Article  ADS  Google Scholar 

  • Kurtsiefer D (2003) Threshold value of three dimensional bootstrap percolation. Int J Mod Phys C 14:529

    Article  ADS  Google Scholar 

  • Lawlor A, De Gregorio P, Bradley P, Sellitto M, Dawson KA (2005) Geometry of dynamically available empty space is the key to near-arrest dynamics. Phys Rev E 72:021401

    Article  ADS  Google Scholar 

  • Lawlor A, De Gregorio P, Cellai D, Dawson KA (2008) (to be published)

    Google Scholar 

  • Manna SS (1998) Abelian cascade dynamics in bootstrap percolation. Phys A Stat Theory Phys 261:351–358

    Article  Google Scholar 

  • Medeiros M, Chaves C (1997) Universality in bootstrap and diffusion percolation. Phys A 234(3):604–610

    Article  Google Scholar 

  • Moukarzel C, Duxbury PM, Leath PL (1997) Infinite-cluster geometry in central-force networks. Phys Rev Lett 78(8):1480–1483

    Article  ADS  Google Scholar 

  • Mountford TS (1995) Critical length for semi-oriented bootstrap percolation. Stoch Process Appl 56:185–205

    Article  MathSciNet  MATH  Google Scholar 

  • Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45:167

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • O’Hern C, Silbert L, Liu A, Nagel S (2003) Jamming at zero temperature and zero applied stress: the epitome of disorder. Phys Rev E 68(1):11306

    Article  Google Scholar 

  • Onsager L (1944) Crystal statistics. I. A two-dimensional model with an order–disorder transition. Phys Rev 65(3–4):117–149

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Parisi G, Rizzo T (2006) On k-core percolation in four dimensions. Arxiv preprint cond-mat/0609777

    Google Scholar 

  • Pittel B, Spencer J, Wormald N (1996) Sudden emergence of a giant k-core in a random graph. J Comb Theory B 67:111–151

    Article  MathSciNet  MATH  Google Scholar 

  • Pollak M, Riess I (1975) Application of percolation theory to 2D-3D Heisenberg ferromagnets. Phys Stat Solidi (B) 69(1):K15–K18

    Article  ADS  Google Scholar 

  • Ritort F, Sollich P (2003) Glassy dynamics of kinetically constraint models. Adv Phys 52:219–342

    Article  ADS  Google Scholar 

  • Sabhapandit S, Dhar D, Shukla P (2002) Hysteresis in the random-field Ising model and bootstrap percolation. Phys Rev Lett 88(19):197202

    Article  ADS  Google Scholar 

  • Sahimi M (1994) Applications of percolation theory. Taylor/Francis, London

    Google Scholar 

  • Schonmann R (1990a) Critical points of two-dimensional bootstrap percolation-like cellular automata. J Stat Phys 58(5):1239–1244

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • Schonmann R (1990b) Finite size scaling behavior of a biased majority rule cellular automaton. Phys A 167(3):619–627

    Article  MathSciNet  Google Scholar 

  • Schonmann R (1992) On the behavior of some cellular automata related to bootstrap percolation. Ann Probab 20(1):174–193

    Article  MathSciNet  MATH  Google Scholar 

  • Schwarz JM, Liu AJ, Chayes LQ (2006) The onset of jamming as the sudden emergence of an infinite k-core cluster. Europhys Lett (EPL) 73(4):560–566

    Article  ADS  Google Scholar 

  • Sellitto M, Biroli G, Toninelli C (2005) Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics. Europhys Lett 69(4):496–502

    Article  ADS  Google Scholar 

  • Smirnov S, Werner W (2001) Critical exponents for 2D percolation. Math Res Lett 8:729–744

    Article  MathSciNet  MATH  Google Scholar 

  • Stauffer D, Aharony A (1992) Introduction to percolation theory. Taylor/Francis, London

    MATH  Google Scholar 

  • Toninelli C, Biroli G, Fisher DS (2006) Jamming percolation and glass transitions in lattice models. Phys Rev Lett 96(3):035702

    Article  ADS  Google Scholar 

  • Toninelli C, Biroli G, Fisher D (2007) Toninelli, Biroli, and Fisher reply. Phys Rev Lett 98(12):129602

    Article  ADS  Google Scholar 

  • Treaster M, Conner W, Gupta I, Nahrstedt K (2006) Contagalert: using contagion theory for adaptive, distributed alert propagation. In: Network computing and applications, NCA 2006, pp 126–136

    Google Scholar 

  • van Enter A (1987) Proof of Straley’s argument for bootstrap percolation. J Stat Phys 48(3):943–945

    Article  ADS  MATH  Google Scholar 

  • van Enter A, Hulshof T (2007) Finite-size effects for anisotropic bootstrap percolation: logarithmic corrections. J Stat Phys 128(6):1383–1389

    Article  ADS  MathSciNet  MATH  Google Scholar 

  • van Enter ACD, Adler J, Duarte JAMS (1990) Finite size effects for some bootstrap percolation models. J Stat Phys 60:323–332

    Article  ADS  MathSciNet  Google Scholar 

  • van Enter A, Adler J, Duarte J (1991) Finite-size effects for some bootstrap percolation models, addendum. J Stat Phys 62:505–506

    Article  ADS  Google Scholar 

  • Widom B (1974) The critical point and scaling theory. Physica 73(1):107–118

    Article  ADS  Google Scholar 

  • Wilson K (1983) The renormalization group and critical phenomena. Rev Mod Phys 55:583–600

    Article  ADS  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Fisica e Astronomia, Università di Padova, INFN. Sezione di Padova, Via Marzolo 8, Padova, Italy

    Paolo De Gregorio

  2. School of Chemistry and Chemical Biology, University College Dublin, Dublin, Ireland

    Aonghus Lawlor & Kenneth A. Dawson

Authors
  1. Paolo De Gregorio
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aonghus Lawlor
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kenneth A. Dawson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paolo De Gregorio .

Editor information

Editors and Affiliations

  1. Ramtech Ltd., Larkspur, California, USA

    Robert A. Meyers

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer Science+Business Media New York

About this entry

Cite this entry

De Gregorio, P., Lawlor, A., Dawson, K.A. (2016). Bootstrap Percolation. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27737-5_41-3

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-27737-5_41-3

  • Received:

  • Accepted:

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Online ISBN: 978-3-642-27737-5

  • eBook Packages: Springer Reference Physics and AstronomyReference Module Physical and Materials ScienceReference Module Chemistry, Materials and Physics

Publish with us

Policies and ethics

Search

Navigation