Nuevos algoritmos metaheurísticos para el análisis de la influencia de los usuarios en las redes sociales

Resumen

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

Estudiante de Doctorado 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). Actualmente realiza su tesis doctoral en la Universidad Rey Juan Carlos, dirigida por los profesores Abraham Duarte y Jesús Sánchez-Oro 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.

Abraham Duarte

Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.