Containment Of Rumor Spread Based On Structure Optimization In Online Social Networks

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 effective strategies to contain the spread of rumors in OSNs.After extensive investigation of the existing research work on containing the spread of rumors in OSNs,this paper finds that few studies consider the community structure in OSNs when setting up rumor diffusion scenarios,and few rumor containing strategies make use of the community structure to optimize network structure.Therefore,this paper aims to make good use of community structure to design effective and practical strategies to optimize the network structure,thereby effectively limiting the spread of rumors within the communities where rumors originate,and eventually ensuring that the number of nodes affected by rumors is within a preset range.The main research contents of this paper are summarized as follows:First,this paper considers the optimization problem of blocking a single rumor community and containing the spread of rumors at a minimum cost under a single information propagation environment.Assume that 1)The non-overlapping community structure of the OSN is known.2)Rumors originate from a community.3)The rumor diffusion follows a given influence diffusion model and there is no other information to spread on the network other than rumors.The problem can be summarized as identifying a minimal subset of nodes and then removing all the nodes in this subset from the network,such that we can not only block rumors within the community where the rumor originates,but alsoguarantee 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.Based on graph theory and the non-overlapping community structure of the network,this paper designs a heuristic algorithm to solve the problem approximately.The experimental results show that the algorithm proposed in this paper performs better than the common heuristic algorithms,and it can delete 46.7% fewer nodes on average.Second,under a specific dual-information competitive influence diffusion model,this paper considers the optimization problem of blocking multiple rumor communities and containing the spread of rumors at a minimum cost.Assume that the non-overlapping community structure of the OSN is known,and that rumors originate from multiple communities of the network.The basic strategy for containing the spread of rumors is to select some protector nodes from the network to spread positive information,thereby fighting against rumors.The problem can be summarized as identifying a minimal subset of nodes to be protector nodes,such that rumors cannot propagate out of any community where the rumor originates,but also guarantee that the proportion of the number of nodes influenced by the rumor to the number of nodes that can be reached by rumors in the communities where rumors originate does not exceed a given proportion ? ?[0,1] at the end of rumor diffusion process.The problem is proved to be an NP-hard problem in this paper and two heuristic algorithms including Set Cover Based Greedy Rumor Containing algorithm and Minimum Vertex Cover Based Greedy Rumor Containing algorithm are designed to solve it approximately.Finally,extensive experiments are conducted and the simulation results show that the performance of the first algorithm is better than that of the second one.