• Featured in Physics

Locating the Source of Diffusion in Large-Scale Networks

Pedro C. Pinto, Patrick Thiran, and Martin Vetterli
Phys. Rev. Lett. 109, 068702 – Published 10 August 2012
Physics logo See Focus story: Tracking Down an Epidemic’s Source
PDFHTMLExport Citation

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.

  • Figure
  • Figure
  • Figure
  • Received 12 January 2012

DOI:https://doi.org/10.1103/PhysRevLett.109.068702

© 2012 American Physical Society

Focus

Key Image

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

Authors & Affiliations

Pedro C. Pinto, Patrick Thiran, and Martin Vetterli

  • École Polytechnique Fédérale de Lausanne (EPFL), Lausanne CH-1015, Switzerland

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 109, Iss. 6 — 10 August 2012

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×