How do networks shape the spread of disease and gossip?
22 Jul 2015
A new approach to exploring the spread of contagious diseases or the latest celebrity gossip has been tested using London’s street and underground networks. Results from the new approach could help to predict when a contagion will spread through space as a simple wave (as in the Black Death) and when long-range connections, such as air travel, enable it to seemingly jump over long distances and emerge in locations far from an initial outbreak.
A team of Oxford Mathematicians together with colleagues from the University of North Carolina at Chapel Hill and Rutgers University used a set of mathematical rules to encode how a contagion spreads, and they used diverse mathematical and computational tools to study outcomes of these rules.
The researchers explored how disease or gossip might spread through London's transit network. Specifically, they illustrated how the street network overlaid with the London Underground network enables contagions to hop to a distant location. To analyse the behaviour of a contagion, the researchers drew on ideas from ‘topology’, a branch of mathematics used to characterise the structure of complex shapes. By studying the ‘shape’ of the data that results from a contagion, it is possible to distinguish between contagions that take long-distance hops across a network and those that exhibit a local (and slower) wave-like spreading pattern.
This ‘computational topology’ technique has the potential to overcome many of the barriers to extracting useful information from big, ‘noisy’ data sets, such as those gathered during a disease epidemic or from gossip spreading over social media. Computational topology could, for example, yield insights into how fast a new contagion might spread or where it might emerge next.
A report of the research is published in the journal Nature Communications.
"Underlying spatial networks have a big influence over how diseases or information spread, but in our ever-more-connected world, there are numerous ‘shortcuts’ that these can take that makes their spreading patterns difficult to predict," said Professor Mason Porter (an author of the report) of the University of Oxford’s Mathematical Institute. "Our work shows a way to reconcile a wave-like model of spreading, which might approximate what happens at a local level, with behaviour that includes shortcuts to distant locations."
To investigate how networks influence spreading processes, the team ran hundreds of scenarios. They considered various subtly different network structures, which encapsulate which ‘nodes’ (representing, for example, people or locations) are directly reachable from each other through a single short-range or long-range connection.
In some scenarios, nodes can be ‘stubborn’ and resist a new infection or idea; but in others, they are not stubborn at all and quickly succumb to a contagion. The team found that the shape of how a contagion spreads is very sensitive to how inclined nodes are to adopt the contagion. Dr Heather Harrington, another author from the Mathematical Institute in Oxford, said “If nodes are very stubborn, a contagion doesn’t spread much at all; whereas if they are compliant, the contagion quickly crops up all over the network. When the nodes are moderately stubborn—a so called ‘sweet spot’—a contagion tends to spread gradually as a wave."
Professor Porter said: "In other situations, when different nodes have different levels of stubbornness, and if we otherwise make the model more complicated, we still observe both wave-like and shortcut ‘hopping’ behaviour, although naturally the results are messier."
By varying the location of the initial outbreak on a given network and tracking exactly who gets infected at what time (and stacking these layers of information on top of one another), the researchers constructed a mathematical object that they call a ‘contagion map’.
Using methods from computational topology to examine the shape of the data encompassed by the contagion map, the researchers looked for ‘holes’ in the data. "You can think of it like looking for the hole in a doughnut shape that enables us to distinguish it from a sphere," said Professor Porter. In simple scenarios, the approach can distinguish between a ‘real’ hole – which could represent where infections tend not to spread over shortcuts between distant locales – and a ‘false’ hole that arises from noise in the data (such that long-range spread could still be common). As the deluge of data gets ever deeper, developing tools that can distinguish genuine features from noise in large, intricate data sets is becoming increasingly important.
Professor Porter said: "Our work illustrates that these topological methods could be useful in a range of different scenarios. It’s a good example of how pure mathematics and applied mathematics are increasingly working together."
In addition to Porter and Harrington, the research team included postgraduate student Florian Klimm from Oxford’s Mathematical Institute, Dr Dane Taylor and Prof. Peter Mucha from University of North Carolina at Chapell Hill, and Dr Miroslav Kramár and Prof. Konstantin Mischaikow from Rutgers University. Taylor and Klimm are joint lead authors of the study.
This article was first published on the website of the Mathematical Institute, University of Oxford, on 22 July 2015.