Information source detection in the SIR model: A sample path based approach

By Kai Zhu, Lei Ying. Information Theory and Applications Workshop, 2012

320 citations recorded by the source corpus.

This paper studies the problem of detecting the information source in a network in which the spread of information follows the popular Susceptible-Infected-Recovered (SIR) model. We assume all nodes in the network are in the susceptible state initially except the information source which is in the infected state. Susceptible nodes may then be infected by infected nodes, and infected nodes may recover and will not be infected again after recovery. Given a snapshot of the network, from which we know all infected nodes but cannot distinguish susceptible nodes and recovered nodes, the problem is to find the information source based on the snapshot and the network topology. We develop a sample path based approach where the estimator of the information source is chosen to be the root node associated with the sample path that most likely leads to the observed snapshot. We prove for infinite-trees, the estimator is a node that minimizes the maximum distance to the infected nodes. A reverse-infection algorithm is proposed to find such an estimator in general graphs. We prove that for g-regular trees such that gq > 1, where g is the node degree and q is the infection probability, the estimator is within a constant distance from the actual source with high probability, independent of the number of infected nodes and the time the snapshot is taken. Our simulation results show that for tree networks, the estimator produced by the reverse-infection algorithm is closer to the actual source than the one identified by the closeness centrality heuristic.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/34d6500af86302bbadda74e2ae90279e1ca2de80

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

CSI: A Hybrid Deep Model for Fake News Detection (2017, background): “e nal characteristic, source, has been studied as the task of identifying the source of an epidemic on a graph [23, 40, 46], or isolating bots based on certain documented behaviors [7, 38].”
Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems (2016, background): “There have been pioneering efforts in addressing the source localization problem in complex networks, such as those based on the maximum likelihood estimation [416, 417], belief propagation [418], the phenomena of hidden geometry of contagion [419], particle diffusion and coloration [420], and inver”