Robust rumor blocking problem with uncertain rumor sources in social networks

摘要

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 / 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 sub-modular 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 + ε) plus a constant, where γ is submodularity ratio and α is curva-ture.Finally, we evaluate our algorithm on real world data sets and do comparison among different strategies for protector. The results show the effectiveness and the efficiency of the proposed algorithm.