A probabilistic characterization of the rumor graph boundary in rumor source detection

Estimation of the source to an epidemic-like spreading has important applications such as rooting out a computer virus in the Internet or rumor spreading in an online social network. Given a snapshot observation of the nodes in the network possessing the malicious information, how to identify the source of the spreading? This problem was first formulated in the seminal work by Shah and Zaman (TIT 2011) as a maximum likelihood estimation problem for a degree-regular graph. In this paper, we provide a probabilistic characterization to the rumor boundary of the observed graph. This leads to a new probabilistic approach of maximum likelihood estimation for a general tree graph that enables a distributed message-passing algorithm. We also evaluate the performance of the message-passing algorithm for finding the rumor center in general graphs numerically.