Rumor Source Detection: Power of Protector

Abstract

Recently, the problem of detecting the rumor source in a social network has been much studied, where it has been shown that the detection probability cannot be beyond 31% even for regular trees [1,2]. In this paper, we study the impact of an anti-rumor on the rumor source detection. We rst show a negative result: the anti-rumor's diffusion does not increase the detection probability under Maximum-Likelihood-Estimator (MLE) under passive diffusion that the anti-rumor starts to be spread by a special node, called the protector, after is reached by the rumor. We next consider the case when the distance between the rumor source and the protector follows certain type of distributions such as Zipf, Geometric and Poisson distribution (but their parameters are hidden) where the higher probabilities are assigned to nearer rumor sources from the protector source under them. This is reasonable in practice since it is natural to place a protector near prior rumor sources by historical information of the location of rumor sources. Then, we propose the following learning algorithm: a) learn the distance distribution parameters under MLE, and b) detect the rumor source under Maximum-A-Posterior-Estimator (MAPE) based on the learnt parameters. We provide an analytic characterization of the rumor source detection probability for regular trees under the proposed algorithm, where MAPE outperforms MLE by up to 50% for 3- regular tree and by up to 63% when the degree of the regular tree becomes large. We demonstrate our theoretical ndings through numerical results, and further present the simulation results for general topologies by using a heuristic algorithm based on Breadth-First Search (MAP-BFS) even without knowledge of the distance distribution, showing that under a simple protector placement algorithm, MAPE produces the detection probability much larger than that by MLE