Temporally Agnostic Rumor-Source Detection

Abstract

We revisit the problem of inferring the source of a rumor on a network, given a snapshot of the extent of its spread. We differ from prior work in two aspects: We consider settings where additional relative information about the infection times of a fraction of node pairs is also available to the estimator and instead of only considering the most likely spreading pattern, we take a complementary approach where our estimator for general networks ranks each node based on counting the number of possible spreading patterns with a given node as root that are compatible with the observations. We first consider the case where additional information is available about infection incidents in the form of a set of directed pairs of neighboring nodes with the implication that the first is known to have infected the second. Under this hypothesis, we derive an estimator for the most likely rumor source based on the Markov chain tree theorem and propose a Markov Chain Monte Carlo scheme to find it. Empirical studies of various performance measures are provided, along with comparisons with the popular scheme of Shah and Zaman adapted to this framework. A further variant of the problem considered is when such pairwise temporal precedence is known for a fraction of pairs of nodes which, however, are not necessarily neighbors. For this case, we again propose a Markov Chain Monte Carlo based scheme for rumor source detection, which combines Aldous's algorithm for uniform sampling of arborescences with rejection sampling.