Nuevos algoritmos metaheurísticos para el análisis de la influencia de los usuarios en las redes sociales
Abstract
La evolución y la difusión de las redes sociales han atraído el interés de la comunidad científica en los últimos años. En concreto, han surgido nuevos problemas interesantes y difíciles de resolver. En el contexto del marketing viral las empresas y los investigadores tratan de encontrar los elementos que maximizan los beneficios, incrementan visualizaciones, etc. Esta familia de problemas suele conocerse como problemas de maximización de la influencia en redes sociales (SNIM, del inglés Social Network Influence Maximization), cuyo objetivo es encontrar los usuarios más influyentes (comúnmente conocidos como semillas) en la red social, simulando un modelo de difusión de influencia. Como se sabe que SNIM es un problema NP-difícil, y la mayoría de las redes a analizar son considerablemente grandes, este problema se ha convertido en un verdadero reto para la comunidad científica. Diferentes trabajos han intentado resolverlo mediante enfoques heurísticos o metaheurísticos, como los algoritmos evolutivos basados en simulaciones del mecanismo de propagación, pero no son capaces de resolver redes de gran tamaño del mundo real debido a sus limitaciones en tiempo de computación. El principal inconveniente de este problema de optimización reside en el esfuerzo computacional necesario para evaluar una solución. Dado que la infección de un nodo se evalúa de forma probabilística, el valor de la función objetivo requiere de una simulación de Monte Carlo para analizar la robustez del método, resultando un proceso computacionalmente complejo. Nuestra propuesta trata de superar estas limitaciones considerando un algoritmo metaheurístico basado en el marco del Greedy Randomized Adaptive Search Procedure (GRASP). Esta metodología se divide en dos fases: la fase de construcción, basada en características estáticas de la red para aumentar su eficiencia al no requerir realizar ninguna simulación, y la fase de optimización local, que consiste en una búsqueda local limitada para encontrar a los usuarios más influyentes basándose en movimientos de intercambio. Los experimentos realizados en 6 conocidos conjuntos de datos de redes sociales con 5 tamaños diferentes de conjuntos de semillas confirman que el algoritmo propuesto es capaz de proporcionar resultados competitivos en términos de calidad y tiempo de computación al compararlo con los mejores algoritmos encontrados en el estado del arte.
Isaac Lozano-Osorio
Artificial Intelligence Phd Student
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.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.