BPSL: a new rumor source location algorithm based on the time-stamp back propagation in social networks

Finding a rumor source is a major issue in the analysis of social networks. In this problem, the rumor source is usually estimated from a given diffusion snapshot. How to estimate the rumor source accurately is a challenging problem. Usually, the rumor source location problem is regarded as a node ranking problem. However, most of the existing algorithms ignore the structure of the infected subgraph or the randomness of the rumor spread. Therefore, they have defects in applicability and accuracy. To solve this problem, this paper takes into account the above two aspects at the same time, and propose a new algorithm to locate the rumor source, which is called Back Propagation Source Location(BPSL). The proposed algorithm contains an estimation method which is based on the time-stamp back propagation. This method makes the proposed algorithm’s accuracy outperform previous algorithms’ accuracy. Moreover, the susceptible-infected model is used to simulate the information spread of the networks. The steps of the proposed algorithm can be stated as follows. First, a new method based on the influence maximization is proposed to determine the observer set, which can greatly reduce the number of observer nodes. Second, a new estimation method based on the time-stamp back propagation is proposed to locate the source, which makes the proposed algorithm more accuracy and doesn’t change the structure of infected subgraph at the same time. Finally, the experimental results on two artificial networks and four real-world networks show the superiority of the proposed algorithm.