How to Identify an Infection Source with Limited Observations
arXiv:1309.4161 · doi:10.1109/JSTSP.2014.2315533
Abstract
A rumor spreading in a social network or a disease propagating in a community can be modeled as an infection spreading in a network. Finding the infection source is a challenging problem, which is made more difficult in many applications where we have access only to a limited set of observations. We consider the problem of estimating an infection source for a Susceptible-Infected model, in which not all infected nodes can be observed. When the network is a tree, we show that an estimator for the source node associated with the most likely infection path that yields the limited observations is given by a Jordan center, i.e., a node with minimum distance to the set of observed infected nodes. We also propose approximate source estimators for general networks. Simulation results on various synthetic networks and real world networks suggest that our estimators perform better than distance, closeness, and betweenness centrality based heuristics.
References in corpus (6)
- The structure and function of complex networks
- The Dynamics of Viral Marketing
- Locating the Source of Diffusion in Large-Scale Networks
- Identifying Infection Sources and Regions in Large Networks
- Rooting out the Rumor Culprit from Suspects
- Immunization of Susceptible-Infected Model on Scale-Free networks
Cited by in corpus (15)
- Infection Spreading and Source Identification: A Hide and Seek Game
- On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks
- Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
- On the Properties of Gromov Matrices and their Applications in Network Inference
- Detection of Rumors and Their Sources in Social Networks: A Comprehensive Survey
- Estimating Infection Sources in Networks Using Partial Timestamps
- Network infection source identification under the SIRI model
- Locating the source of interacting signal in complex networks
- Network Topology Inference Using Information Cascades with Limited Statistical Knowledge
- Source location on multilayer networks
- Graph Signal Processing over a Probability Space of Shift Operators
- Contamination source inference in water distribution networks
- Information Source Detection with Limited Time Knowledge
- Identifying Rumor Sources Using Dominant Eigenvalue of Nonbacktracking Matrix
- Information Source Finding in Networks: Querying with Budgets