Research Of Misinformation Containment Problem In Social Networks Based On Influence Maximization

The popularity of online social networks has aroused people’s more attention to information diffusion,how to maximize the information diffusion has become a hot issue.As a key question in information diffusion research,influence maximization problem has been extensively studied.Social networks also provide a platform for the misinformation,and the spread of misinformation in social networks may lead to serious consequences.It is crucial to propose effective method to control the dissemination of misinformation,in which a hot research is to study the misinformation containment problem based on the influence maximization problem.In this topic,the common method is to spread a corresponding real information to prevent the spread of misinformation.The classical misinformation containment problem based on the strategy of disseminating real information aims to reduce the impact of misinformation by launching a set of nodes as real information seeds to compete against misinformation,and it is believed that nodes can only accept one information.This paper considers that the infected nodes can still accept real information,and facilitates the propagation of real information by adding edges,and then forms a new misinformation containment problem.The main work is as follows:(1)First,under the assumption that the propagation process of the misinformation has terminated,we study the problem that make as many infected nodes as possible be corrected by adding edges,called misinformation correction maximization problem with edge addition.We use the sandwich approximation method to get an approximation solution with a data-dependent approximation ratio since the objective function is neither submodular nor supermodular.We first find submodular lower and upper bound functions of the objective function,and then modify the original IMM algorithm to solve the corresponding upper and lower bound problems.Finally,we evaluate the proposed algorithm by conducting experiments on three real datasets,and show the proposed algorithm outperforms other baseline algorithms.(2)Second,we consider a more general case that the propagation process of the misinformation has not yet terminated,and aims to make as many nodes as possible not infected by adding edges.The set of candidate edges has been narrowed down in this problem in order to be more practical.We propose the CELF*algorithm and the Modified-IMM algorithm with approximate ratio no more than 1-1/e-ε since the objective function is submodular.Finally,we experimentally compare the two algorithms on three real datasets,and the experimental results verify the Modified-IMM algorithm performs more efficient.