Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo

 

Unsupported browser: Your browser does not meet modern web standards. See how it scores »

The way information percolates through networks is of ongoing fascination to increasingly diverse groups of people. 

That’s why physicists have developed a new science of networks to better understand what’s going on. The models they have developed can accurately describe how disease spreads through society, how gossip spreads through social networks and how malware spreads over the internet. 

In other words, given the location of the source and the structure of the network, they can accurately predict how information will spread.

However, the reverse task of determining the source of information after it has already spread is much harder. That’s because most interesting networks are so big that it’s impossible to measure the state of every node.

Today, Pedro Pinto and pals at the École Polytechnique Fédérale de Lausanne in Switzerland show that it can be done, even if you have information from only a few nodes. “We show that it is fundamentally possible to estimate the location of the source from measurements collected by sparsely-placed observers,” they say.

The start with a theoretical description of the problem and how it can be solved. They go on to demonstrate the effectiveness their method using data about a cholera outbreak in the KwaZulu-Natal province in South Africa in 2000. This data includes a detailed map of the network of waterways in this area through which the disease would have spread, and the number of cholera victims in various communities in the network. 

“By monitoring only 20% of the communities, we achieve an average error of less than 4 hops between the estimated source and the first infected community”, they say. 

That’s an impressive result.  However, it comes with a number of caveats. One problem is that the method assumes a good understanding of the structure of the network, something that is not always easy to get for large, real-world networks.  

In the case of cholera, for example, the disease spreads downstream through rivers, which can be mapped reasonably accurately. But it also spreads when infected victims move from one geographical location to another and this is much harder to to take into account. 

Another problem is that nodes can have different levels of importance in a network so the choice of the ones used to sample the data is important. However, nobody knows what the optimal choice should be.  

Nevertheless, the new approach should have wide application. The same technique that can spot the first victim in a cholera outbreak should also work with other network-based phenomena such as the spread of a computer virus or news or malicious gossip. 

That’s something that more than few people ought to be interested in.  

Ref: arxiv.org/abs/1208.2534:  Locating the Source of Diffusion in Large-Scale Networks

0 comments about this story. Start the discussion »

Tagged: Web

Reprints and Permissions | Send feedback to the editor

From the Archives

Close

Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me
×

A Place of Inspiration

Understand the technologies that are changing business and driving the new global economy.

September 23-25, 2014
Register »