9.4. Percolation

Percolation is a process in which a fluid flows through a semi-porous material. Examples include oil in rock formations, water in paper, and hydrogen gas in micropores. Percolation models are also used to study systems that are not literally percolation, including epidemics and networks of electrical resistors.

Percolation models are often represented using random graphs like the ones we saw in Section 4.2, but they can also be represented using cellular automatons. In the next few sections we’ll explore a 2-D CA that simulates percolation.

In this model:

Two questions of interest regarding percolation are (1) the probability that a random array contains a percolating cluster, and (2) how that probability depends on q. These questions might remind you of Section 4.4 where we considered the probability that a random Erdős-Rényi graph is connected. We will see several connections between that model and this one.

I define a new class to represent a percolation model:

class Percolation(Cell2D):

    def __init__(self, n, q):
        self.q = q
        self.array = np.random.choice([1, 0], (n, n), p=[q, 1-q])
        self.array[0] = 5

n and m are the number of rows and columns in the CA.

The state of the CA is stored in array, which is initialized using np.random.choice to choose 1 (porous) with probability q, and 0 (non-porous) with probability 1-q.

The state of the top row is set to 5, which represents a wet cell. Using 5, rather than the more obvious 2, makes it possible to use correlate2d to check whether any porous cell has a wet neighbor. Here is the kernel:

kernel = np.array([[0, 1, 0],
                   [1, 0, 1],
                   [0, 1, 0]])

This kernel defines a 4-cell “von Neumann” neighborhood; unlike the Moore neighborhood we saw in Section 8.2, it does not include the diagonals.

This kernel adds up the states of the neighbors. If any of them are wet, the result will exceed 5. Otherwise the maximum result is 4 (if all neighbors happen to be porous).

We can use this logic to write a simple, fast step function:

def step(self):
   a = self.array
   c = correlate2d(a, self.kernel, mode='same')
   self.array[(a==1) & (c>=5)] = 5

This function identifies porous cells, where a==1, that have at least one wet neighbor, where c>=5, and sets their state to 5, which indicates that they are wet.

"Figure 9.1: Sand pile model initial state (left), after 200 steps (middle), and 400 steps (right)."

Figure 9.5: The first three steps of a percolation model with n=10 and p=0.7.

Figure 9.5 shows the first few steps of a percolation model with n=10 and p=0.7. Non-porous cells are white, porous cells are lightly shaded, and wet cells are dark.

"Gif of how liquid interacts with porous and non-porous cells."

Gif of how liquid interacts with porous and non-porous cells.

You have attempted of activities on this page