Percolation theory
Part of a series on | ||||
Network science | ||||
---|---|---|---|---|
Network types | ||||
|
||||
Graphs | ||||
|
||||
Models | ||||
|
||||
| ||||
In
Introduction
A representative question (and the
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
History
The Flory–Stockmayer theory was the first theory investigating percolation processes.[2]
The history of the percolation model as we know it has its root in the coal industry. Since the industrial revolution, the economical importance of this source of energy fostered many scientific studies to understand its composition and optimize its use. During the 30' and 40'[when?], the qualitative analysis by organic chemistry left more and more room to more quantitative studies. [3]
In this context, the British Coal Utilisation Research Association (BCURA) was created in 1938. It is a research association funded by the coal mines owners. In 1942, Rosalind Franklin, who then recently graduated in chemistry from the university of Cambridge, joined the BCURA. She started research on the density and porosity of coal. During the Second World War, coal was an important strategic resource. It was used as a source of energy, but also was the main constituent of gas masks.
Coal is a porous medium. To measure its 'real' density, one was to sink it in a liquid or a gas whose molecules are small enough to fill its microscopic pores. While trying to measure the density of coal using several gases (helium, methanol, hexane, benzene), and as she found different values depending on the gas used, Rosalind Franklin showed that the pores of coal are made of microstructures of various lengths that act as a microscopic sieve to discriminate the gases. She also discovered that the size of these structures depends on the temperature of carbonation during the coal production. With this research, she obtained a PhD degree and left the BCURA in 1946. [4]
In the mid fifties, Simon Broadbent worked in the BCURA as a statistician. Among other interests, he studied the use of coal in gas masks. One question is to understand how a fluid can diffuse in the coal pores, modeled as a random maze of open or closed tunnels. In 1954, during a symposium on Monte Carlo methods, he asks questions to John Hammersley on the use of numerical methods to analyze this model. [5]
Broadbent and Hammersley introduced in their article of 1957 a mathematical model to model this phenomenon, that is percolation.
Computation of the critical parameter
For most infinite lattice graphs, pc cannot be calculated exactly, though in some cases pc there is an exact value. For example:
- for the square lattice ℤ2 in two dimensions, pc = 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,[6] see Kesten (1982). For site percolation on the square lattice, the value of pc is not known from analytic derivation but only via simulations of large lattices which provide the estimate pc = 0.59274621 ± 0.00000013.[7]
- A limit case for lattices in high dimensions is given by the Bethe lattice, whose threshold is at pc = 1/z − 1 for a coordination number z. In other words: for the regular tree of degree , is equal to .
- For a random tree-like network without degree-degree correlation, it can be shown that such network can have a giant component, and the percolation threshold (transmission probability) is given by , where is the generating function corresponding to the excess degree distribution. So, for random Erdős–Rényi networks of average degree , pc = 1/⟨k⟩.[8][9][10]
- In networks with low clustering, , the critical point gets scaled by such that:
This indicates that for a given degree distribution, the clustering leads to a larger percolation threshold, mainly because for a fixed number of links, the clustering structure reinforces the core of the network with the price of diluting the global connections. For networks with high clustering, strong clustering could induce the core–periphery structure, in which the core and periphery might percolate at different critical points, and the above approximate treatment is not applicable.[12]
Universality
The
Phases
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.[15]
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).[16]
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.
Criticality
Percolation has a
- 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).[17] 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).[18]
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
Different models
- 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 was next 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.[20]
- First passage percolation.
- Invasion percolation.
Applications
In biology, biochemistry, and physical virology
Percolation theory has been used to successfully predict the fragmentation of biological virus shells (capsids),[21][22] with the fragmentation threshold of Hepatitis B virus capsid predicted and detected experimentally.[23] 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.[21]
In ecology
Percolation theory has been applied to studies of how environment fragmentation impacts animal habitats[24] and models of how the plague bacterium Yersinia pestis spreads.[25]
See also
- Continuum percolation theory
- Critical exponent – Parameter describing physics near critical points
- Directed percolation – Physical models of filtering under forces such as gravity
- Erdős–Rényi model – Two closely related models for generating random graphs
- Fractal – Infinitely detailed mathematical structure
- Giant component – Large connected component of a random graph
- Graph theory – Area of discrete mathematics
- Interdependent networks – Subfield of network science
- Invasion percolation
- Kahn–Kalai conjecture – Mathematical proposition
- Network theory – Study of graphs as a representation of relations between discrete objects
- Network science – Academic field
- Percolation threshold – Threshold of percolation theory models
- Percolation critical exponents – Mathematical parameter in percolation theory
- Scale-free network – Network whose degree distribution follows a power law
- Shortest path problem – Computational problem of graph theory
- Bunkbed conjecture – Conjecture in probabilistic combinatorics
References
- ^ S2CID 84176793.
- ISBN 978-0-203-22153-2. Archivedfrom the original on 2023-02-04. Retrieved 2020-10-27.
- .
- ^ The rosalind franklin papers - the holes in coal: Research at BCURA and in Paris, 1942-1951. https://profiles.nlm.nih.gov/spotlight/kr/feature/coal Archived 2022-07-07 at the Wayback Machine. Accessed: 2022-01-17.
- .
- S2CID 7342807.
- S2CID 747665.
- ^ Erdős, P. & Rényi, A. (1959). "On random graphs I.". Publ. Math. (6): 290–297.
- ^ Erdős, P. & Rényi, A. (1960). "The evolution of random graphs". Publ. Math. Inst. Hung. Acad. Sci. (5): 17–61.
- ^ Bolloba's, B. (1985). "Random Graphs". Academic.
- from the original on 2023-02-04. Retrieved 2022-02-24.
- S2CID 231719831.
- S2CID 119112286.
- S2CID 22593028.
- ISBN 978-0-8176-3107-9.
- S2CID 122534964.
- from the original on 2020-02-23. Retrieved 2009-04-18.
- from the original on 2021-02-24. Retrieved 2022-10-30.
- ISSN 0764-4442.
- .
- ^ PMID 34296852.
- PMID 29714713.
- PMID 28795465.
- PMC 1689475.
- S2CID 4425203.
- S2CID 35592821
- Menshikov, Mikhail(1986), "Coincidence of critical points in percolation problems", Soviet Mathematics - Doklady, 33: 856–859
Further reading
- Austin, David (July 2008). "Percolation: Slipping through the Cracks". American Mathematical Society. Archived from the original on 2009-11-13. Retrieved 2021-04-28.
- ISBN 978-0521872324. Archivedfrom the original on 2015-09-23. Retrieved 2008-06-26.
- Kesten, Harry (May 2006). "What Is ... Percolation?" (PDF). Notices of the American Mathematical Society. 53 (5): 572–573. (PDF) from the original on 2021-05-02. Retrieved 2021-04-28.