New metaheuristic algorithms for the analysis of the user influence in social networks

Resumen

The evolution and spread of social networks have attracted the interest of the scientific community in the last few years. Specifically, several new interesting problems which are hard to solve have arisen in the context of viral marketing, disease analysis and influence analysis , among others. Companies and researchers try to find the elements that maximize profit, stop pandemics, etc. This family of problems are usually known as Social Network Influence Maximization (SNIM) problems , whose goal is to find the most influential users (commonly known as seeds) in the social network, simulating an influence diffusion model. Since SNIM is known to be an NP-hard problem, and most of the networks to analyze are considerably large, this problem have become a real challenge for the scientific community. Different works have attempted to solve it by means of heuristic or metaheuristic approaches, such as evolutionary algorithms based on simulations of the spreading mechanism , but they are not able to solve real-world large-scale networks due to their limitations in computing time. The main drawback of this optimization problem lies in the computational effort required to evaluate a solution. Since the infection of a node is evaluated in a probabilistic manner, the objective function value requires from a Monte Carlo simulation to see the robustness of the method, resulting in a computationally complex process. The current proposal tries to overcome this limitations by considering a metaheuristic algorithm based on the Greedy Random-ized Adaptive Search Procedure (GRASP) framework. The construction phase is based on static features of the network, which notably increases its efficiency, since it does not require to perform any simulation during construction. The local improvement involves a surrogate-assisted-swap local search to find the most influential users based on swap moves. Experiments performed on 6 well-known social networks datasets with 5 different seed set sizes confirm that the proposed algorithm is able to provide competitive results in terms of quality and computing time when comparing it with the best algorithms found in the state of the art.

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.