# Researchers develop method to predict source of network diffusion

##### August 22, 2012 by Bob Yirka report

(Phys.org) -- In building network models, researchers have shown it’s possible to show how information moves from a source node to many and sometime all of the nodes in a network using available data and probability calculations. Not so easy is doing the reverse, i.e. finding the source after data has already diffused throughout a network. Building a model that could do so would have innumerable applications, ranging from tracing rumors on Twitter back to the original poster to discovering where an epidemic got its start. Now new research by a team at the École Polytechnique Fédérale de Lausanne in Switzerland has shown that using techniques similar to triangulation methods that can locate an individual phone from cell towers, it’s possible to predict the source in a network using limited data sets. The team, led by Pedro Pinto, has published its findings in the journal Physical Review Letters.

To find the physical location of a single cell phone to within a few city blocks, engineers look at data from just three cell towers within which the phone is located. By noting the time stamp on the incoming data, it’s possible to deduce, or triangulate, the likely position of the phone. Pinto el al used a similar technique to narrow down the source of data in a diffused network.

The idea they say is to look at the arrival times of data to a node, be it a cell tower, a village in Africa experiencing a cholera epidemic or finding the leader of a terrorist network. Nodes in any network can be associated by drawing lines between them. The way to trace back in time then, involves following the lines that are most likely to lead to the source. Of course while that sounds easy, figuring out which lines to follow back most certainly is not, especially when there is limited or missing information, or when a network is so large looking at every node becomes impossible. That’s where the techniques the team developed come in handy. They used arrival times and probabilistic equations to derive maximum likelihood estimations to help them guess which path to take at each node.

It seems to work. They applied their modeling technique to a cholera outbreak that occurred in Africa back in 2000 and achieved an error rate of less than four hops using data from just twenty percent of the communities involved, which is of course quite impressive. Unfortunately their techniques can only be applied under certain pure conditions, i.e. when there’s a single source, when there’s only one choice at each node, etc. but that doesn’t take away from what they’ve accomplished, likely the instigation of a whole new area of network research.

More information: Locating the Source of Diffusion in Large-Scale Networks, Phys. Rev. Lett. 109, 068702 (2012). DOI:10.1103/PhysRevLett.109.068702 (ArXiv preprint)

Abstract
How can we localize the source of diffusion in a complex network? Because of the tremendous size of many real networks—such as the internet or the human social graph—it is usually unfeasible to observe the state of all nodes in a network. We show that it is fundamentally possible to estimate the location of the source from measurements collected by sparsely placed observers. We present a strategy that is optimal for arbitrary trees, achieving maximum probability of correct localization. We describe efficient implementations with complexity O(Nα), where α=1 for arbitrary trees and α=3 for arbitrary graphs. In the context of several case studies, we determine how localization accuracy is affected by various system parameters, including the structure of the network, the density of observers, and the number of observed cascades.

## Related Stories

#### Study discovers link between cell phone usage and relationship strength

July 18, 2011

A project on the dynamics of social networks at the University of Notre Dame’s Interdisciplinary Center for Network Science and Applications (iCeNSA) has found a link between cell phone usage and relationship strength.

#### Researchers to demo and deploy disaster communications system

August 17, 2011

In the aftermath of most disasters – from the terrorist attacks of Sept. 11, 2001, to this year’s earthquake in Japan – communication systems have been overwhelmed, leaving people without phones and Internet ...

#### Removing 'black sheep' could make Internet run more efficiently

February 28, 2012

(PhysOrg.com) -- Whether dealing with Internet traffic or vehicle traffic, congestion can slow everything down. One team of researchers working on improving network transmission efficiency has developed a strategy that identifies ...

#### The elusive capacity of data networks

May 15, 2012

In its early years, information theory — which grew out of a landmark 1948 paper by MIT alumnus and future professor Claude Shannon — was dominated by research on error-correcting codes: How do you encode information ...

#### Mathematicians use network theory to model champion Spanish soccer team's style

July 6, 2012

(Phys.org) -- For years, sports fanatics have turned to statistics to help them gauge the relative strength or weaknesses of different teams, though some have been more amenable to the process than others. Baseball and football, ...

#### Math algorithm tracks crime, rumours, epidemics to source

August 10, 2012

(Phys.org) -- A team of EPFL scientists has developed an algorithm that can identify the source of an epidemic or information circulating within a network, a method that could also be used to help with criminal investigations.

## Recommended for you

#### First global antineutrino emission map highlights Earth's energy budget

September 1, 2015

The neutrino and its antimatter cousin, the antineutrino, are the tiniest subatomic particles known to science. These particles are byproducts of nuclear reactions within stars (including our sun), supernovae, black holes ...

#### ATLAS and CMS experiments shed light on Higgs properties

September 1, 2015

Three years after the announcement of the discovery of a new particle, the so-called Higgs boson, the ATLAS and CMS Collaborations present for the first time combined measurements of many of its properties, at the third annual ...

#### Tiny drops of early universe 'perfect' fluid

September 1, 2015

The Relativistic Heavy Ion Collider (RHIC), a particle collider for nuclear physics research at the U.S. Department of Energy's (DOE) Brookhaven National Laboratory, smashes large nuclei together at close to the speed of ...

#### Quantum computer that 'computes without running' sets efficiency record

August 31, 2015

(Phys.org)—Due to quantum effects, it's possible to build a quantum computer that computes without running—or as the scientists explain, "the result of a computation may be learned without actually running the computer." ...

#### Neural qubits: Quantum cognition based on synaptic nuclear spins

August 27, 2015

(Phys.org)—The pursuit of an understanding of the base machinery of the mind led early researchers to anatomical exhaustion. With neuroscience now in the throes of molecular mayhem and a waning biochemical bliss, physics ...

#### Evidence suggests subatomic particles could defy the standard model

August 27, 2015

The Standard Model of particle physics, which explains most of the known behaviors and interactions of fundamental subatomic particles, has held up remarkably well over several decades. This far-reaching theory does have ...