Evaluation of rumor source estimation algorithms

Abstract

In modern society, social network had evolved as a powerful tool for users to interact with others all over the world. As time goes by, many social network platforms with huge number of users such as Weibo, Facebook and Twitter have become new means of rumor-spreading platforms. Detecting the rumor source on social network is essential as the rumors constantly cause harmful effects to the public wellness as well as human in terms of social exposure, physical and psychological well-being. To detect the rumor source, many techniques have been proposed in recent years. The performance of the techniques should be evaluated to examine their effectiveness of detecting the rumor source. In this project, Belief Propagation (BP) algorithm was selected to achieve our objectives. BP algorithm is a decoding algorithm based on passing messages between local functions and the corresponding variables and computes the marginal probability distribution of the true source. We operated the algorithm on factor graph under SIR model and tested it on both random regular graphs (RRG) and Erdős Rényi (ER) Graph on synthetic datasets. We evaluated the performance of the algorithm based on an indicator called normalized rank of true source. The simulation results showed the BP algorithm can effectively estimate the rumor source in terms of the small epidemic size and observation time.