Identifying the Source of Information Spread in Networks via Markov Chains
For researchers studying information diffusion in social networks, this provides a computationally efficient approach to source detection, though it is incremental over existing MLE-based methods.
The paper proposes an efficient method for identifying the source of information spread in networks under the Independent Cascade model, using Markov chain stationary distributions to approximate maximum likelihood estimation. Simulations show it outperforms state-of-the-art methods on both random and real-world networks.
Nowadays, the diffusion of information through social networks is a powerful phenomenon. One common way to model diffusions in social networks is the Independent Cascade (IC) model. Given a set of infected nodes according to the IC model, a natural problem is the source detection problem, in which the goal is to identify the unique node that has started the diffusion. Maximum Likelihood Estimation (MLE) is a common approach for tackling the source detection problem, but it is computationally hard. In this work, we propose an efficient method for the source detection problem under the MLE approach, which is based on computing the stationary distribution of a Markov chain. Using simulations, we demonstrate the effectiveness of our method compared to other state-of-the-art methods from the literature, both on random and real-world networks.