Back to notes

Percolation theory

Keywords: math, statistical physics, graphs, connected components, network science
  • Percolation theory relates to how networks/graphs behave when edges or vertices areremoved from the system
  • Representative question:
    • "given that a liquid is poured onto some porous material, will the liquid be able to make its way from hole to hole and reach the bottom?"
    • often modeled as a 3-dimensional graph of size n x n x n, where edges (bonds) between vertices (sites) allow the liquid to pass through probabilistically
      • edges will independently allow liquid between two given vertices with probability p, or not with probability 1 - p
      • so the likelihood of percolation depends on the "site vacancy probability" p
        • "therefore, for a given p, what is the probability that an open path exists for the liquid?"
          • particularly when n (the dimension of the porous material) is large
  • a system "percolates" if and only if (iff) there is an open path from top to bottom
  • reflected in many real-world systems:
model system vacant site occupied site percolates
electricity material conductor insulated conducts
fluid flow material empty blocked porous
social interaction population person empty communicates