Locating the Source of Diffusion in Large-Scale Networks
By Pedro C. Pinto, Patrick Thiran, Martin Vetterli. Physical Review Letters, 2012
390 citations recorded by the source corpus.
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.
Subfields: Computer Networks and Communications, Computer Science Applications, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/5ef6f70dec300cc92df58cb0e91c4b01dc00d4b8
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
In Statistical and Nonlinear Physics
Citations in the corpus
- Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols (2019, neutral): “ter of this graph to deduce the node that started the gossip. Another line of work studies the setting in which some nodes are curious sensors that inform a central entity when they receive a message [18]. Gossiping is assumed to happen at random times and the source node is estimated by comparing t”
- Dynamics of information diffusion and its applications on complex networks (2016, background): “Besides CST-basedmethods, there are some other works [18,261,262] addressing the inverse problem of special topics of complex propagation networks.”
- Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems (2016, background): “Taking into account the time delays in the diffusion process enables a straightforward inference of the source in a complex network through enumerating all possible hierarchical trees [275, 276].”