Percolation theory
Network science  

Network types  
Graphs  


Models  


 
In statistical physics and mathematics, percolation theory describes the behaviour of connected clusters in a random graph. The applications of percolation theory to materials science and other domains are discussed in the article percolation.
Contents
Introduction[edit]
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 threedimensional 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),^{[1]} 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).
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 p_{c}) 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.
For most infinite lattice graphs, p_{c} cannot be calculated exactly, though in some cases p_{c} there is an exact value. For example:
 for the square lattice ℤ^{2} in two dimensions, p_{c} = 1/2 for bond percolation, a fact which was an open question for more than 20 years and was finally resolved by Harry Kesten in the early 1980s,^{[2]} see Kesten (1982).
 A limit case for lattices in many dimensions^{[clarification needed]} is given by the Bethe lattice, whose threshold is at p_{c} = 1/z − 1 for a coordination number z. In other words: for the regular tree of degree , is equal to .
Universality[edit]
The universality principle states that the numerical value of p_{c} is determined by the local structure of the graph, whereas the kind of behavior of clusters that is observed below, at, and above p_{c} is independent of the local structure, and therefore, in some sense these behaviors are more natural to consider than p_{c} itself. This universality also means that for a given dimension, the various critical exponents, the fractal dimension of the clusters at p_{c} 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.^{[3]}^{[4]}
Phases[edit]
Subcritical and supercritical[edit]
The main fact in the subcritical phase is "exponential decay". That is, when p < p_{c}, 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 p_{c} = 1/2.^{[5]}
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 twodimensional slab ℤ^{2} × [0, N]^{d − 2}. This was proved by Grimmett & Marstrand (1990).^{[6]}
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 p_{c} < 1/2, and there is coexistence of infinite open and closed clusters for p between p_{c} and 1 − p_{c}.
Critical[edit]
The model has a singularity at the critical point p = p_{c} believed to be of powerlaw type. 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. Most of these predictions are conjectural except when the number d of dimensions satisfies either d = 2 or d ≥ 19. They include:
 There are no infinite clusters (open or closed)
 The probability that there is an open path from some fixed point (say the origin) to a distance of r decreases polynomially, i.e. is on the order of r^{α} for some α
 α does not depend on the particular lattice chosen, or on other local parameters. It depends only on the dimension d (this is an instance of the universality principle).
 α_{d} decreases from d = 2 until d = 6 and then stays fixed.
 α_{2} = −5/48
 α_{6} = −1.
 The shape of a large cluster in two dimensions is conformally invariant.
See Grimmett (1999).^{[7]} 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).^{[8]}
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 twodimensional 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)^{[9]} in the special case of site percolation on the triangular lattice.
Different models[edit]
 Directed percolation that models the effect of gravitational forces acting on the liquid was also introduced in Broadbent & Hammersley (1957),^{[1]} and has connections with the contact process.
 The first model studied was Bernoulli percolation. In this model all bonds are independent. This model is called bond percolation by physicists.
 A generalization next was introduced as the Fortuin–Kasteleyn random cluster model, which has many connections with the Ising model and other Potts models.
 Bernoulli (bond) percolation on complete graphs is an example of a random graph. The critical probability is p = 1/N, where N is the number of vertices (sites) of the graph.
 Bootstrap percolation removes active cells from clusters when they have too few active neighbors, and looks at the connectivity of the remaining cells.^{[10]}
 First passage percolation.
 Invasion percolation.
 Percolation with dependency links was introduced by Parshani et al.^{[11]}
 Percolation and the opinion Model.^{[12]}
 Percolation under localized attack was introduced by Berezin et al.^{[13]} See also Shao et al.^{[14]}
 Percolation of traffic in cities was introduced by Daqing Li et al^{[15]}
 Introducing recovery of nodes and links in percolation.^{[16]}
 Percolation in 2d with a characteristic link length.^{[17]}
 A generalized percolation model that introduces a fraction of reinforced nodes in a network that can function and support their neighborhood was introduced by Yanqing Hu et al.^{[18]}
Applications[edit]
In biology, biomedicine, and physical virology[edit]
Percolation theory has been used to successfully predict the fragmentation of biological virus shells (capsids), with the percolation threshold of Hepatitis B Virus capsid predicted and detected experimentally. 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 singleparticle techniques. This is a molecular analog to the common board game "Jenga," and has relevance to virus disassembly. ^{[19]} ^{[20]}
Percolation theory has been applied to studies of how environment fragmentation impacts animal habitats^{[21]} and models of how the plague bacterium Yersinia pestis spreads.^{[22]}
See also[edit]
References[edit]
 ^ ^{a} ^{b} Broadbent, S. R.; Hammersley, J. M. (2008). "Percolation processes". Mathematical Proceedings of the Cambridge Philosophical Society. 53 (3): 629. Bibcode:1957PCPS...53..629B. doi:10.1017/S0305004100032680. ISSN 03050041.
 ^ 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 10429832.
 ^ Hassan, M. K.; Rahman, M. M. (2015). "Percolation on a multifractal scalefree 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.
 ^ Hassan, M. K.; Rahman, M. M. (2016). "Universality class of site and bond percolation on multimultifractal scalefree planar stochastic lattice". Phys. Rev. E. 94 (4): 042109. arXiv:1604.08699. Bibcode:2016PhRvE..94d2109H. doi:10.1103/PhysRevE.94.042109. PMID 27841467.
 ^ Kesten, Harry (1982). Percolation Theory for Mathematicians. doi:10.1007/9781489927309. ISBN 9780817631079.
 ^ Grimmett, G. R.; Marstrand, J. M. (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 13645021.
 ^ Grimmett, Geoffrey (1999). Percolation. Grundlehren der mathematischen Wissenschaften. 321. doi:10.1007/9783662039816. ISBN 9783642084423. ISSN 00727830.
 ^ Hara, Takashi; Slade, Gordon (1990). "Meanfield critical behaviour for percolation in high dimensions". Communications in Mathematical Physics. 128 (2): 333–391. Bibcode:1990CMaPh.128..333H. doi:10.1007/BF02108785. ISSN 00103616.
 ^ Smirnov, Stanislav (2001). "Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limits". Comptes Rendus de l'Académie des Sciences, Série I. 333 (3): 239–244. arXiv:0909.4499. Bibcode:2001CRASM.333..239S. CiteSeerX 10.1.1.246.2739. doi:10.1016/S07644442(01)019917. ISSN 07644442.
 ^ Adler, Joan (1991), "Bootstrap percolation", Physica A: Statistical Mechanics and its Applications, 171 (3): 453–470, Bibcode:1991PhyA..171..453A, doi:10.1016/03784371(91)90295n.
 ^ 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 00278424. PMC 3024657. PMID 21191103.
 ^ 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 00319007. PMID 19659181.
 ^ 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 20452322. PMC 4355725. PMID 25757572.
 ^ 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. doi:10.1088/13672630/17/2/023049.
 ^ 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 00278424. PMC 4311803. PMID 25552558.
 ^ 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 17452473.
 ^ 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/02955075/115/36002. ISSN 02955075.
 ^ Yuan, Xin; Hu, Yanqing; Stanley, H. Eugene; Havlin, Shlomo (20170328). "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 00278424. PMC 5380073. PMID 28289204.
 ^ 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.
 ^ 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), 21702180.
 ^ Boswell, G. P.; Britton, N. F.; Franks, N. R. (19981022). "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 09628452. PMC 1689475.
 ^ Davis, S.; Trapman, P.; Leirs, H.; Begon, M.; Heesterbeek, J. a. P. (20080731). "The abundance threshold for plague as a critical percolation phenomenon". Nature. 454 (7204): 634–637. doi:10.1038/nature07053. hdl:1874/29683. ISSN 14764687. PMID 18668107.
Further reading[edit]
 Aizenman, Michael; Barsky, David (1987), "Sharpness of the phase transition in percolation models", Communications in Mathematical Physics, 108 (3): 489–526, Bibcode:1987CMaPh.108..489A, doi:10.1007/BF01212322
 Bollobás, Béla; Riordan, Oliver (2006), Percolation, Cambridge University Press, ISBN 9780521872324
 Broadbent, Simon; Hammersley, John (1957), "Percolation processes I. Crystals and mazes", Proceedings of the Cambridge Philosophical Society, 53 (3): 629–641, Bibcode:1957PCPS...53..629B, doi:10.1017/S0305004100032680
 Bunde A. and Havlin S. (1996), Fractals and Disordered Systems, Springer
 Cohen R. and Havlin S. (2010), Complex Networks: Structure, Robustness and Function, Cambridge University Press
 Grimmett, Geoffrey (1999), Percolation, Springer
 Grimmett, Geoffrey; Marstrand, John (1990), "The supercritical phase of percolation is well behaved", Proceedings of the Royal Society A, 430 (1879): 439–457, Bibcode:1990RSPSA.430..439G, doi:10.1098/rspa.1990.0100
 Hara, Takashi; Slade, Gordon (1990), "Meanfield critical behaviour for percolation in high dimensions", Communications in Mathematical Physics, 128 (2): 333–391, Bibcode:1990CMaPh.128..333H, doi:10.1007/BF02108785
 Kesten, Harry (1982), Percolation theory for mathematicians, Birkhauser
 Menshikov, Mikhail (1986), "Coincidence of critical points in percolation problems", Soviet Mathematics  Doklady, 33: 856–859
 Smirnov, Stanislav (2001), "Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limits", Comptes Rendus de l'Académie des Sciences, 333 (3): 239–244, arXiv:0909.4499, Bibcode:2001CRASM.333..239S, CiteSeerX 10.1.1.246.2739, doi:10.1016/S07644442(01)019917
 Stauffer, Dietrich; Aharony, Anthony (1994), Introduction to Percolation Theory (2nd ed.), CRC Press, ISBN 9780748402533
External links[edit]
 PercoVIS: a Mac OS X program to visualize percolation on networks in real time
 Interactive Percolation
 Kesten, Harry (May 2006), "What Is ... Percolation?" (PDF), Notices of the American Mathematical Society, 53 (5): 572–573, ISSN 10889477
 Austin, David (July 2008), Percolation: Slipping through the Cracks, American Mathematical Society
 Nanohub online course on Percolation Theory
 Introduction to Percolation Theory: short course by Shlomo Havlin