Some principles of network epidemiology

Lockdowns and “flattening the curve” are very much in the news right now, so I thought it was timely to post about some principles of network epidemiology. The charts below (click to zoom) show the simulated spread of a disease (in a small “toy” population of 2000) subject to certain assumptions. The blue lines show the total number of cases over time (adding up those infected, recovered, and dead). This total number is important because some percentage of the final total will die, and we want to minimise that (if we can). The red lines show the number of current infections over time. This is important because some percentage of the red numbers are in hospital, and the red peak therefore represents peak load on the medical system.

In the top row, we have connections happening at random, with increasing social distancing happening from left to right. Moderate social distancing doesn’t change the fact that almost everybody gets the disease, but it does delay and reduce the peak, thus taking strain off the medical system. Extreme social distancing saves many lives, but only if social distancing is continued for a long time (in real terms, until a vaccine is available, which is almost certainly not sustainable).

In the middle row, we have the same number of contacts happening as in the top row, but most of the contacts are within limited social circles. Such contacts, between family members and close friends, are less serious than contacts with strangers. If Peter is your close friend, and you catch the virus, then there’s a reasonable chance that Peter caught it the same way, and so there’s a reasonable chance that your contact with Peter makes no actual difference. If Peter is a spouse, child, or flatmate, that’s quite a good chance. Contacts with strangers, however, can spread the disease from one social circle to another, and so are far more serious.

In the bottom row, we again have the same total number of contacts happening, but a few “super spreaders” have many more contacts than average (while the majority have slightly less than average, to compensate). This third scenario is significantly worse than the top row – higher, earlier, red peaks, and many deaths even when there is extreme social distancing. Unfortunately, experience has shown that medical personnel, in spite of the fantastic work that they do, have the potential to be serious “super spreaders,” because:

• they have contact with many patients;
• the patients are strangers; and
• the patients are more likely than average to be elderly and/or vulnerable.

This is why personal protective equipment (PPE) for medical personnel is so critically important, as are good testing protocols for medical personnel. Other kinds of “super spreaders” also occur, of course, and it is important to identify them, test them, and provide them PPE (or stop them doing what they’re doing, if it’s non-essential – some jurisdictions with supposedly strict rules are still allowing prostitutes to operate, for example).

Overall, if we look at columns in the picture (all three charts in each column have the same total number of contacts), we see that the kind of contact is just as important as the number of contacts. Isolation regulations in some jurisdictions don’t always recognise that fact, unfortunately.

---

The three men and their sisters

The medieval Propositiones ad Acuendos Juvenes (“Problems to Sharpen the Young”) is attributed to Alcuin of York (735–804), a leading figure in the “Carolingian Renaissance.” He is the middle person in the image above.

Along with the more famous problem of the wolf, the goat, and the cabbage, Propositiones ad Acuendos Juvenes contains the problem of the three men and their sisters. Three men, each accompanied by a sister, wish to cross a river in a boat that holds only two people. To protect each woman’s honour, no woman can be left with another man unless her brother is also present (and if that seems strange, remember that Alcuin was writing more than 1,200 years ago). In Latin, the problem is:

“Tres fratres erant qui singulas sorores habebant, et fluvium transire debebant (erat enim unicuique illorum concupiscientia in sorore proximi sui), qui venientes ad fluvium non invenerunt nisi parvam naviculam, in qua non potuerunt amplius nisi duo ex illis transire. Dicat, qui potest, qualiter fluvium transierunt, ne una quidem earum ex ipsis maculata sit?”

The diagram below (click to zoom) shows the state graph for this problem. The solution is left (per tradition) as an exercise for the reader (but to see Alcuin’s solution, highlight the white text below the diagram).

---

Solution:
Miss A and Mr A cross
Mr A returns (leaving Miss A on the far side)
Miss B and Miss C cross
Miss A returns (leaving Misses B and C on the far side)
Mr B and Mr C cross
Mr B and Miss B return (leaving Miss C and Mr C on the far side)
Mr A and Mr B cross
Miss C returns (leaving 3 men on the far side)
Miss A and Miss C cross
Mr B returns (leaving the A’s and C’s on the far side)
Mr B and Miss B cross

---

Mathematical Meme Madness Month #4

All done using R, of course (showtext and igraph packages).

Spoilers: A001349.

---

ASC 10: Six Degrees of Wikipedia

I’ve been having some fun with Six Degrees of Wikipedia, which finds shortest paths inside the network of links between Wikipedia pages. Here are some connections between ASC teams (of various lengths):

• 3: University of Michigan Solar Car Team → Nichols Arboretum → Appalachia → Appalachian State University
• 3: PrISUm → Atanasoff–Berry computer → Gian-Carlo Rota → University of Bologna
• 3: École de technologie supérieure → Quadcopter → George de Bothezat → Peter the Great St. Petersburg Polytechnic University
• 3: University of Minnesota Solar Vehicle Project → Solar cell → Bell Labs → New Jersey Institute of Technology
• 4: Esteban Solar Car Team → World Solar Challenge → Massachusetts Institute of Technology → Harvard Medical School → Alfaisal University

Teams connect to locations too:

• 2: Western Sydney University Solar Car Project → Outback → Oregon Trail
• 2: Missouri University of Science and Technology → American Solar Challenge → Omaha, Nebraska
• 3: University of Illinois at Urbana–Champaign → Illinois → Idaho → Craters of the Moon National Monument and Preserve
• 4: Bend, Oregon → Volcano → Earth → Midnight sun → Midnight Sun Solar Race Team

And my personal favourites:

• 4: Oregon Trail → Salt → Latin → University of Kentucky → University of Kentucky Solar Car Team
• 5: Western Sydney University Solar Car Project → Adelaide → Formula One → Desiré Wilson → Alan Wilson (motorsport) → Motorsport Park Hastings

---

The Game of Mu Torere

The New Zealand game of mū tōrere is illustrated above with a beautiful handmade wooden board. The game seems to have been developed by the Māori people in response to the European game of draughts (checkers). Play is quite different from draughts, however. The game starts as shown above, with Black to move first. Legal moves involve moving a piece to an adjacent empty space:

• along the periphery (kewai), or
• from the centre (pūtahi) to the periphery, or
• from the periphery to the centre, provided the moved piece is adjacent to an opponent’s piece.

Game play continues forever until a draw is called (by mutual consent) or a player loses by being unable to move. Neither player can force a win, in general, so a loss is always the result of a mistake. For each player there is one “big trap” and four “small traps.” This is the “big trap” (Black wins in 5 moves):

  
The board on the left is the “big trap” for White – Black can force a win by moving as shown, which leaves only one move for White.

  
Again, Black moves as shown, which leaves only one move for White.

  
Now, when Black moves as shown, White cannot move, which means that White loses.

Here is one of the four “small traps” for White. The obvious move by Black results in White losing (but avoiding this does not require looking quite so far ahead as with the “big trap”):

Here (click to zoom) is the complete network of 86 game states for mū tōrere (40 board positions which can occur in both a “Black to move” and a “White to move” form, plus 6 other “lost” board positions). Light-coloured circles indicate White to move, and dark-coloured circles Black to move, with the start position in blue at the top right. Red and pink circles are a guaranteed win for Black, while green circles are a guaranteed win for White. Arrows indicate moves, with coloured arrows being forced moves. The diagram (produced in R) does not fully indicate the symmetry of the network. Many of the cycles are clearly visible, however:

---

Chemical Compounds: the board game!

I have previously mentioned my strong interest in science / technology / engineering / mathematics education and in networks and in board games. This has prompted me to start designing educational games, such as the World Solar Challenge game. Joining the collection is my new Chemical Compounds game, which looks like this:

The online game store (faciliated by the wonderful people at The Game Crafter) has a free download link for the rules, should anyone wish to take a look. I also have a few other educational games there.

---

On fairy tales

“About once every hundred years some wiseacre gets up and tries to banish the fairy tale,” C.S. Lewis wrote in 1952. The wiseacre of our time seems to be Richard Dawkins who, two years ago, told the world that fairy tales could be harmful because they “inculcate a view of the world which includes supernaturalism” (he had said similar things in 2008). In a later clarification, he added that fairy tales could “be wonderful” and that they “are part of childhood, they are stretching the imagination of children” – provided some helpful adult emphasises that “Do frogs turn into princes? No they don’t.”

But many scientists grew up with, and were inspired by, fantasy literature. For example, Jane Goodall tells of growing up with the novel The Story of Doctor Dolittle (as I did!). In fact, many science students and professional scientists avidly read fantasy literature even as adults (as they should). The booksthatmakeyoudumb website lists, among the top 10 novels read at CalTech and MIT, Harry Potter, Dune, and The Lord of the Rings. And Alice in Wonderland was written by a mathematician.

This is a science blog, so I have a strong emphasis on scientific truth, which tells us many important ecological and physiological facts about, for example, frogs. Without science, we’d all still be struggling subsistence farmers. But there is actually more than scientific truth out there.

There is also mathematical truth. Are the links in this frog network all equivalent? Yes, they are – but that is decided by mathematical proof, not by scientific experiment. It is in fact a purely abstract mathematical question – the background picture of the frog is actually irrelevant.

And there is ethical truth. Is it OK to eat frog’s legs? Science does not give us the answer to this (although logic can help us decide if our answer is consistent with our other beliefs), but fantasy literature often helps us to explore such ethical questions. Tolkien’s The Lord of the Rings is one superb example. Would you “snare an orc with a falsehood”? Would you attempt to take the One Ring and “go forth to victory”?

There is metaphorical truth. A frog may, in spite of what Dawkins says, be a handsome prince – there’s more to the universe than can be seen at first glance. Or, as Antoine de Saint-Exupéry put it, “What is essential is invisible to the eye.” Children often learn this important fact from fairy tales.

And there is even religious and philosophical truth. Does the frog-goddess Heqet exist, for example? Does the universe exist? Is there a spoon? The methods of philosophy are different from the methods of science, and some amateur philosophers simply state their beliefs without actually justifying them, but philosophy is actually very important. Science itself is based on certain philosophical beliefs about reality.

---

Ecological networks and the Australian dingo

I’m excited at the publication of a joint paper on network ecology, with a focus on the Australian dingo: “Trophic cascades in 3D: Network analysis reveals how apex predators structure ecosystems” (by Arian D. Wallach, Anthony H. Dekker, Miguel Lurgi, Jose M. Montoya, Damien A. Fordham & Euan G. Ritchie, and appearing in Methods in Ecology and Evolution).

Associated with this publication is an animation I put together for the paper showing how the ecological network changes if the role of the dingo as apex predator is weakened. I’m grateful to my ecologist co-authors at the opportunity to contribute my mathematical skills to such an interesting project.

---

Chromatic polynomials

Network colouring is an fascinating branch of mathematics, originally motivated by the four colour map theorem (first conjectured in 1852, but proved only in 1976). Network colouring has applications to register allocation in computers.

For each network there is a chromatic polynomial which gives the number of ways in which the network can be coloured with x colours (subject to the restriction that directly linked nodes have different colours). For example, this linear network can be coloured in two ways using x = 2 colours:

The corresponding chromatic polynomial is x (x − 1)³, which is plotted below. Zeros at x = 0 and x = 1 indicate that at least 2 colours are required.

For the Petersen network below, the chromatic polynomial is:

x (x − 1) (x − 2) (x⁷ − 12 x⁶ + 67 x⁵ − 230 x⁴ + 529 x³ − 814 x² + 775 x − 352)

This polynomial has zeros at 0, 1, 2, and 2.2051, and is plotted below:

Chromatic polynomials provide an interesting link between elementary and advanced mathematics, as well as an interesting case study of network algorithms.

---

Mathematics in action: “Skin groups”

There are three main (though closely related) branches of mathematics – the study of number, the study of shape, and the study of relationships. An interesting ethnomathematical example of the latter is the “skin group” system of the Lardil people of Mornington Island in Australia.

Lardil children

Similar systems (often with two groups, called moieties) can be found around the world (I first discovered the concept as a child, in the classic young adult science fiction novel Citizen of the Galaxy). Among the Lardil, there are eight groups, each associated with particular totemic creatures or objects:

Skin Group	Name	Totem
1	Burulungi	Lightning
2	Ngariboolungi	Shooting star
3	Bungaringi	Turtle
4	Yugumari	Seagull
5	Gungulla	Grey shark
6	Bulunyi	Crane
7	Bulyarini	Sea turtle
8	Gumerungi	Rock

Membership of a “skin group” implies a complex set of tribal obligations and taboos, but the most significant is that only certain kinds of marriages are permitted. Members of group 1 must marry people from group 2 (and vice versa), and similarly for the pairs 3/4, 5/6, and 7/8. All other marriages are considered to be incestuous.

We can define a mathematical function, the spouse function σ, that maps each person’s “skin group” to the “skin group” that their spouse must have: σ(1) = 2, σ(2) = 1, σ(3) = 4, σ(4) = 3, etc. For each of the eight kinds of valid marriage, there is also a rule for determining the “skin group” of the children:

Father	Mother	Children
1	2	8
2	1	3
3	4	2
4	3	5
5	6	4
6	5	7
7	8	6
8	7	1

We can define two mathematical functions, the father-of function φ and the mother-of function μ, that map the “skin group” of a father or mother to the “skin group” that their children must have: φ(1) = 8, μ(1) = 3, φ(2) = 3, μ(2) = 8, etc.

This is all much clearer when displayed visually. In the diagram, two-part black arrows →→ indicate valid marriages. The arrows run from the “skin group” of the wife to the “skin group” of the husband. Red arrows → run from each marriage arrow to the “skin group” of the children. Together, the arrows form an octagonal prism:

Following a single black arrow and then a red arrow (→→) gives the mother-of function μ, with μ(1) = 3, etc. It can be seen that this function has a four-generation cycle: μ(μ(μ(μ(x)))) = x or, as it is often expressed, μ⁴(x) = x. In other words, each person’s “skin group” is the same as that of their great-great-grandmother in the female line (the maternal grandmother of their maternal grandmother).

Following a single black arrow backwards (from the head end) and then a red arrow (←→) gives the father-of function φ, with φ(1) = 8, etc. It can be seen that this function has a two-generation cycle: φ(φ(x)) = x or, as it is often expressed, φ²(x) = x. In other words, each person’s “skin group” is the same as that of their grandfather in the male line (their paternal grandfather).

The combination of the two cycles makes the Lardil “skin group” system a very effective way of shuffling genes within a small population, thus avoiding inbreeding. It also highlights the fact that mathematics can be found in some surprising places. And there are even more patterns to be found in this example. Among others, σ(x) = φ(μ(x)). Also, μ(φ(μ(x))) = φ(x), which some readers may recognise as indicating a dihedral group.

---