Multi-Topic Misinformation Blocking With Budget Constraint on Online Social Networks

Abstract

Along with the development of Information Technology, Online Social Networks (OSN) are constantly developing and have become popular media in the world. Besides communication enhancement benefits, OSN have such limitations on rapid spread of false information as rumors, fake news, and contradictory news. False information spread is collectively referred to as misinformation which has significant on social communities. The more sources and topics of misinformation are, the greater the number of users are affected. Therefore, it is necessary to prevent the spread of misinformation with multiple topics within a given period of time. In this paper, we propose a Multiple Topics Linear Threshold model for misinformation diffusion, and define a misinformation blocking problem based on this model that takes account of multiple topics and budget constraint. The problem is to find a set of nodes that minimizes the impact of misinformation at an allowed cost when blocking them from the network. We prove that the problem is NP-hard and the time complexity of the objective function calculation is $\#P$ -hard. We also prove that the objective function is monotone and submodular. We propose an approximation algorithm with approximation ratio $(1-1/\sqrt {e})$ based on these attributes. For large networks, we propose an extended algorithm by using a tree data structure for quickly updating and calculating the objective function. Experiments conducted on real-world datasets show efficiency and effectiveness of our proposed algorithms in comparison with other state-of-the-art algorithms.

Keywords

• Information diffusion
• misinformation blocking
• optimization
• social networks