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

Resumen

Las Redes Sociales han estado en crecimiento continuo durante las últimas décadas. La enorme cantidad de información y aplicaciones ha llevado a un aumento en el interés de científicos y practicantes en el estudio de problemas relacionados con la influencia en Redes Sociales. Algunas de las aplicaciones del mundo real en esta área son marketing viral, análisis de enfermedades, detección de rumores, opinión pública, entre otras. En este artículo, se estudia el problema de Maximización de Influencia Multi-Ronda Adaptativa, en el cual la influencia de un conjunto de usuarios seleccionados (conjunto semilla) se propaga en múltiples rondas independientemente, con la posibilidad de seleccionar diferentes conjuntos semilla en cada ronda. Por lo tanto, los conjuntos semilla pueden ser seleccionados adaptativamente basándose en los resultados de propagación en las rondas previas. Dado que cada nodo se activa con cierta probabilidad, el número total de nodos activados debe calcularse a través de un Modelo de Difusión de Influencia (IDM), que resulta en un método computacionalmente bastante demandante. En esta investigación, se considera el Modelo de Cascada Independiente, que es uno de los IDMs más extendidos, y también el usado en el mejor método previo. Los practicantes destacan la relevancia de diseñar un algoritmo capaz de resolver eficientemente el problema. En esta investigación, el problema se aborda considerando la metodología de Búsqueda de Vecindarios Variables, proponiendo un método constructivo novedoso que se basa en probabilidad independiente basada en eventos, y un método de búsqueda local inteligente. Nuestro mejor algoritmo se compara con el método estado del arte, llamado AdaIMM, para analizar el rendimiento de la propuesta. Los resultados obtenidos muestran la superioridad de la propuesta tanto en calidad (propagación de influencia) como en tiempo de computación, obteniendo la mejor solución en todas las 40 instancias consideradas requiriendo la mitad del tiempo de computación que el mejor enfoque previo (28 s vs. 53 s). Adicionalmente, el mejor método previo presenta una desviación promedio de 24.23%. Estos resultados se confirman además mediante la realización de pruebas estadísticas no paramétricas.

Citar Esta Publicación

Lozano-Osorio, I., Sánchez-Oro, J. & Duarte, A. A variable neighborhood search approach for the adaptive multi round influence maximization problem. Soc. Netw. Anal. Min. 14, 165 (2024).