Abstract
In this paper, we study the problem of rooting out a single rumor source: supposing that a rumor, which originates from one node among a set of suspect nodes in a network, is spreading across the network following the susceptible-infected (SI) model, how can we and how well can we identify this rumor source? With the a priori knowledge of the set of suspect nodes and a snapshot observation of infected nodes, we construct a maximum a posteriori (MAP) estimator to identify the rumor source. For regular tree-type networks, we establish exact and asymptotic results on the detection probability of the source estimator. In particular, if the network is not linear, we have the following asymptotic results of the correct detection probability: First, when every infected node belongs to the suspect set, it grows from 0.25 to 0.307 as the node degree increases from three to infinity, a result first established in [1], [2] via a different approach. Second, when the suspect nodes form a connected subgraph of the network, it significantly exceeds the a priori probability, and reliable detection is achieved as the node degree becomes large. Third, when there are only two suspect nodes, it is at least 0.75 and increases with the distance between the two nodes. Our analysis leverages ideas from the Polya's urn model and sheds insight into the behavior of the rumor spreading process.

This publication has 10 references indexed in Scilit: