Rumor Source Detection: A Probabilistic Perspective
Journal
ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Journal Volume
2018-April
Pages
4159-4163
Date Issued
2018
Author(s)
Fan, T.-H.
Abstract
In this paper we consider the problem of rumor source detection in a network. Our main contribution is an efficient Belief-Propagation-based (BP) algorithm to compute the joint likelihood function of the source location and the spreading time for the general continuous-time Susceptible-Infected epidemic model on trees. As a result, many probabilistic detection algorithms, including the joint maximum likelihood estimator, can be implemented with time complexity being nearly linear in the product of the size of the graph and the effective range of the spreading time. This is in sharp contrast to the widely employed discrete-time epidemic models where the complexity in computing the likelihood function of the source location is exponential. To extend the BP algorithm to general graphs, we propose a 'Gamma Generated Tree' heuristic to convert the original graph to a tree with heterogeneous infection rates over edges. Compared to state-of-the-art methods, simulation results show that our algorithm provides better estimates of the source when the graph topology is similar to trees. As a byproduct, the spreading time can also be estimated, which is useful in some applications. © 2018 IEEE.
Subjects
Belief Propagation; Maximum Likelihood Estimation; Rumor Source Detection; Social Networks
SDGs
Type
conference paper