Locating Sources in Online Social Networks via Random Walk

To locate source nodes of influence propagation given an observation set in online social networks is the source location problem. It is increasingly critical to control the diffusion of malicious information in terms of source nodes with the popularity of online social networks. In this paper, we focus on multi-source location with incomplete information. First, to track the causes that make node activation, we propose the Bayes backtracking model (BBM), where the posterior probabilities of activation causes are formulated. Then, we employ random walk to represent the source backtracking process and present the corresponding backtracking algorithm for source location by taking the posterior probability in BBM as the transition probability in random walk. Finally, we test the effectiveness of our method on real online social networks and make performance studies.