What is the meaning of the term "edge percolation"?
Context is graph theory, specifically, random graphs. In general, what does "percolation" mean in the context of random graphs?
Thanks.
What is the meaning of the term "edge percolation"?
Context is graph theory, specifically, random graphs. In general, what does "percolation" mean in the context of random graphs?
Thanks.
Edge percolation (often called bond percolation) refers to edges being randomly removed from a graph (a lattice): typically, each edge has probability $p\in (0,1)$ of surviving, independent of other edges. In line with original meaning of percolation (fluid transit), one may think of the removed edges as closed, i.e., made impermeable. How far the fluid may spread in the graph depends on the size of connected component. One often sees a phase transition: emergence of a unique giant component when $p$ exceeds some value $p_0$.
Some references: Wikipedia page, Pierre Nolin's lecture slides.