Minimizing spread of misinformation in social networks: a network topology based approach

In the emerging landscape of online social networks (OSNs), the rapid dissemination of misinformation poses a significant challenge to the integrity of information shared among users. Hence, misinformation containment problem in OSNs has drawn significant attention nowadays. In this paper, given a fixed budget, the problem is formulated as minimizing misinformation spread (MMS) problem, which is shown to be an NP-hard problem. With the objective to combat the misinformation in real time, this paper explores a new direction to leverage the network topology to minimize the search space drastically. Based on the community structure of the OSN along with the trust relationship among nodes, a novel linear-time seed node selection algorithm is proposed here that is independent of the positions of the misinformed nodes. Once the set of seed nodes is selected, it can combat any situation of misinformation spread in the OSN, provided the community structure of the network does not change significantly. To the best of our knowledge, this work is the first where trust relationship among users is considered along with the community structure of the network, to control the spread of misinformation in real time. To analyze the diffusion dynamics pertaining to both true information and misinformation, competitive linear threshold model (LTM) with provision for belief switching is followed to provide a more realistic and comprehensive understanding of information diffusion dynamics. Extensive experimental studies on large scale OSNs demonstrate that in comparison to earlier works, the proposed technique obtains 47-74% improvements in performance parameters. Not only that, its parallel implementations also achieve around 51x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$51\times$$\end{document} speedup compared to the earlier algorithms, revealing that the proposed technique is scalable on large scale OSNs for real-time restraint of misinformation.