Trace the Source of a Rumour or Epidemic via its Network

By

Home / Trace the Source of a Rumour or Epidemic via its Network
N Factorial from 1 to 5 or 10 image by Mike DeHaan

N Factorial from 1 to 5 or 10. Image by Mike DeHaan

Why are Pinto’s Algorithms So Efficient?

Dr. Pinto and his team proposed more efficient algorithms for tree and graph networks. These algorithms share two important characteristics.

First, researchers only need to examine the details of what happens at a few nodes; perhaps 10% to 30% of all the nodes in the network.

Using our method, we can find the source of all kinds of things circulating in a network just by ‘listening’ to a limited number of members of that network,” explained Dr. Pinto in a news release.

How is it possible to use only a few nodes? By “taking into account the time factor,” according to Dr. Pinto. This second feature means that the algorithm looks for the nearest node that has the earliest message. That should be the vector from which the message was transmitted.

One Current Limitation on this Network Tracing Algorithm

Decoded Science asked Dr. Pinto if the algorithm depends on knowing the whole network configuration before reviewing the events, and he responded, “Yes, the algorithm requires full knowledge of the network. We are working on extending it so that it can deal with an incomplete knowledge of the network.

The Computational Complexity of this Network Tracing Algorithm

How well does the algorithm fare as the number of nodes or connections grows? Dr. Pinto told Decoded Science that, “The algorithm complexity is O(N) for arbitrary trees (ie, graphs without cycles), and O(N^3) for arbitrary graphs (possibly with cycles), where N is the total number of nodes in the network. So in other words, yes, the complexity depends on how nodes are interconnected (tree or graph).

As his paper notes, spanning trees can take exponential complexity. Therefore an algorithm with polynomial complexity of O(N^3) is a significant improvement.

Another Application for this Network Tracing Algorithm

Map of the Nile Basin image by Norman B. Leventhal Map Center at the BPL

The Nile illustrates a tree structure where tributaries join to form a single river: Image by Norman B. Leventhal Map Center at the BPL

Dr. Pinto’s algorithms have been tested against a quite different real-world problem: a cholera epidemic in South Africa’s province of KwaZulu-Natal.

Cholera tends to be transmitted from village to village (“nodes”) along rivers and streams (“edges”). Dr. Pinto’s team mapped the villages as linked by waterways, then reviewed the times when cholera was first reported. Working with a complete map but only the records from 20% of the villages, they were able to determine the first report fairly accurately.

This test came years after the cholera outbreak had occurred, but demonstrated that the technique is practical.

About Dr. Pedro Pinto?

Dr. Pedro Pinto, the lead author, earned his PhD in Electrical Engineering and Computer Science from MIT in 2010.

Dr. Pinto is a researcher in the Audiovisual Communications Laboratory at EPFL (Ecole Polytechnique Fédérale de Lausanne), and has led or contributed to a number of previous articles for various IEEE (Institute of Electrical and Electronics Engineers) journals, primarily on the mathematical underpinnings of communications networks.

Portrait of Pedro Pinto courtesy of Pedro Pinto via e-mail to DeHaan Services

Pedro Pinto, lead author of this study. Image courtesy of Pedro Pinto

The Importance of Dr. Pinto’s Algorithms

The effort of tracing a rumour or an epidemic back to its source depends on how efficiently the path can be traced. Finding medical records or interviewing family members takes a great deal of time and personnel, and time is of the essence when attempting to prevent an epidemic.

Finding the source of a computer virus, or the originator of an e-mail hoax, may require court orders to gain access to each user’s accounts – but this algorithm can eliminate the need for these measures. Again, the fewer “nodes” that need to be investigated, the more quickly the problem can be traced.

Resources

Pedro C. Pinto, Patrick Thiran, and Martin Vetterli. Locating the Source of Diffusion in Large-Scale Networks. (2012). École Polytechnique Fédérale de Lausanne (EPFL). (August 10, 2012). Accessed August 10, 2012.

Weisstein, Eric W. Complexity Theory. (2012). MathWorld-A Wolfram Web Resource. Accessed August 10, 2012.

Leave a Comment