Least Cost Rumor Community Blocking optimization in Social Networks

Abstract

The rapid development of online social networks (OSNs) makes it possible for rumors to spread quickly and widely, which can result in undesirable social effects. Hence, it is necessary to design an effective strategy to contain the spread of rumors in OSNs. In this paper, we assume rumors originate from one community C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</sub> in a social network and adopt a given influence diffusion model as the rumor diffusion model, then we consider the Least Cost Rumor Community Blocking Optimization (LCRCBO) problem. The problem can be summarized as identifying a minimal subset of nodes and then removing all the nodes in this subset as well as their incoming and outgoing edges from the network, such that we can not only block rumors within C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</sub> but also guarantee that the expected number of nodes influenced by the rumor does not exceed a given positive integer K at the end of rumor diffusion process. Under these two constraints, the Minimum Vertex Cover Based Greedy (MVCBG) algorithm is proposed to solve the LCRCBO problem in this paper. Finally, to validate the effectiveness of the MVCBG algorithm, we conduct experiments on three real-world networks and two artificial networks. The simulation results show that the MVCBG algorithm outperforms other heuristics.