Complex networks and collective behavior in nature

The giant island: Part 2

There are two closely related variants of the Erdős–Rényi random graph model.

In the $G(N,M)$ model, a graph is chosen uniformly at random from the collection of all graphs which have N nodes and M edges. For example, in the G(3, 2) model, each of the three possible graphs on three vertices and two edges are included with probability 1/3.

In the $G(N,p)$ model, a graph is thought to be constructed by connecting nodes randomly. Each edge is included in the graph with probability $p$ , with the presence or absence of any two distinct edges in the graph being independent.

Both models are connected through the following relation, The expected number of edges in $G(N,p)$ is $\tbinom{N}{2}p$ , and by the law of large numbers any graph in $G(N,p)$ will almost surely have approximately this many edges (provided the expected number of edges tends to infinity). Therefore a rough heuristic rule is that if $pN^{2}$ tends to infinity, then $G(N,p)$ should behave similarly to $G(N,M)$ with $M=\tbinom{N}{2}p$ as $N$ increases.

Animation:The phase transition

Let's look at how the graph evolve in $p$ , the probability of an edge between two nodes. Effectively, as we keep adding edges randomly to a graph, what happens? From theory, we expect to see a giant component with approximately log(N) vertices emerge when p is near 1/(N-1). Then, we expect the graph to become completely connected when p is close to log(n)/n.

In a 1960 paper, Erdős and Rényi described the behavior of $G(N,p)$ very precisely for various values of $p$ . Their results included that:

If $Np<1$ , then a graph in $G(N,p)$ will almost surely have no connected components of size larger than O(logN)
If $Np=1$ , then a graph in $G(N,p)$ will almost surely have largest component whose size is of order $n^{\frac{2}{3}}$

The phase transition in the $G(N,p)$ model occurs when Np = 1, In the following example we show a graph generated by using 100 vertices, in the top of the plot you can see the value of $p$ . At the begining the lines connect small islands, a different color was selected to represent the biggest island in the system, as the animation goes further, you will see that almost all the nodes are connected through the same color lines, meaning that they belong to the giant island. The animation pauses briefly at the moment where a giant threshold is reached, in this case p = 0.0101.

To create this video MatLab code was used, following the instructions posted by David Gleich with slightly modifications.

Back