# 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.

# 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.

# Graph Drawing 2013

0xDE has posted a brief summary report on the Graph Drawing 2013 conference, after previously posting some preprints. Another report on the same conference has also been blogged by André Schulz. Those who draw networks for a living (or for fun!) should take a look.

# Random networks

I’m currently working on a paper about, among other things, random networks. Here is a random network with 120 nodes and 3,600 links. It’s fascinating how much predictable regularity there can be to the process of randomly adding links to a network:

# 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:

# 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.

# Blogroll: 0xDE

0xDE, one of the blogs I follow, has been posting a day-by-day series of posts on the Symposium on Computational Geometry at the Pontifical Catholic University of Rio de Janeiro, Brazil. Fascinating stuff! The photo below of the city is by Mario Roberto Durán Ortiz.

# Cubic symmetric graphs again

Continuing the theme of the Foster Census of cubic symmetric graphs (networks) from my last post, here is the graph F96B from that census (click on the picture for a larger image). This beautifully symmetrical graph has 96 nodes (all equivalent) and 144 edges (also all equivalent). The image does not do justice to the symmetry of this graph.

Graph F96B is bipartite: the two classes of node are coloured red and blue. It has diameter 7 and girth 8. One of the 8-rings within the graph is highlighted in orange. The graph can be expressed in LCF notation as [−45, −33, −15, 45, −39, −21, −45, 39, 21, 45, −15, 15, −45, 39, −39, 45, 33, 27, −45, 15, −27, 45, −39, 39]4.

# Cubic Symmetric Graphs

The so-called “Foster Census” of cubic symmetric graphs (networks) has been very ably continued by New Zealand mathematician Professor Marston Conder. In August last year, he gave us a complete list of cubic symmetric graphs on up to 10,000 vertices. The chart above summarises that list, noting the diameter, girth, and order (number of vertices) of each graph. Each coloured dot is a graph. Seven of the better-known graphs are labelled, and the Tutte–Coxeter graph is illustrated (click on the chart for a larger image).