Random graphs are networks where the links are introduced at random, among a pre-existing set of nodes. Here, the nodes will be the numbers from 1 to N = 20. The theory of random graphs, described in the classic textbook by Béla Bollobás, is quite beautiful.
The theory of random graphs is sometimes introduced as a game involving buttons and string. However, I cannot recommend that – it leads to the most horrible tangled mess. Instead, I suggest using a pair of icosahedral (d20) dice, like this one (such dice can be obtained from games shops, although I must confess to using random.org to do my dice rolls):
The first dice roll gives 2 and 4 (we re-roll any pairs which are doubles, or which have come up before). Each pair of numbers like this represents a random link in the network. We write the numbers 1 to 20 on a piece of paper, and draw a line between 2 and 4:
The second dice roll gives 1 and 12, so we add a link between those two numbers. A common measure of the density of links is the average degree, which is the average number of links per node. In this case, the average degree is the number of links divided by 10 (not by 20, because each link connects two nodes):
We keep repeating this process, and at an average degree of 1, something interesting starts to happen. A giant component begins to emerge – one big cluster containing many nodes (accompanied by smaller clusters and isolated nodes). The giant component is more impressive with a larger number of nodes, of course.
At an average degree of around log(N), taking (natural) logarithms to the base e = 2.7182818284…, enough random links have been introduced that the network becomes connected. We have log(20) = 3.00, but for this particular set of dice rolls, the network becomes connected at an average degree of 2.5. For larger networks, this connectivity threshold becomes quite sharp.
Additional random links reduce the average distance (mean path length) between pairs of nodes. This is the average number of “hops” needed to get from one node to another. Here the average degree is 6, and the average distance is 1.758:
For connected networks with an average degree of d, the average distance will be approximately log(N) / log(d). This function is shown by the red line below (with black dots showing measured values for our set of dice rolls). For large networks, this formula gives quite a small number, and the property of having small average distances is often called the “small world” property.
There is much more to the study of random graphs, of course, but we can see that a simple pair of icosahedral (d20) dice is enough to introduce the basics.