Random Graph

a graph that is generated by some random process.
The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.
A random graph is obtained by starting with a set of n vertices and adding edges between them at random.


G(n,p)  : in which every possible edge occurs independently with probability p (the Edgar Gilbert model). Thus, the expected number of edges is pn(n − 1)/2.

Percolation Theory

For example, we might ask for a given value of n and p what the probability is that G(n, p) is connected. In studying such questions, researchers often concentrate on the asymptotic behavior of random graphs—the values that various probabilities converge to as n grows very large. Percolation theory characterizes the connectedness of random graphs, especially infinitely large ones.

Percolation is related to the robustness of the graph (called also network). Given a random graph of n nodes and an average degree <k>. Next we remove randomly a fraction 1-p of nodes and leave only a fraction p. There exists a critical percolation threshold pc = 1/<k>  below which the network becomes fragmented while above pc a giant connected component exists.


Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom?

Bond Percolation:
Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled mathematically as a three-dimensional network of n × n × n points (or vertices/sites) the connections (or edges/bonds) between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path exists from the top to the bottom?

Site Percolation:
When a site is occupied with probability p or empty (its edges are also removed) with probability 1-p, the problem is called "site percolation".

Detail of a bond percolation on the square lattice in two dimensions with percolation probability p = 0.51

As is quite typical, it is actually easier to examine infinite networks than just large ones. In this case the corresponding question is: does an infinite open cluster exist? That is, is there a path of connected points of infinite length "through" the network? By Kolmogorov's zero-one law, for any given p, the probability that an infinite cluster exists is either zero or one. Since this probability is an increasing function of p (proof via coupling argument), there must be a critical p (denoted by pc) below which the probability is always 0 and above which the probability is always 1. In practice, this criticality is very easy to observe. Even for n as small as 100, the probability of an open path from the top to the bottom increases sharply from very close to zero to very close to one in a short span of values of p.

Random graphs are widely used in the probabilistic method, where one tries to prove the existence of graphs with certain properties. The existence of a property on a random graph can often imply, via the famous Szemerédi regularity lemma, the existence of that property on almost all graphs.

Random Tree