181841
20190316235509.0
doi
10.1103/PhysRevLett.109.068702
0031-9007
ISI
000307381900015
ARTICLE
Locating the Source of Diffusion in Large-Scale Networks
2012
College Pk
American Physical Society
2012
5
Journal Articles
How can we localize the source of diffusion in a complex network? Due to the tremendous size of many real networks---such as the Internet or the human social graph---it is usually infeasible 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^{\alpha}) , where \alpha=1 for arbitrary trees, and \alpha=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.
source, localization, networks, diffusion, graphs
Pinto, Pedro
240373
Thiran, Patrick
103925
240184
Vetterli, Martin
107537
109
068702
Physical Review Letters
561821
http://infoscience.epfl.ch/record/181841/files/PRL.pdf
Publisher's version
Publisher's version
252056
LCAV
U10434
252454
LCA3
U10431
oai:infoscience.tind.io:181841
IC
article
GLOBAL_SET
206235
206235
148230
EPFL-ARTICLE-181841
EPFL
REVIEWED
PUBLISHED
ARTICLE