TY  - JOUR
PY  - 2021//
TI  - Robust rumor blocking problem with uncertain rumor sources in social networks
JO  - World wide web
A1  - Zhu, Jianming
A1  - Ghosh, Smita
A1  - Wu, Weili
SP  - 229
EP  - 247
VL  - 24
IS  - 1
N2  - 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+
LA  - en
SN  - 1386-145X
UR  - http://dx.doi.org/10.1007/s11280-020-00841-8
ID  - ref1
ER  -