Minimizing Influence of Rumors by Blockers on Social Networks: Algorithms and Analysis

摘要

Online social networks, such as Facebook, Twitter, and Wechat have become major social tools. The users can not only keep in touch with family and friends, but also send and share the instant information. However, in some practical scenarios, we need to take effective measures to control the negative information spreading, e.g., rumors spread over the networks. In this paper, we first propose the minimizing influence of rumors (MIR) problem, i.e., selecting a blocker set B with k nodes such that the users' total activation probability by rumor source set S is minimized. Then, we employ the classical independent cascade (IC) model as an information diffusion model. Based on the IC model, we prove that the objective function is monotone decreasing and non-submodular. To address the MIR problem effectively, we propose a two-stages method generating candidate set and selecting blockers for the general networks. Furthermore, we also study the MIR problem on the tree network and propose a dynamic programming guaranteeing the optimal solution. Finally, we evaluate proposed algorithms by simulations on synthetic and real-life social networks, respectively. Experimental results show our algorithms are superior to the comparative heuristic approaches, such as out-degree, betweenness centrality, and PageRank.