Mathematics in action: Alea jacta est and Random graphs

Having posted about the mathematics of dice, here is a way to use dice to teach a seemingly unrelated concept, that of random graphs (also known as Erdős–Rényi networks).

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.

Advertisements

Paperweights

I find paperweights useful while working, and all the more so if they are appropriate in some way. Here is part of my collection.

On the left is a marble cuboctahedron. Since the edges of this shape form a symmetric graph (all 24 edges are equivalent), it made a nice example while I was working on my 2004 paper “Network Robustness and Graph Topology.” For example, the cuboctahedron is one of the Cayley graphs for the alternating group A4.

The frog on the right, on the other hand, feels right at home with some current work I’m doing on amphibian species distribution modelling.

Curved networks as art

This Dagstuhl workshop included a wonderful art exhibit, titled “Bending Reality: Where arc and science meet.” Exhibits included this image by David Eppstein, and also this one:

There were also several metro maps, including ones based on concentric circles and freeform Béziers, as well as some curved annotations of the world and images of curved relationships, like this poster:

See also this blog post, and my previous post about CIRCOS diagrams.

Network Science: a new journal

From the journals.cambridge.org page: “Network Science is a new journal for a new discipline – one using the network paradigm, focusing on actors and relational linkages, to inform research, methodology, and applications from many fields across the natural, social, engineering and informational sciences. Given growing understanding of the interconnectedness and globalization of the world, network methods are an increasingly recognized way to research aspects of modern society along with the individuals, organizations, and other actors within it.

A very welcome step! Volume 1, issue 01 was April 2013, and is still online.