A variable neighborhood search approach for the adaptive multi round influence maximization problem

Resumen

Social Networks have been in continuous growing during the last decades. The huge amount of information and applications has led to an increase in the interest of scientists and practitioners in the study of problems related to the influence in Social Networks. Some of the wide variety of real-world applications in this area are viral marketing, disease analysis, rumor detection, public opinion, among others. In this paper, the Adaptive Multi Round Influence Maximization problem is studied, in which the influence of a set of selected users (seed set) is propagated in multiple rounds independently, with the possibility of selecting different seed sets in each round. Therefore, seed sets can be adaptively selected based on the propagation results in the previous rounds. Since each node is activated with a certain probability, the total number of activated nodes must be calculated through an Influence Diffusion Model (IDM), which results in a rather computationally demanding method. In this research, the Independent Cascade Model is considered, which is one of the most extended IDMs, and also the one used in the best previous method. Practitioners highlight the relevance of designing an algorithm capable of efficiently solving the problem. In this research, the problem is addressed by considering the Variable Neighborhood Search methodology, proposing a novel constructive method that relies on independent probability based on events, and an intelligent local search method. Our best algorithm is compared with the state-of-the-art method, named AdaIMM, to analyze the performance of the proposal. The obtained results show the superiority of the proposal in both quality (influence spread) and computing time, obtaining the best solution in all the 40 instances considered requiring half of the computing time than the best previous approach (28 s vs. 53 s). Additionally, the best previous method presents an average deviation of 24.23%. These results are further confirmed by conducting non-parametric statistic tests.

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

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.