The Erdös-Rényi graph III

On the preceding pages we have introduced the Erdös-Rényi random graph model and posed the question when is it connected. You could have used the interactive demo to get to know that for \lambda\geq 2 more than half of the points are connected to each other by edges.

Let us put this into context. Each points could be connected to n-1 other points. If we put \lambda=2, so that p=2/n, then the expected number of edges for each node is 2\frac {n-1} n \approx 2. So, on average, each vertex is connected to two other vertices. The remarkable thing is that this is enough to have most vertices to be connected. If you take larger and larger graph size, so that n becomes very large, then you will see that \lambda=1 is already enough to obtain a connected component
of decent size.
This means that actually on average only one edge per vertex suffices for decent connectivity. To give an idea why this is true, let us not only look at the average number of edges per vertex, but rather at their distribution. The number of edges that are connected to a vertex is also called the degree. Below, we see the proportion of vertices with zero edges, with one edge, with two edges, etc.

To use this demonstration on your full screen click here

In the simulation, you can observe that the connected components in the Erdös-Rényi Random Graph are held together by a small number of vertices that have a relatively high degree. Most vertices are only connected by one or two edges to the large connected component. In most real-world network these high degree vertices play a more prominent role than in Erdös-Rényi Random Graph. For this reason, many other random graph models have been invented that have a larger variability in the number of edges per vertex. Keep checking out this site, as we will introduce such models soon!

The Erdös-Rényi Random Graph is one of the most highly investigated network models, and acts as a playground for mathematicians to investigate numerous properties of interest. To give one more example, we will publish an article discussing distances on the Erdös-Rényi Random Graph soon...

Comments are closed