How quickly things spread

Feb 21, 2012
Time-ordered graph. Credit: Hyoungshick Kim

Understanding the spread of infectious diseases in populations is the key to controlling them. If we were facing a flu pandemic, how could we measure where the greatest spreading risk comes from? This information could help inform decisions on whether to impose travel restrictions or close schools.

Think of the patterns of human contact that can infectious disease; you might be breathed on by a hundred people a day in meetings, on and even in the street. These interactions create a highly dynamic network, in which new nodes (contact points), are added to the graph, some existing ones are removed, and in which edges (the lines that join the nodes) come and go too.

These are difficult concepts to grasp and the spread of diseases is just one of the many examples of visualising how networks rapidly spread into a complex mass of interactions.

Most analyses and models have assumed that networks are static, typically represented in graph form as a number of nodes connected by edges. For example, if a local council were to monitor the flow of traffic through a city, the roads would be modelled as a network and capacities would be assigned to the edges, which represent the number of lanes on the roads. Static network models would apply a network flow equation to determine the maximum traffic between any given pair of points.

Although this model would discover the maximum number of cars that can travel through a city in a single wave – if the cars all leave at the same time and get to any point with no delay – it would not be capable of plotting the time it would take for cars to travel and if cars delayed their departure.

Now, scientists at the University of Cambridge’s Computer Laboratory have taken the understanding of standard graph theory one step further by designing a model that can plot the effects of mobility and interaction with the use of a time-ordered graph.

“We would like to offer our metrics to the research community as a better tool to measure behaviour in dynamic networks,” said lead author Hyoungshick Kim, a PhD student in Professor Ross Anderson’s research group.

The time-ordered reduces the complexity of a dynamic network and applies it to a static network by using directed flows. Directed flows allow for network properties to be extended; such as betweenness, which measures the influence a node has over the spread of information through the network (eg how influential a person is within a social ).

For example, in epidemiology, some possibly infective contacts between individuals are long term (friends, family) but many are fleeting (people in the street or the market place). Their relative importance may vary. The new model can be used to identify places or people that are the most influential for epidemics.

Explore further: Spanish scientists create algorithms to measure sentiment on social networks

add to favorites email to friend print save as pdf

Related Stories

Location determines social network influence, study finds

Aug 29, 2010

A team of researchers led by Dr. Hernan Makse, professor of physics at The City College of New York (CCNY), has shed new light on the way that information and infectious diseases proliferate across complex networks. Writing ...

How to control complex networks

May 12, 2011

At first glance, a diagram of the complex network of genes that regulate cellular metabolism might seem hopelessly complex, and efforts to control such a system futile.

MIT researchers create new Urban Network Analysis toolbox

Sep 06, 2011

MIT researchers have created a new Urban Network Analysis (UNA) toolbox that enables urban designers and planners to describe the spatial patterns of cities using mathematical network analysis methods. Such tools can support ...

Recommended for you

N. Korea suffers another Internet shutdown

49 minutes ago

North Korea suffered an Internet shutdown for at least two hours on Saturday, Chinese state-media and cyber experts said, after Pyongyang blamed Washington for an online blackout earlier this week.

Sony's PlayStation 'gradually coming back'

49 minutes ago

Sony was still struggling Saturday to fully restore its online PlayStation system, three days after the Christmas day hack that also hit Microsoft's Xbox, reporting that services were "gradually coming back."

Chattanooga touts transformation into Gig City

50 minutes ago

A city once infamous for the smoke-belching foundries that blanketed its buildings and streets with a heavy layer of soot is turning to lightning-fast Internet speeds to try to transform itself into a vibrant ...

Uber broke Indian financial rules: central bank chief

52 minutes ago

India's central bank chief lashed out at Uber, already under fire over the alleged rape of a passenger, saying the US taxi-hailing firm violated the country's financial regulations by using an overseas payment ...

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.