A fast Monte Carlo algorithm for source localization on graphs

Epidemic models on networks have long been studied by biologists and social sciences to determine the steady state levels of an infection on a network. Recently, however, several authors have begun considering the more difficult problem of estimating the source of an infection given information about its behavior some time after the initial infection. In this paper, we describe a technique to estimate the source of an infection on a general graph based on observations from a small set of observers during a fixed time window at some unknown time after the initial infection. We describe an alternate representation for the susceptible-infected (SI) infection model based on geodesic distances on a randomly-weighted version of the graph; this representation allows us to exploit fast algorithms to compute geodesic distances to estimate the marginal distributions for each observer and compute a pseudo-likelihood function that is maximized to find the source.