Conference Proceeding Article
The problem of information source detection, whose goal is to identify the source of a piece of information from a diffusion process (e.g., computer virus, rumor, epidemic, and so on), has attracted ever-increasing attention from research community in recent years. Although various methods have been proposed, such as those based on centrality, spectral and belief propagation, the existing solutions still suffer from high time complexity and inadequate effectiveness. To this end, we revisit this problem in the paper and present a comprehensive study from the perspective of likelihood approximation. Different from many previous works, we consider both infected and uninfected nodes to estimate the likelihood for the detection. Specifically, we propose a Maximum A Posteriori (MAP) estimator to detect the information source for general graphs with rumor centrality as the prior. To further improve the efficiency, we design two approximate estimators, namely Brute Force Search Approximation (BFSA) and Greedy Search Bound Approximation (GSBA). BFSA tries to traverse the permitted permutations and directly computes the likelihood, while GSBA exploits a strategy of greedy search to find a surrogate upper bound of the probabilities of permitted permutations for a given node, and derives an approximate MAP estimator. Extensive experiments on several network data sets clearly demonstrate the effectiveness of our methods in detecting the single information source.
Greedy search, Information source detection, Likelihood approximation, Maximum a posteriori
Databases and Information Systems
Data Management and Analytics
Proceedings 15th IEEE International Conference on Data Mining ICDM 2015
City or Country
CHANG, Biao; ZHU, Feida; CHEN, Enhong; and LIU, Qi..
Information source detection via maximum a posteriori estimation. (2016). Proceedings 15th IEEE International Conference on Data Mining ICDM 2015. 21-30. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3137
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.