Citation

Zhu J, Ghosh S, Wu W. World Wide Web 2021; 24(1): 229-247.

Copyright

(Copyright © 2021, Holtzbrinck Springer Nature Publishing Group)

DOI

10.1007/s11280-020-00841-8

PMID

unavailable

Abstract

Rumormongers spread negative information throughout the social network, which may even lead to panic or unrest. Rumor should be blocked by spreading positive information from several protector nodes in the network. Users will not be influenced if they receive the positive information ahead of negative one. In many cases, network manager or government may not know the exact positions where rumor will start. Meanwhile, protector nodes also need to be selected in order to prepare for rumor blocking. Given a social network G = (V,E,P), where P is the weight function on edge set E, P(u,v) is the probability that v is activated by u after u is activated. Assume there will be l rumormongers in the network while the exact positions are not clear, Robust Rumor Blocking(RRB) problem is to select k nodes as protector such that the expected eventually influenced users by rumor is minimized. RRB will be proved to be NP-hard and the objective function is neither submodular nor supermodular. We present an estimation process for the objective function of RRB based on Reverse Reachable Set(RR-Set) methods. A randomized greedy algorithm is designed for solving this problem. And this algorithm is proved to have approximation ratio 1α(1−e−αγ)(1+