A scalable GRASP algorithm for the targeted misinformation blocking problem

Abstract

The research on Social Network Analysis has exponentially grown in the last decades due to the relevance of social networks in the society. Although most of the works have been focused on the maximization of influence, the spread of misinformation and its impact in relevant aspects of the society such as politics or economy, among others, have attracted the attention of both practitioners and the scientific community. This work is focused on the Targeted Misinformation Blocking Problem (TMB), whose aim is to minimize the number of nodes required to reduce the spread of misinformation through a social network. It is considered that if the information is spread under a certain target, then it would not have effect on the network. Therefore, the objective is to find a subset of blocking nodes that guarantee that the spread of information is below that target. However, existing state-of-the-art approaches face significant scalability limitations, often failing to generate feasible solutions for large-scale networks due to the high computational cost of influence estimation. To that end, a Scalable Greedy Randomized Adaptive Search Procedure (GRASP) algorithm is proposed, being able to deal with medium and large scale networks in reasonable computing time. The results obtained are compared with the best method found in the literature, Scalable TMB, which generates a set of trees to simulate the influence spread and identify the most promising nodes. Experimental results show that the proposed algorithm is able to outperform the state of the art when considering two of the most extended diffusion models. Additionally, the scalability of the proposal is proven, been able to provide high-quality solutions even in those instances in which previous algorithm are not able to generate a feasible one. Those results, supported by non-parametric statistical tests, indicates that the proposed algorithm is a competitive method for solving the TMB.