The Erdös-Rényi random graph I

You could argue that random network theory started with one particular model, first studied by famous mathematicians Paul Erdös and Alfred Rényi (1959). (Erdös, in particular, was a hugely important and endlessly fascinating figure, about whom we will surely have more to say in future posts.) The model is now known simply as the Erdös-Rényi Random Graph.
It’s a very simple abstract mathematical model for making graphs. A graph is just a mathematical model for a network that works as follows:

Take any number of points. Let’s call this number n, and let’s call the points vertices. A graph is just a collection of vertices that are connected in pairs. We call such a connection an edge (you can think of an edge as a line connecting two vertices). So if we would start with 9 vertices and connect each pair of them by an edge we would create the following graph:

The name of the graph with n vertices where each vertex is connected with each other vertex is appropriately named the complete graph.

The Erdös-Rényi Random Graph model is to start with a complete graph, and randomly delete edges from it. To make these random deletions, we need some kind of method. For each possible edge we want to say randomly either “yes, you are in” or “no, you are out”. If you want to produce a random “yes-no” kind of answer, then one way of doing that is to flip a coin. We could agree that if the coin comes up heads, then the answer is "yes", and if it comes up tails, the answer is "no". Now we can flip our coin once for each possible edge, and in that way determine which edges we keep, and which ones we delete. But of course a coin is kind of limited, since the conventional wisdom is that a coin comes up heads roughly about as often as it comes up tails. Which means that we would typically expect to see graphs with about half as many edges as the complete graph. So what if we want more or fewer edges? Well, since the coin is totally fictitious, at this point we could just imagine a coin that is does not produce a 1:1 heads-tails ratio, but rather a R : Q ratio, for some arbitrarily chosen numbers R and Q. If we write p for this ratio (i.e., p = \frac{R}{R+Q}), then we call this a p-coin (so if R=3 and Q=7, then p=0.3, corresponding to a coin that comes up heads 30% of the time).
Below you find a demo that allows you to create Erdös-Rényi Random Graph with a given number of vertices (points) and for a given probability of keeping an edge ( the ratio R/(R+Q)):

The Erdös-Rényi Random Graph sure looks nice, but why is this model such an endless source of fascination for mathematicians? Proceed to Part II of this series to find out.

Comments are closed