000181841 001__ 181841
000181841 005__ 20190316235509.0
000181841 0247_ $$2doi$$a10.1103/PhysRevLett.109.068702
000181841 022__ $$a0031-9007
000181841 02470 $$2ISI$$a000307381900015
000181841 037__ $$aARTICLE
000181841 245__ $$aLocating the Source of Diffusion in Large-Scale Networks
000181841 269__ $$a2012
000181841 260__ $$aCollege Pk$$bAmerican Physical Society$$c2012
000181841 300__ $$a5
000181841 336__ $$aJournal Articles
000181841 520__ $$aHow 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.
000181841 6531_ $$asource, localization, networks, diffusion, graphs
000181841 700__ $$aPinto, Pedro
000181841 700__ $$0240373$$aThiran, Patrick$$g103925
000181841 700__ $$0240184$$aVetterli, Martin$$g107537
000181841 773__ $$j109$$k068702$$tPhysical Review Letters
000181841 8564_ $$s561821$$uhttps://infoscience.epfl.ch/record/181841/files/PRL.pdf$$yPublisher's version$$zPublisher's version
000181841 909C0 $$0252056$$pLCAV$$xU10434
000181841 909C0 $$0252454$$pLCA3$$xU10431
000181841 909CO $$ooai:infoscience.tind.io:181841$$pIC$$particle$$qGLOBAL_SET
000181841 917Z8 $$x206235
000181841 917Z8 $$x206235
000181841 917Z8 $$x148230
000181841 937__ $$aEPFL-ARTICLE-181841
000181841 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000181841 980__ $$aARTICLE