Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

1-2016

Abstract

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.

Keywords

Greedy search, Information source detection, Likelihood approximation, Maximum a posteriori

Discipline

Databases and Information Systems

Publication

Proceedings 15th IEEE International Conference on Data Mining ICDM 2015

First Page

21

Last Page

30

ISBN

9781467395038

Identifier

10.1109/ICDM.2015.116

Publisher

IEEE

City or Country

MA, USA

Download

Share

COinS