Percolation theory
Keywords: | math, statistical physics, graphs, connected components, network science |
Date: |
- 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 probability1 - 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
- particularly when
- "therefore, for a given
- edges will independently allow liquid between two given vertices with probability
- 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 |