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
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.
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.
Decoding Science. One article at a time.