Stochastic Model for Rumor Blocking Problem in Social Networks Under Rumor Source Uncertainty

Either in real world social society or online social networks, rumor blocking is an important issue. Rumor sources spread negative information throughout the network, which may cause unbelievable results in real society, such as panic, unrest. Propagating positive information from several “protector” users is an effective method for rumor blocking once the rumor is detected. In this paper, we assume that user will not be influenced if they receive the positive information ahead of negative one. According to data analysis of user’s activity, network manager may not know the exact positions of rumor but the probability of each user being a rumor, “protector” nodes need to be selected in order to prepare for rumor blocking. Given a social network \(G=(V,E,P,Q)\) , 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, and Q is the weight function on node set V, \(Q_v\) is the probability that v will be a rumor source. Stochastic Rumor Blocking (SRB) problem is to select k nodes as “protectors” such that the expected influence of rumors on users is minimized eventually. SRB will be proved to be NP-hard and the objective function is supermodular. We present a Compound Reverse Influence Set (CRIS) sampling method for estimation of the objective value which can be represented as a compound set function. Based on CRIS, a randomized greedy algorithm with theoretical analysis will be presented.