In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected clusters merge into significantly larger connected, so-called spanning cluster. The applications of percolation theory to materials science and in many other disciplines are discussed here and in the articles network theory and percolation.


A three-dimensional site percolation graph
A three-dimensional site percolation graph
Bond percolation in a square lattice from p=0.3 to p=0.52
Bond percolation in a square lattice from p=0.3 to p=0.52

The Flory–Stockmayer theory was the first theory investigating percolation processes.[1]

A representative question (and the source of the name) is as follows. Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled mathematically as a three-dimensional network of n × n × n vertices, usually called "sites", in which the edge or "bonds" between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path (meaning a path, each of whose links is an "open" bond) exists from the top to the bottom? The behavior for large n is of primary interest. This problem, called now bond percolation, was introduced in the mathematics literature by Broadbent & Hammersley (1957),[2] and has been studied intensively by mathematicians and physicists since then.

In a slightly different mathematical model for obtaining a random graph, a site is "occupied" with probability p or "empty" (in which case its edges are removed) with probability 1 – p; the corresponding problem is called site percolation. The question is the same: for a given p, what is the probability that a path exists between top and bottom? Similarly, one can ask, given a connected graph at what fraction 1 – p of failures the graph will become disconnected (no large component).

A 3D tube network percolation determination
A 3D tube network percolation determination

The same questions can be asked for any lattice dimension. As is quite typical, it is actually easier to examine infinite networks than just large ones. In this case the corresponding question is: does an infinite open cluster exist? That is, is there a path of connected points of infinite length "through" the network? By Kolmogorov's zero–one law, for any given p, the probability that an infinite cluster exists is either zero or one. Since this probability is an increasing function of p (proof via coupling argument), there must be a critical p (denoted by pc) below which the probability is always 0 and above which the probability is always 1. In practice, this criticality is very easy to observe. Even for n as small as 100, the probability of an open path from the top to the bottom increases sharply from very close to zero to very close to one in a short span of values of p.

Detail of a bond percolation on the square lattice in two dimensions with percolation probability p = 0.51
Detail of a bond percolation on the square lattice in two dimensions with percolation probability p = 0.51

For most infinite lattice graphs, pc cannot be calculated exactly, though in some cases pc there is an exact value. For example:


The universality principle states that the numerical value of pc is determined by the local structure of the graph, whereas the behavior near the critical threshold, pc, is characterized by universal critical exponents. For example the distribution of the size of clusters at criticality decays as a power law with the same exponent for all 2d lattices. This universality means that for a given dimension, the various critical exponents, the fractal dimension of the clusters at pc is independent of the lattice type and percolation type (e.g., bond or site). However, recently percolation has been performed on a weighted planar stochastic lattice (WPSL) and found that although the dimension of the WPSL coincides with the dimension of the space where it is embedded, its universality class is different from that of all the known planar lattices.[8][9]


Subcritical and supercritical

The main fact in the subcritical phase is "exponential decay". That is, when p < pc, the probability that a specific point (for example, the origin) is contained in an open cluster (meaning a maximal connected set of "open" edges of the graph) of size r decays to zero exponentially in r. This was proved for percolation in three and more dimensions by Menshikov (1986) and independently by Aizenman & Barsky (1987). In two dimensions, it formed part of Kesten's proof that pc = 1/2.[10]

The dual graph of the square lattice 2 is also the square lattice. It follows that, in two dimensions, the supercritical phase is dual to a subcritical percolation process. This provides essentially full information about the supercritical model with d = 2. The main result for the supercritical phase in three and more dimensions is that, for sufficiently large N, there is[clarification needed] an infinite open cluster in the two-dimensional slab 2 × [0, N]d − 2. This was proved by Grimmett & Marstrand (1990).[11]

In two dimensions with p < 1/2, there is with probability one a unique infinite closed cluster (a closed cluster is a maximal connected set of "closed" edges of the graph). Thus the subcritical phase may be described as finite open islands in an infinite closed ocean. When p > 1/2 just the opposite occurs, with finite closed islands in an infinite open ocean. The picture is more complicated when d ≥ 3 since pc < 1/2, and there is coexistence of infinite open and closed clusters for p between pc and 1 − pc. For the phase transition nature of percolation see Stauffer and Aharony[12] and Bunde and Havlin[13] . For percolation of networks see Cohen and Havlin.[14]


Zoom in a critical percolation cluster (Click to animate)
Zoom in a critical percolation cluster (Click to animate)

Percolation has a singularity at the critical point p = pc and many properties behave as of a power-law with , near . Scaling theory predicts the existence of critical exponents, depending on the number d of dimensions, that determine the class of the singularity. When d = 2 these predictions are backed up by arguments from conformal field theory and Schramm–Loewner evolution, and include predicted numerical values for the exponents. The values of the exponents are given in [12] and.[13] Most of these predictions are conjectural except when the number d of dimensions satisfies either d = 2 or d ≥ 6. They include:

See Grimmett (1999).[15] In 11 or more dimensions, these facts are largely proved using a technique known as the lace expansion. It is believed that a version of the lace expansion should be valid for 7 or more dimensions, perhaps with implications also for the threshold case of 6 dimensions. The connection of percolation to the lace expansion is found in Hara & Slade (1990).[16]

In two dimensions, the first fact ("no percolation in the critical phase") is proved for many lattices, using duality. Substantial progress has been made on two-dimensional percolation through the conjecture of Oded Schramm that the scaling limit of a large cluster may be described in terms of a Schramm–Loewner evolution. This conjecture was proved by Smirnov (2001)[17] in the special case of site percolation on the triangular lattice.

Different models


In biology, biochemistry, and physical virology

Percolation theory has been used to successfully predict the fragmentation of biological virus shells (capsids),[32][33] with the fragmentation threshold of Hepatitis B virus capsid predicted and detected experimentally.[34] When a critical number of subunits has been randomly removed from the nanoscopic shell, it fragments and this fragmentation may be detected using Charge Detection Mass Spectroscopy (CDMS) among other single-particle techniques. This is a molecular analog to the common board game Jenga, and has relevance to the broader study of virus disassembly. Interestingly, more stable viral particles (tilings with greater fragmentation thresholds) are found in greater abundance in nature.[32]

In ecology

Percolation theory has been applied to studies of how environment fragmentation impacts animal habitats[35] and models of how the plague bacterium Yersinia pestis spreads.[36]

Percolation of multilayer interdependent networks

Buldyrev et al.[37] developed a framework to study percolation in multilayer networks with dependency links between the layers. New physical phenomena has been found, including abrupt transitions and cascading failures.[38] When the networks are embedded in space they become extremely vulnerable even for a very small fraction of dependency links[39] and for localized attacks on a zero fraction of nodes.[40][41] When recovery of nodes is introduced, a rich phase diagram is found that include multicritical points, hysteresis and metastable regimes.[42][43]

In traffic

In recent articles, percolation theory has been applied to study traffic in a city. The quality of the global traffic in a city at a given time can be characterized by a single parameter, the percolation critical threshold. The critical threshold represents the velocity below which one can travel in a large fraction of the city network. Above this threshold the city network break into clusters of many sizes and one can travel within relatively small neighborhoods. This novel method is also able to identify repetitive traffic bottlenecks.[44] Critical exponents characterizing the cluster size distribution of good traffic are similar to those of percolation theory.[45] It is also found that during rush hours the traffic network can have several metastable states of different network sizes and the alternate between these states.[46] An empirical study regarding the spatial-temporal size distribution of traffic jams has been performed by Zhang et al.[47] They found an approximate universal power law for the jam sizes distribution in different cities. A method to identify functional clusters of spatial-temporal streets that represent fluent traffic flow in a city has been developed by Serok et al.[48]

See also


  1. ^ Sahini, M.; Sahimi, M. (2003-07-13). Applications Of Percolation Theory. CRC Press. ISBN 978-0-203-22153-2.
  2. ^ a b Broadbent, Simon; Hammersley, John (1957). "Percolation processes I. Crystals and mazes". Mathematical Proceedings of the Cambridge Philosophical Society. 53 (3): 629–641. Bibcode:1957PCPS...53..629B. doi:10.1017/S0305004100032680. ISSN 0305-0041.
  3. ^ Bollobás, Béla; Riordan, Oliver (2006). "Sharp thresholds and percolation in the plane". Random Structures and Algorithms. 29 (4): 524–548. arXiv:math/0412510. doi:10.1002/rsa.20134. ISSN 1042-9832. S2CID 7342807.
  4. ^ MEJ Newman; RM Ziff (2000). "Efficient Monte Carlo algorithm and high-precision results for percolation". Physical Review Letters. 85 (19): 4104–4107. arXiv:cond-mat/0005264. Bibcode:2000PhRvL..85.4104N. doi:10.1103/physrevlett.85.4104. PMID 11056635. S2CID 747665.
  5. ^ Erdős, P. & Rényi, A. (1959). "On random graphs I.". Publ. Math. (6): 290–297.
  6. ^ Erdős, P. & Rényi, A. (1960). "The evolution of random graphs". Publ. Math. Inst. Hung. Acad. Sci. (5): 17–61.
  7. ^ Bolloba's, B. (1985). "Random Graphs". Academic.
  8. ^ Hassan, M. K.; Rahman, M. M. (2015). "Percolation on a multifractal scale-free planar stochastic lattice and its universality class". Phys. Rev. E. 92 (4): 040101. arXiv:1504.06389. Bibcode:2015PhRvE..92d0101H. doi:10.1103/PhysRevE.92.040101. PMID 26565145. S2CID 119112286.
  9. ^ Hassan, M. K.; Rahman, M. M. (2016). "Universality class of site and bond percolation on multi-multifractal scale-free planar stochastic lattice". Phys. Rev. E. 94 (4): 042109. arXiv:1604.08699. Bibcode:2016PhRvE..94d2109H. doi:10.1103/PhysRevE.94.042109. PMID 27841467. S2CID 22593028.
  10. ^ Kesten, Harry (1982). Percolation Theory for Mathematicians. Birkhauser. doi:10.1007/978-1-4899-2730-9. ISBN 978-0-8176-3107-9.
  11. ^ Grimmett, Geoffrey; Marstrand, John (1990). "The Supercritical Phase of Percolation is Well Behaved". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 430 (1879): 439–457. Bibcode:1990RSPSA.430..439G. doi:10.1098/rspa.1990.0100. ISSN 1364-5021. S2CID 122534964.
  12. ^ a b Stauffer, Dietrich; Aharony, Anthony (1994). Introduction to Percolation Theory (2nd ed.). CRC Press. ISBN 978-0-7484-0253-3.
  13. ^ a b Bunde, A. & Havlin, S. (1996). Fractals and Disordered Systems. Springer.
  14. ^ Cohen, R. & Havlin, S. (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press.
  15. ^ Grimmett, Geoffrey (1999). Percolation. Grundlehren der mathematischen Wissenschaften. 321. Berlin: Springer. doi:10.1007/978-3-662-03981-6. ISBN 978-3-642-08442-3. ISSN 0072-7830.
  16. ^ Hara, Takashi; Slade, Gordon (1990). "Mean-field critical behaviour for percolation in high dimensions". Communications in Mathematical Physics. 128 (2): 333–391. Bibcode:1990CMaPh.128..333H. doi:10.1007/BF02108785. ISSN 0010-3616. S2CID 119875060.
  17. ^ Smirnov, Stanislav (2001). "Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limits". Comptes Rendus de l'Académie des Sciences. I. 333 (3): 239–244. arXiv:0909.4499. Bibcode:2001CRASM.333..239S. CiteSeerX doi:10.1016/S0764-4442(01)01991-7. ISSN 0764-4442.
  18. ^ Adler, Joan (1991), "Bootstrap percolation", Physica A: Statistical Mechanics and Its Applications, 171 (3): 453–470, Bibcode:1991PhyA..171..453A, doi:10.1016/0378-4371(91)90295-n.
  19. ^ Parshani, R.; Buldyrev, S. V.; Havlin, S. (2010). "Critical effect of dependency groups on the function of networks". Proceedings of the National Academy of Sciences. 108 (3): 1007–1010. arXiv:1010.4498. Bibcode:2011PNAS..108.1007P. doi:10.1073/pnas.1008404108. ISSN 0027-8424. PMC 3024657. PMID 21191103.
  20. ^ Shao, Jia; Havlin, Shlomo; Stanley, H. Eugene (2009). "Dynamic Opinion Model and Invasion Percolation". Physical Review Letters. 103 (1): 018701. Bibcode:2009PhRvL.103a8701S. doi:10.1103/PhysRevLett.103.018701. ISSN 0031-9007. PMID 19659181.
  21. ^ Berezin, Yehiel; Bashan, Amir; Danziger, Michael M.; Li, Daqing; Havlin, Shlomo (2015). "Localized attacks on spatially embedded networks with dependencies". Scientific Reports. 5 (1): 8934. Bibcode:2015NatSR...5E8934B. doi:10.1038/srep08934. ISSN 2045-2322. PMC 4355725. PMID 25757572.
  22. ^ Shao, S.; Huang, X.; Stanley, H.E.; Havlin, S. (2015). "Percolation of localized attack on complex networks". New J. Phys. 17 (2): 023049. arXiv:1412.3124. Bibcode:2015NJPh...17b3049S. doi:10.1088/1367-2630/17/2/023049. S2CID 7165448.
  23. ^ Shai, S; Kenett, D.Y; Kenett, Y.N; Faust, M; Dobson, S; Havlin, S. (2015). "Critical tipping point distinguishing two types of transitions in modular network structures". Phys. Rev. E. 92 (6): 062805. Bibcode:2015PhRvE..92f2805S. doi:10.1103/PhysRevE.92.062805. PMID 26764742.
  24. ^ Dong, Gaogao; Fan, Jingfang; Shekhtman, Louis M; Shai, Saray; Du, Ruijin; Tian, Lixin; Chen, Xiaosong; Stanley, H Eugene; Havlin, Shlomo (2018). "Resilience of networks with community structure behaves as if under an external field". Proceedings of the National Academy of Sciences. 115 (27): 6911–6915. arXiv:1805.01032. Bibcode:2018PNAS..115.6911D. doi:10.1073/pnas.1801588115. PMC 6142202. PMID 29925594. S2CID 49352915.
  25. ^ B Gross, D Vaknin, SV Buldyrev, S Havlin (2020). "Two transitions in spatial modular networks". New Journal of Physics. 22 (5): 053002. arXiv:2001.11435. doi:10.1088/1367-2630/ab8263. S2CID 210966323.CS1 maint: multiple names: authors list (link)
  26. ^ Li, Daqing; Fu, Bowen; Wang, Yunpeng; Lu, Guangquan; Berezin, Yehiel; Stanley, H. Eugene; Havlin, Shlomo (2015). "Percolation transition in dynamical traffic network with evolving critical bottlenecks". Proceedings of the National Academy of Sciences. 112 (3): 669–672. Bibcode:2015PNAS..112..669L. doi:10.1073/pnas.1419185112. ISSN 0027-8424. PMC 4311803. PMID 25552558.
  27. ^ G Zeng, D Li, S Guo, L Gao, Z Gao, HE Stanley, S Havlin (2019). "Switch between critical percolation modes in city traffic dynamics". Proceedings of the National Academy of Sciences. 116 (1): 23–28. doi:10.1073/pnas.1801545116. PMC 6320510. PMID 30591562.CS1 maint: multiple names: authors list (link)
  28. ^ Majdandzic, Antonio; Podobnik, Boris; Buldyrev, Sergey V.; Kenett, Dror Y.; Havlin, Shlomo; Eugene Stanley, H. (2013). "Spontaneous recovery in dynamical networks". Nature Physics. 10 (1): 34–38. Bibcode:2014NatPh..10...34M. doi:10.1038/nphys2819. ISSN 1745-2473.
  29. ^ Danziger, Michael M.; Shekhtman, Louis M.; Berezin, Yehiel; Havlin, Shlomo (2016). "The effect of spatiality on multiplex networks". EPL (Europhysics Letters). 115 (3): 36002. arXiv:1505.01688. Bibcode:2016EL....11536002D. doi:10.1209/0295-5075/115/36002. ISSN 0295-5075.
  30. ^ Ivan Bonamassa; Bnaya Gross; Michael M Danziger; Shlomo Havlin (2019). "Critical stretching of mean-field regimes in spatial networks". Phys. Rev. Lett. 123 (8): 088301. Bibcode:2019PhRvL.123h8301B. doi:10.1103/PhysRevLett.123.088301. PMC 7219511. PMID 31491213.
  31. ^ Yuan, Xin; Hu, Yanqing; Stanley, H. Eugene; Havlin, Shlomo (2017-03-28). "Eradicating catastrophic collapse in interdependent networks via reinforced nodes". Proceedings of the National Academy of Sciences. 114 (13): 3311–3315. arXiv:1605.04217. Bibcode:2017PNAS..114.3311Y. doi:10.1073/pnas.1621369114. ISSN 0027-8424. PMC 5380073. PMID 28289204.
  32. ^ a b Brunk, Nicholas E.; Twarock, Reidun (2021). "Percolation Theory Reveals Biophysical Properties of Virus-like Particles". ACS Nano. American Chemical Society (ACS). 15 (8): 12988–12995. doi:10.1021/acsnano.1c01882. ISSN 1936-0851. PMC 8397427. PMID 34296852.
  33. ^ Brunk, N. E.; Lee, L. S.; Glazier, J. A.; Butske, W.; Zlotnick, A. (2018). "Molecular Jenga: the percolation phase transition (collapse) in virus capsids". Physical Biology. 15 (5): 056005. Bibcode:2018PhBio..15e6005B. doi:10.1088/1478-3975/aac194. PMC 6004236. PMID 29714713.
  34. ^ Lee, L. S.; Brunk, N.; Haywood, D. G.; Keifer, D.; Pierson, E.; Kondylis, P.; Zlotnick, A. (2017). "A molecular breadboard: Removal and replacement of subunits in a hepatitis B virus capsid". Protein Science. 26 (11): 2170–2180. doi:10.1002/pro.3265. PMC 5654856. PMID 28795465.
  35. ^ Boswell, G. P.; Britton, N. F.; Franks, N. R. (1998-10-22). "Habitat fragmentation, percolation theory and the conservation of a keystone species". Proceedings of the Royal Society of London B: Biological Sciences. 265 (1409): 1921–1925. doi:10.1098/rspb.1998.0521. ISSN 0962-8452. PMC 1689475.
  36. ^ Davis, S.; Trapman, P.; Leirs, H.; Begon, M.; Heesterbeek, J. a. P. (2008-07-31). "The abundance threshold for plague as a critical percolation phenomenon". Nature. 454 (7204): 634–637. Bibcode:2008Natur.454..634D. doi:10.1038/nature07053. hdl:1874/29683. ISSN 1476-4687. PMID 18668107. S2CID 4425203.
  37. ^ Buldyrev, S.V.; Parshani, R.; Paul, G.; Stanley, H.E.; Havlin, S. (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (8932): 1025–8. arXiv:0907.1182. Bibcode:2010Natur.464.1025B. doi:10.1038/nature08932. PMID 20393559. S2CID 1836955.
  38. ^ Gao, J.; Buldyrev, S.V.; Stanley, H.E.; Havlin, S. (2012). "Networks formed from interdependent networks". Nature Physics. 8 (1): 40–48. Bibcode:2012NatPh...8...40G. doi:10.1038/nphys2180.
  39. ^ Bashan, A.; Berezin, Y.; Buldyrev, S.V.; Havlin, S. (2013). "The extreme vulnerability of interdependent spatially embedded networks". Nature Physics. 9 (10): 667. arXiv:1206.2062. Bibcode:2013NatPh...9..667B. doi:10.1038/nphys2727. S2CID 12331944.
  40. ^ Berezin, Y.; Bashan, A.; Danziger, M.M.; Li, D.; Havlin, S. (2015). "Localized attacks on spatially embedded networks with dependencies". Scientific Reports. 5: 8934. Bibcode:2015NatSR...5E8934B. doi:10.1038/srep08934. PMC 4355725. PMID 25757572.
  41. ^ D Vaknin; MM Danziger; S Havlin (2017). "Spreading of localized attacks in spatial multiplex networks". New J. Phys. 19 (7): 073037. arXiv:1704.00267. Bibcode:2017NJPh...19g3037V. doi:10.1088/1367-2630/aa7b09. S2CID 9121930.
  42. ^ Majdandzic, Antonio; Podobnik, Boris; Buldyrev, Sergey V.; Kenett, Dror Y.; Havlin, Shlomo; Eugene Stanley, H. (2013). "Spontaneous recovery in dynamical networks". Nature Physics. 10 (1): 34–38. doi:10.1038/nphys2819.
  43. ^ Majdandzic, Antonio; Braunstein, Lidia A.; Curme, Chester; Vodenska, Irena; Levy-Carciente, Sary; Eugene Stanley, H.; Havlin, Shlomo (2016). "Multiple tipping points and optimal repairing in interacting networks". Nature Communications. 7: 10850. arXiv:1502.00244. Bibcode:2016NatCo...710850M. doi:10.1038/ncomms10850. PMC 4773515. PMID 26926803.
  44. ^ D. Li; B. Fu; Y. Wang; G. Lu; Y. Berezin; H.E. Stanley; S. Havlin (2015). "Percolation transition in dynamical traffic network with evolving critical bottlenecks". Proceedings of the National Academy of Sciences of the United States of America. 112 (3): 669–72. Bibcode:2015PNAS..112..669L. doi:10.1073/pnas.1419185112. PMC 4311803. PMID 25552558.
  45. ^ G Zeng; D Li; S Guo; L Gao; Z Gao; HE Stanley; S Havlin (2019). "Switch between critical percolation modes in city traffic dynamics". 116 (1): 23–28. Cite journal requires |journal= (help)
  46. ^ G Zeng; J Gao; L Shekhtman; S Guo; W Lv; J Wu; H Liu; O Levy; D Li (2020). "Multiple metastable network states in urban traffic". Proceedings of the National Academy of Sciences of the United States of America. 117 (30): 17528–17534. doi:10.1073/pnas.1907493117. PMC 7395445. PMID 32661171.
  47. ^ Limiao Zhang; Guanwen Zeng; Daqing Li; Hai-Jun Huang; H Eugene Stanley; Shlomo Havlin (2019). "Scale-free resilience of real traffic jams". Proceedings of the National Academy of Sciences. 116 (18): 8673–8678. arXiv:1804.11047. Bibcode:2019PNAS..116.8673Z. doi:10.1073/pnas.1814982116. PMC 6500150. PMID 30979803. S2CID 111390178.
  48. ^ Nimrod Serok; Orr Levy; Shlomo Havlin; Efrat Blumenfeld-Lieberthal (2019). "Unveiling the inter-relations between the urban streets network and its dynamic traffic flows: Planning implication". Environment and Planning B: Urban Analytics and City Science. 46 (7): 1362–1376. doi:10.1177/2399808319837982. S2CID 202355697.

Further reading