Percolating Ideas

Today I want to write briefly about some of what I have been learning about Percolation Theory. I will try and make this interesting to the layperson, but some of the details require a bit of mathematical maturity. As always, questions are welcome. I won’t spend too much time on the history or significance of the subject, but the Wikipedia article above is a good place to start for that, and I can always provide some good references if you ask.

There are three types of percolation: bond, site, and continuum. I will focus exclusively on bond percolation for this introduction. We are interested in a specific type of ordered graph called a lattice. There are several technical ways to define or think about them, but I will instead just describe one of the simplest examples, the square grid lattice. To define this object, think of all of the integer points in the plane, ${{\mathbb R}^2}$, as nodes, and the four nearest points as edges. This is just cutting up the plane by squares in a natural way.

Percolation theory studies what happens to connected pieces of a lattice, where we have randomly removed pieces of it. To be precise, for every edge ${e \in E}$ we declare this edge to be open with probability ${p}$, and closed otherwise. What one is interested in are the sizes of open clusters or components, where collections of open edges are all connected to one another. A simple example can be seen in the first two pictures. The first image is a lattice of 30 by 30 points, where we have connected edges with probability ${p=0.6}$. The second is the same lattice, but only plotting the largest connected component.

Central to the theory is the idea that there exists a critical probability, ${p_c}$, such that for all ${p < p_c}$, the probability that an open cluster of infinite size exists is ${0}$, and that for all ${p > p_c}$ this probability is ${1}$. That means that there is a critical transition point in the density of edges locally that gives rise to dramatically different global behaviour. The simplest possible example is a lattice in one dimension. In this case, ${p_c=1}$, since any lower bond probability will almost surely terminate a large cluster at some point.

To give a more interesting example of this, consider the next two images. For the square lattice, the critical probability is ${p_c = 0.5}$ for bond percolation (note that this is a highly nontrivial fact). Below are two large lattices (500 by 500 nodes) with bond probabilities ${p=0.49}$ and ${p=0.51}$ respectively.

The lattices appear virtually identical (although quite busy due to the poor graphical resolution). This makes sense as the local structure induced by ${p}$ is very similar. But if we now remove the pieces not connected to the largest cluster, we have a much different picture. These are exactly the same images as above, with just the largest connected components plotted. As a technical note, Tarjan’s algorithm was used to find this largest connected component.

The dramatic difference becomes increasingly pronounced as one increases ${n}$, the number of nodes per side. There are some interesting reasons for this related to renormalization groups, but I will save that discussion for a later date.

Depending on the scientific question one is interested in, there are a variety of functions that can be defined for these lattices. Several interesting asymptotic relationships hold at or near the critical probability ${p_c}$. As an example, let ${n_s(p)}$ denote the concentration of clusters having ${s}$ sites connected. Here, I mean concentration as the number of such clusters normalized by some reference volume. At the critical probability, ${n_s(p_c) \sim s^{-\tau}}$ where ${\tau}$ is a universal constant that depends only on the type of percolation, and the dimension. This notion of universality permeates the theory at or near this critical threshold, and hence much of the numerical and analytical progress in this area has been on studying it. There are results and theories away from criticality, such as Critical Path Analysis, but I won’t discuss that in any detail here.

One interesting mathematical note is that many of these relationships obey power laws, as models for scale invariance. Why might we say that a power law is scale invariant? Consider the function ${f = f_0(\frac{x}{x_0})^{-d}}$ where ${f_0}$ and ${x_0}$ are reference constants, usually chosen to indicate some representative scale. ${d}$ is just an example power law relationship between the variables we are interested in, ${f}$ and ${x}$. The constants here really don’t denote any particular scale, as we can make them whatever we’d like by rescaling ${x}$. This law, whenever it is valid, will always give a notion of how ${f}$ scales with ${x}$. For example, if ${d=2}$, then any doubling of ${x}$ will cause ${f}$ to decrease by a factor of four. Compare this power function with an exponential, e.g. ${f = f_0e^{-x/x_0}}$. Here, the choice of ${x_0}$ immediately gives a notion of the scale of ${f}$. This is one reason why these asymptotic power laws are interesting from the theoretical standpoint.

What motivates this study, besides the interesting mathematics of scale invariance and universality? It turns out that many physical critical phenomena, such as phase transitions or emergent phenomena can be explored using these approaches as models. A very related model from physics is the Ising model, which was developed to understand phase transitions. The original motivation for percolation theory was trying to understand the global behaviour of local geometry on flow in porous material. That is, if I have a pore-filled rock, what fraction of the rock has to be pore space so that it soaks up water when submerged, as opposed to just being surface-wetting?

There are many other approaches to understanding porous media. I will likely write more about that later, but one of the key advantages to this stochastic geometry approach is the ability to infer global properties (e.g. the permeability of a rock) from local properties, such as density of pore networks. This kind of phenomena also exists in biology: in tumour vasculature, nutrient transport on a variety of scales, and some ecological models through heterogeneous landscapes. In all of these cases, understanding the details of the networks of interactions is crucial to inferring behaviour globally. I won’t mention too much of my work in the area just yet, but it is using this kind of percolation model to try and deduce changes in flow parameters, such as permeability, based on bioactive material changes in the local porosity. More to come later!