Resumen
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
Máster en Inteligencia Artificial
Iván Penedo se graduó en Ingeniería Informática e Ingeniería del Software en la Universidad Rey Juan Carlos en 2024. Actualmente trabaja como investigador centrado en problemas de análisis de redes sociales.
Isaac Lozano-Osorio
Doctor en Inteligencia Artificial
Isaac Lozano se graduó en el Doble grado de Ingeniería Informática e Ingeniería de Computadores por la Universidad Rey Juan Carlos. Al finalizar el doble grado, fue galardonado con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Investigación en Inteligencia Artificial (UIMP) y es doctor por la Universidad Rey Juan Carlos. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.
Jesús Sánchez-Oro
Profesor Titular de Universidad
Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.