Multi-Round Influence Maximization: A Variable Neighborhood Search Approach

Resumen

The study of Social Network Influence has attracted the interest of scientists. The wide variety of real-world applications of this area, such as viral marketing and disease analysis, highlights the relevance of designing an algorithm capable of solving the problem efficiently. This paper studies the Multiple Round Influence Maximization (MRIM) problem, in which influence is propagated in multiple rounds independently from possibly different seed sets. This problem has two variants: the non-adaptive MRIM, in which the advertiser needs to determine the seed sets for all rounds at the beginning, and the adaptive MRIM, in which the advertiser can select the seed sets adaptively based on the propagation results in the previous rounds. The main difficulty of this optimization problem lies in the computational effort required to evaluate a solution. Since each node is infected with a certain probability, the value of the objective function must be calculated through an influence diffusion model, which results in a computationally complex process. For this purpose, a metaheuristic algorithm based on Variable Neighborhood Search is proposed with the aim of providing high-quality solutions, being competitive with the state of the art.

Publicación
Variable Neighborhood Search
Isaac Lozano-Osorio
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
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
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.