METAHEURÍSTICAS PARA EL PROBLEMA DE INFLUENCIA CON COSTE MÍNIMO EN REDES SOCIALES.

Abstract

En la actualidad, debido al auge del uso de Internet y las redes sociales, se ha visto propiciado el conocido ¿marketing viral¿, es decir, la búsqueda de estrategias que permitan difundir un mensaje de forma rápida y masiva a través de los propios usuarios. De esta motivación, surgen los problemas de investigación operativa relativos a la maximización de influencia en una red social. Durante este Trabajo de Fin de Grado, TFG, se va a tratar el problema de Least Cost Influence Problem (LCIP), o problema de influencia con menor coste, cuyo principal objetivo es hacer una asignación de incentivos a los usuarios de manera que la red quede influenciada por completo minimizando la suma de los incentivos. Este problema ha sido tratado con anterioridad por otros investigadores como Günneç y Raghavan, de quienes se han tomado sus artículos como referencia para comparar los resultados que se han obtenido en los experimentos realizados. Durante el trabajo se han implementado diferentes algoritmos para estudiar el problema, y, finalmente, se propone una solución metaheurística Greedy Random Adaptive Search Procedure (GRASP). Los resultados de esta propuesta muestran la eficiencia en la búsqueda de soluciones para el LCIP, obteniendo mejores resultados que con las propuestas del artículo que se ha tomado como referencia.