Algoritmos de optimización por colonia de hormigas para la maximización de la influencia en grafos

Abstract

En los tiempos que vivimos, nos rodea una gran afluencia de información que podemos usar para nuestros propósitos. Es posible modelar el entorno que nos rodea en grafos para analizar las distintas relaciones y sistemas que se hallan presentes a nuestro alrededor. Dentro de la gran cantidad de problemas que pueden abarcar los grafos hay un conjunto que son recogidos por el problema de la maximización de la influencia. El problema tiene aplicaciones en marketing viral, por ejemplo. Dadas una red social y una estimación de en qué medida quién influye a quién, para una empresa que pretende comercializar un nuevo producto es interesante saber qué miembros influyentes de la red social pueden provocar una mayor aceptación del producto al darle visibilidad. El inconveniente de este problema es que es NP-duro, y por lo tanto encontrar soluciones para problemas con grandes cantidades de datos puede ser computacionalmente muy costoso. No obstante, existen formas de paliar esta desventaja, con el uso de heurísticas, que a cambio de darnos soluciones aproximadas, tendrán una complejidad temporal mucho menor. En este caso nos centraremos en la metaheurística de colonia de hormigas y experimentaremos con distintas variantes de este algoritmo, con el objetivo de diseñar e implementar un nuevo algoritmo de optimización que supere, en tiempo de ejecución o soluciones encontradas, a la versión ACO-IM (Singh et al. 2020) de la que se partirá.

Nowadays, we are surrounded by a large amount of information, which we can use for our purposes. It’s possible to model our surroundings in influence graphs, to analyze various relationships and systems that exist around us. There are a lot of problems that we can include in the scope of influence graphs, but we are going to focus on those related to the problem of maximizing influence. This problem has applications in viral marketing, for example. Given a social network and an estimate of who influences whom, it is interesting to know for a company which influential members in the social network can trigger a major acceptance of the product by giving it visibility. A big drawback of this problem is that it is NP-hard, which means that finding solutions for problems with a large collection of data can be computationally complex. Nonetheless, we can circumvent this by using heuristics, which will give approximated solutions in a much better time. In this case, we will focus on the metaheuristic of Ant Colony, we will experiment with various variants of this algorithm, with the objective of designing and implementing a new optimization algorithm that exceeds, in execution time or solutions found, the ACO-IM (Singh et al. 2020) version from which we will start.