Resolución del problema de conjunto dominante de influencia positiva mı́nima en redes sociales mediante metaheurśticas

Resumen

El auge de internet y las redes sociales han propuesto nuevos retos para intentar estudiar el comportamiento de las personas en ellas. Normalmente, cada persona tiene gustos similares a los de un pequeño grupo de personas, aquellos que son más afines o en los que más confían. Por este motivo, se han diseñado nuevas técnicas de marketing viral que pretenden propagar la información sobre el producto o servicio que quieran anunciar de manera efectiva. De esta motivación, se definen los problemas de maximización/minimización de influencia social y conjuntos de dominancia. En concreto, el problema de conjuntos dominantes de influencia positiva mínima (del inglés Minimum Positive Influence Dominating Set, MPIDS) consiste en obtener un conjunto de dominancia de cardinalidad mínima que permita influir en toda una red social. Como restricción, el problema define que para que un nodo se vea influenciado, al menos la mitad de sus vecinos deben encontrarse en el conjunto de dominancia. Teniendo en cuenta que el MPIDS es un problema NP-difícil donde aproximaciones exactas no son posibles debido al tamaño de las redes sociales. En este trabajo se propone el uso de Greedy Randomized Adaptive Search Procedure (GRASP). Esta reconocida metaheurística se compone de dos fases: una fase constructiva y una fase de mejora. La fase constructiva diseñada se compara con un enfoque completamente voraz y otro completamente aleatorio. Por otro lado, la fase de mejora se lleva a cabo en dos etapas. En la primera, se aplica un procedimiento de eliminación de nodos redundantes dentro del conjunto solución. Posteriormente, se propone una estrategia innovadora de búsqueda local, basada en la generación de agujeros, que consiste en eliminar la -vecindad de un nodo para facilitar una reconstrucción inteligente de la solución. Los resultados obtenidos muestran una desviación de un 5.54% frente al estado del arte sobre un conjunto de 196 instancias de tamaños variables

Iván Penedo

Estudiante de 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.