Percolation Theory

Introduction

Classical percolation theory studies site and bond percolations. In a graph model, the site is represented as the vertex while the bond is represented as the edge. In a grid structure, each cell is a site and the bond is edge between cells. By assigning each site/bond with a probability p of being occupied/open, we are interested whether we could find a path from the leftmost to the rightmost or from the top to the bottom. We have created several 3-D visualizations of percolation models. Our project also focuses on the bootstrap percolation process. Bootstrap percolation is a model for disease infection: In a grid, if the site is initially occupied independently with a random probability p, recursively other sites will be infected if the number of infected neighbors is not less than a predefined threshold r. We are interested in whether the whole grid will be infected eventually. We specifically focus on the 2-D grid. 1-neighbor and 4-neighbor bootstrap percolation processes are relatively simple. 2-neighbor bootstrap percolation has been extensively studied while the critical probability for 3-neighbor bootstrap percolation process is still open.


Site percolation

Imagine ļ¬lling a box with glass and metal balls placed randomly. A natural question is: Does the entire box act like a conductor or an insulator? In other words, is there a spanning cluster, a group of metal balls touching each other that reaches from one side of the box to the other? Consider a random network where vertices are metal balls with probability p and glass balls with probability of (1-p). Edges in the network correspond to where balls touch each other.


Visualization from a mathematica .cdf file


Site percolation with p = 0.25

Site percolation with p = 0.35

Site percolation with p = 0.65

Bond percolation

Imagine pouring a liquid on top of a block of porous material and letting the liquid trickle down. Will the liquid be able to travel through an open path from top to bottom? Consider a random network in which an edge is open, and therefore blocking liquid with probability (1-p).


Visualization from a C++ implementation.


Bond percolation with p = 0.30

Bond percolation with p = 0.45

Bond percolation with p = 0.65

Two-Neighbor Bootstrap percolation

Bootstrap percolation is somehow similar to site percolation. But compared with site percolation, bootstrap percolation is more "dynamic". It has a k-dimensional grids(in the following example k=2) and each grid has a independent probability to be infected as the initial configuration. A site will be infected if it has at least r neighbors being infected in each step(in the example r=2). We are interested in the question that if the whole grdis will percolate and what the critical probability is.


Visualization from a mathematica .cdf file.


Step 1. Initial configuration. Probability = 0.1.

Step 2. red Xs are about to be infected.

Step 3 Grids are infected


A Demonstration from Wolfram Alpha