关键词: 社交网络, 信息传播, 影响力最大化, 虚假信息控制, 三明治近似策略

Abstract: The popularity of online social networks such as Wechat has aroused people’s more attention to information diffusion.The spread of misinformation in social networks may lead to serious consequences,such as economic losses and public panic.Therefore,relevant measures need to be taken to control the spread of misinformation.The classical misinformation containment problem aims to reduce the impact of misinformation by launching a set of nodes as real information seeds to compete against misinformation.This paper combines the spread of real information with the edge addition,proposes a misinformation correction maximization problem.The proposed problem is NP-hard and the computation of its objective function is #P-hard.Then,we use the sandwich approximation strategy to get an approximation solution since the objective function is neither submodular nor supermodular.We first find submodular lower and upper bound functions of the objective function,and then get corresponding approximation solutions under the cardinality constraint by the reverse influence sampling technique.At last,combined with lower and upper bound function’s solution,we obtain an approximation solution for misinformation correction maximization problem with a data-dependent approximation ratio.Experiments on three realistic data sets indicate that the proposed algorithm is efficient and performs better than classical heuristic methods.

Key words: Social network, Information diffusion, Influence maximization, Misinformation containment, Sandwich approximation strategy