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__ $$bAmerican Physical Society$$c2012$$aCollege Pk
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$$g103925$$aThiran, Patrick
000181841 700__ $$aVetterli, Martin$$g107537$$0240184
000181841 773__ $$j109$$tPhysical Review Letters$$k068702
000181841 8564_ $$uhttps://infoscience.epfl.ch/record/181841/files/PRL.pdf$$zPublisher's version$$s561821$$yPublisher's version
000181841 909C0 $$xU10434$$0252056$$pLCAV
000181841 909C0 $$pLCA3$$xU10431$$0252454
000181841 909CO $$qGLOBAL_SET$$pIC$$particle$$ooai:infoscience.tind.io:181841
000181841 917Z8 $$x206235
000181841 917Z8 $$x206235
000181841 917Z8 $$x148230
000181841 937__ $$aEPFL-ARTICLE-181841
000181841 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000181841 980__ $$aARTICLE