METAHEURÍSTICAS PARA LA RESOLUCIÓN DEL PROBLEMA DE CONJUNTO DOMINANTE DE INFLUENCIA POSITIVA MÍNIMA EN REDES SOCIALES

Abstract

Con el auge del uso de internet y las redes sociales, han aparecido nuevos retos para intentar estudiar el comportamiento de las personas en ellas. Todos los usuarios tienen gustos relacionados con un conjunto reducido de usuarios, de tal manera que confíen más o sean más afines con ellos. Por este motivo, algunas técnicas de marketing viral pretenden propagar la información sobre el producto o servicio que quieran anunciar lo más efectivamente posible. De esta motivación, se definirían los problemas de investigación operativa de maximización de influencia social.

Durante este Trabajo de Fin de Grado se va a tratar el problema de conjuntos dominantes de influencia mínima positiva (MPIDS), el cual pretende conseguir un conjunto dominante en una red social de mínima cardinalidad. Con este conjunto, se definirían aquellos usuarios clave que conseguirían acelerar la difusión de influencia en la red. En concreto, se van a realizar implementaciones de varios algoritmos para estudiar en profundidad el problema y, finalmente, se implementará un algoritmo de búsqueda básica por entornos variables (BVNS) en combinación con una búsqueda local.

Este problema ha sido tratado ya por varios investigadores como F. Wang, C. Blum o R. Sun, entre otros. De este último, se tomará uno de sus artículos como referencia para poder comparar los resultados que se obtenga con el algoritmo BVNS que se implementará con el fin de conseguir resultados competentes. Finalmente, se analizarán los resultados obtenidos por los diferentes experimentos realizados y se comprobará la eficiencia del algoritmo BVNS para obtener soluciones de calidad para el problema de MPIDS.