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 focused on the maximization of influence, the spread of misinformation and its impact on 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 an effect on the network. Therefore, the objective is to find a subset of blocking nodes that guarantees 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, being able to provide high-quality solutions even in those instances in which previous algorithms are not able to generate a feasible one. Those results, supported by non-parametric statistical tests, indicate that the proposed algorithm is a competitive method for solving the TMB.
Iván Penedo
Master’s Degree in Artificial Intelligence Research
Iván Penedo graduated in a double degree in Computer Science and Software Engineering in the Rey Juan Carlos University in 2024. He is working here as a researcher focusing in social network analysis.
Isaac Lozano-Osorio
Phd in Artificial Intelligence
Isaac Lozano graduated with a double degree in Computer Engineering and Computer Engineering from the Universidad Rey Juan Carlos, where he was awarded the prize for the Best Final Project. Subsequently, he completed a Master in Artificial Intelligence Research (UIMP). His main research interests are focused on the interface between Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristic procedures for graph modeled optimization problems.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.