An Efficient Randomized Algorithm for Rumor Blocking in Online Social Networks

Social networks allow rapid spread of ideas and innovations while negative information can also propagate widely. When a user receives two opposing opinions, they tend to believe the one arrives first. Therefore, once misinformation or rumor is detected, one containment method is to introduce a positive cascade competing against the rumor. Given a budget k, the rumor blocking problem asks for k seed users to trigger the spread of a positive cascade such that the number of the users who are not influenced by rumor can be maximized. The prior works have shown that the rumor blocking problem can be approximated within a factor of (1-1/e) by a classic greedy algorithm combined with Monte Carlo simulation. Unfortunately, the Monte Carlo simulation based methods are time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized approximation algorithm which is provably superior to the state-of-the art methods with respect to running time. The superiority of the proposed algorithm is demonstrated by experiments done on both the real-world and synthetic social networks.