Estimating Infection Sources in Networks Using Partial Timestamps
arXiv:1711.01537
Abstract
We study the problem of identifying infection sources in a network based on the network topology, and a subset of infection timestamps. In the case of a single infection source in a tree network, we derive the maximum likelihood estimator of the source and the unknown diffusion parameters. We then introduce a new heuristic involving an optimization over a parametrized family of Gromov matrices to develop a single source estimation algorithm for general graphs. Compared with the breadth-first search tree heuristic commonly adopted in the literature, simulations demonstrate that our approach achieves better estimation accuracy than several other benchmark algorithms, even though these require more information like the diffusion parameters. We next develop a multiple sources estimation algorithm for general graphs, which first partitions the graph into source candidate clusters, and then applies our single source estimation algorithm to each cluster. We show that if the graph is a tree, then each source candidate cluster contains at least one source. Simulations using synthetic and real networks, and experiments using real-world data suggest that our proposed algorithms are able to estimate the true infection source(s) to within a small number of hops with a small portion of the infection timestamps being observed.
arXiv comment15 pages, 15 figures, accepted by IEEE Transactions on Information Forensics and Security
References in corpus (13)
- Emergence of scaling in random networks
- Epidemic spreading in scale-free networks
- Understanding the spreading patterns of mobile phone viruses
- Locating the Source of Diffusion in Large-Scale Networks
- Inferring the origin of an epidemic with a dynamic message-passing algorithm
- Bayesian inference of epidemics on networks via Belief Propagation
- Identifying Infection Sources and Regions in Large Networks
- How to Identify an Infection Source with Limited Observations
- Locating the source of diffusion in complex networks by time-reversal backward spreading
- Nonparametric Stein-type Shrinkage Covariance Matrix Estimators in High-Dimensional Settings
- Infection Spreading and Source Identification: A Hide and Seek Game
- Source Localization in Networks: Trees and Beyond
- Modeling the Propagation of Trojan Malware in Online Social Networks