A Markov Chain Monte Carlo Approach for Source Detection in Networks

The source detection task, which targets at finding the most likely source given a snapshot of the information diffusion, has attracted wide attention in theory and practice. However, due to the hardness of this task, traditional techniques may suffer biased solution and extraordinary time complexity. Specially, source detection task based on the widely used Linear Threshold (LT) model has been largely ignored. To that end, in this paper, we formulate the source detection task as a Maximum Likelihood Estimation (MLE) problem, and then proposed a Markov Chain Monte Carlo (MCMC) algorithm, whose convergence is demonstrated. Along this line, to further improve efficiency of proposed algorithm, the sampling method is simplified only on the observed graph rather than the entire one. Extensive experiments on public data sets show that our MCMC algorithm significantly outperforms several state-of- the-art baselines, which validates the potential of our algorithm in source detection task.