Format

Send to

Choose Destination
Phys Rev Lett. 2012 Aug 10;109(6):068702. Epub 2012 Aug 10.

Locating the source of diffusion in large-scale networks.

Author information

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

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.

PMID:
23006310
DOI:
10.1103/PhysRevLett.109.068702
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for American Physical Society
Loading ...
Support Center