A Theoretically Guaranteed Approach to Efficiently Block the Influence of Misinformation in Social Networks

Abstract

Nowadays, social network plays an important role in human life. Besides all advantages of social networks, the dissemination of rumors becomes a major concern for users, so it is important to find a way to limit the spread of misinformation as much as possible. Influence blocking maximization (IBM) is the problem of finding k nodes in a social graph to minimize the spread of rumor source at the end of a propagation process. In this article, we propose a two-step method called influence blocking maximization using martingale (IBMM) to solve IBM problem under competitive independent cascade model (ICM) with both (1-1/e-ε)-approximation guarantee and practical runtime efficiency. In the proposed method, first we calculate the number of required samples using a set of estimation techniques based on martingale; and then we generate the samples and find top- k savior nodes. We perform extensive experiments on three real-world data sets and three rumor sets with different behaviors. We both experimentally and theoretically show that the effectiveness of IBMM is close to greedy. The results also show that IBMM is very fast, in particular, for a network with 265 214 nodes, 420 045 edges, and a set of 50 high influential nodes as rumor, when k = 50, l=1, and ε = 0.5 IBMM returns the solution within 3.5 s.