We introduce a statistical inference framework for maximum likelihood estimation of the contagion source from a partially observed contagion spreading process on an arbitrary network structure. The framework is based on simulations of a contagion spreading process from a set of potential sources which were infected in the observed realization. We present a number of different likelihood estimators for determining the conditional probabilities of potential initial sources producing the observed epidemic realization, which are computed in scalable and parallel way. This statistical inference framework is applicable to arbitrary networks with different dynamical spreading processes.
@cite_15: 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.
@cite_7: We study the problem of estimating the origin of an epidemic outbreak -- given a contact network and a snapshot of epidemic spread at a certain time, determine the infection source. Finding the source is important in different contexts of computer or social networks. We assume that the epidemic spread follows the most commonly used susceptible-infected-recovered model. We introduce an inference algorithm based on dynamic message-passing equations, and we show that it leads to significant improvement of performance compared to existing approaches. Importantly, this algorithm remains efficient in the case where one knows the state of only a fraction of nodes.
Zhu et. al. adopted the SIR model and proposed a sample path counting approach for source detection @cite_15 . They prove that the source node on infinite trees minimizes the maximum distance to the infected nodes. They assume that the infected and susceptible nodes are indistinguishable. Lokhov et. al. use a dynamic message-passing algorithm to estimate the probability that a given node produces an observed snapshot. They use a mean-field-like approximation to compute the marginal probabilities and an assumption of sparse contact network @cite_7 .