Locating the Source of Diffusion in Large-Scale Networks
arXiv:1208.2534 · doi:10.1103/PhysRevLett.109.068702
Abstract
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^α), 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.
To appear in Physical Review Letters. Includes pre-print of main paper, and supplementary material
References in corpus (2)
Cited by in corpus (66)
- Epidemic processes in complex networks
- Inferring the origin of an epidemic with a dynamic message-passing algorithm
- Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
- Spectrum of Controlling and Observing Complex Networks
- Bayesian inference of epidemics on networks via Belief Propagation
- Reconstructing propagation networks with natural diversity and identifying hidden sources
- Rooting out the Rumor Culprit from Suspects
- How to Identify an Infection Source with Limited Observations
- Computational Socioeconomics
- Locating the source of diffusion in complex networks by time-reversal backward spreading
- Identification of Patient Zero in Static and Temporal Networks - Robustness and Limitations
- Events Determine Spreading Patterns: Information Transmission via Internal and External Influences on Social Networks
- Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
- Confidence Sets for the Source of a Diffusion in Regular Trees
- Optimizing sensors placement in complex networks for localization of hidden signal source: A review
- Minimal contagious sets in random regular graphs
- Individual-based approach to epidemic processes on arbitrary dynamic contact networks
- Epidemic Source Detection in Contact Tracing Networks: Epidemic Centrality in Graphs and Message-Passing Algorithms
- Bayesian Inference of Spreading Processes on Networks
- The zero-patient problem with noisy observations
- Quantifying efficient information exchange in real network flows
- Back to the Past: Source Identification in Diffusion Networks from Partially Observed Cascades
- Detecting the Influence of Spreading in Social Networks with Excitable Sensor Networks
- Effects of city-size heterogeneity on epidemic spreading in a metapopulation: A reaction-diffusion approach
- Simulating SIR processes on networks using weighted shortest paths
- On the Properties of Gromov Matrices and their Applications in Network Inference
- Structural-constrained Methods for the Identification of Unobservable False Data Injection Attacks in Power Systems
- Multiple propagation paths enhance locating the source of diffusion in complex networks
- Schemes of Propagation Models and Source Estimators for Rumor Source Detection in Online Social Networks: A Short Survey of a Decade of Research
- Detection of Rumors and Their Sources in Social Networks: A Comprehensive Survey
- Statistical inference framework for source detection of contagion processes on arbitrary network structures
- Diffusion on hierarchical systems of weakly-coupled networks
- Inferring Spatial Source of Disease Outbreaks using Maximum Entropy
- Source Localization on Graphs via l1 Recovery and Spectral Graph Theory
- A Simple Algorithm for Graph Reconstruction
- Inverse source problem in a forced network
- Sensor-based localization of epidemic sources on human mobility networks
- Source Localization in Networks: Trees and Beyond
- Sequential metric dimension for random graphs
- Triangulation sensing: how cells recover a source from diffusing particles in three dimensions
- Inferring propagation paths for sparsely observed perturbations on complex networks
- Bayes-optimal inference for spreading processes on random networks
- Information Evolution in Complex Networks
- Locating Contagion Sources in Networks with Partial Timestamps
- Inferring network topology via the propagation process
- Rumor Source Detection under Querying with Untruthful Answers
- Statistical Mechanics of Inference in Epidemic Spreading
- Blind Identification of Invertible Graph Filters with Multiple Sparse Inputs
- Estimating Infection Sources in Networks Using Partial Timestamps
- Locating the Source of Large-scale Diffusion of Foodborne Contamination
- Node seniority ranking
- The metric dimension of critical Galton-Watson trees and linear preferential attachment trees
- Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols
- Self-stabilizing Algorithm for Maximal Distance-2 Independent Set
- Bandit algorithms for real-time data capture on large social medias
- Source location on multilayer networks
- Locating the source of interacting signal in complex networks
- Optimal Localization of Diffusion Sources in Complex Networks
- Locating the Source in Real-world Diffusion Network
- Nonlinear dynamics of information overload: Impact on source localization in complex networks
- Inference in Spreading Processes with Neural-Network Priors
- Reconstruction of Worm Propagation Path Using a Trace-back Approach
- Social Diffusion Sources Can Escape Detection
- Information Source Detection with Limited Time Knowledge
- Sharp bound on the threshold metric dimension of trees
- Catch'Em All: Locating Multiple Diffusion Sources in Networks with Partial Observations