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 , where for arbitrary trees and 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.
- Received 12 January 2012
DOI:https://doi.org/10.1103/PhysRevLett.109.068702
© 2012 American Physical Society
Focus
Tracking Down an Epidemic’s Source
Published 10 August 2012
Researchers find the source of an epidemic using relatively little information. Their technique could also help authorities track down contamination in water systems or locate problems in electrical grids.
See more in Physics