Conjunto Dominante de Influencia Positiva Mínima (MPIDS)

Descripción del Problema

Este proyecto se centra en el problema del Conjunto Dominante de Influencia Positiva Mínima (MPIDS). Dado un grafo no dirigido $G = (V, E)$, un Conjunto Dominante de Influencia Positiva (PIDS) se define como un subconjunto de vértices $D \subseteq V$ tal que, para cualquier vértice $v \in V$, al menos la mitad de sus vecinos son miembros de $D$. Formalmente, esta condición se expresa como $ |D \cap N(v)| \geq |N(v)|/2 \ \forall v \in V$. El objetivo del problema MPIDS es determinar un PIDS con la mínima cardinalidad posible. Lin et al. [1] definieron formalmente este problema, y Wang et al. [2] demostraron que es un problema $\mathcal{NP}$-difícil para grafos generales. En este marco, una red social se modela formalmente como un grafo no dirigido $G=(V, E)$, donde $V$ representa a los usuarios y $E$ representa las conexiones. Una arista $(u,v) \in E$ indica una relación y un potencial de influencia entre los usuarios $u$ y $v$. $N(v)$ denota el conjunto de vértices adyacentes a $v$, es decir, ${u \in V : (u,v) \in E}$.

Contexto Industrial

Los principios de la influencia social, y por extensión el problema MPIDS, tienen importantes implicaciones industriales más allá de la investigación académica. En el marketing viral, comprender y aprovechar la influencia social permite a las empresas identificar a individuos clave que pueden difundir eficientemente información sobre productos o promover su adopción, lo que lleva a campañas más rentables. En la salud pública, la identificación de conjuntos dominantes mínimos puede ayudar a dirigir estratégicamente intervenciones (por ejemplo, campañas de vacunación o mensajes de concienciación sanitaria) para controlar eficazmente los brotes de enfermedades. Para las plataformas de e-learning, la identificación de usuarios influyentes puede mejorar los sistemas de recomendación, sugiriendo contenido relevante o compañeros para el aprendizaje colaborativo. Además, estos conceptos son vitales en campos como la lucha contra el terrorismo o la prevención del delito, donde comprender la propagación de la influencia puede ayudar a desmantelar redes maliciosas al atacar a individuos clave.

Desafíos Comunes

Una limitación significativa en la resolución de problemas MPIDS surge de la escala sustancial de las redes sociales contemporáneas. El gran tamaño de estas redes a menudo hace que la aplicación directa de modelos matemáticos sea computacionalmente intratable, impidiendo ocasionalmente la identificación de una solución factible dentro de plazos razonables. Por ejemplo, el modelo de programación lineal entera para MPIDS, según lo definido por Lin et al. [1], se vuelve inviable para grafos grandes debido al número masivo de variables binarias asignadas a cada vértice. Esta barrera computacional requiere el desarrollo de enfoques de solución más escalables, ya que los métodos exactos no pueden proporcionar soluciones oportunas o incluso ninguna solución para instancias de redes sociales del mundo real.

Enfoques de Resolución

Dados los desafíos computacionales, la literatura existente propone varias metodologías voraces, heurísticas y metaheurísticas para abordar el problema MPIDS.

Enfoques Voraces y Heurísticos

Wang et al. [2] fueron pioneros en un algoritmo voraz que, en cada iteración, selecciona el vértice con la influencia más amplia. Raei et al. [5] lo mejoraron introduciendo el parámetro cover-degree para priorizar vértices. Pan [4] avanzó aún más las estrategias voraces con el Algoritmo Voraz Rápido (FGA), que optimiza la propagación de la influencia a través de la exploración de vecindades y la dominancia priorizada. El Algoritmo Voraz Mejorado (IGA-PIDS) de Bouamama et al. [3], basado en FGA, incorpora los parámetros need-degree y cover-degree para una priorización mejorada, junto con una poda inicial de la red y un proceso de cribado final.

Enfoques Metaheurísticos

El campo también se beneficia de diversos algoritmos metaheurísticos. Lin et al. [1] presentaron el algoritmo memético ILPMA, que combina la formulación matemática con una Búsqueda Tabú para optimizaciones locales. Akbay y Blum [6] propusieron el algoritmo Construir, Fusionar, Resolver y Adaptar (CMSA), que genera y mezcla soluciones a través de estructuras adaptativas. Una variante auto-adaptativa lo refinó ajustando dinámicamente el número de soluciones generadas en cada iteración [7]. El algoritmo Iterated Carousel Greedy (ICG) [8] reemplazó la Búsqueda Tabú con un proceso iterativo de destrucción y reconstrucción del conjunto dominante.

Más recientemente, el algoritmo FastPIDS de Sun et al. [9] ha surgido como una solución de vanguardia. Introduce varias reglas de reducción para la generación de conjuntos dominantes y reutiliza la función need-degree. FastPIDS integra una construcción voraz utilizando un criterio híbrido con una búsqueda local basada en el intercambio de vértices, complementado por un mecanismo de “juicio de satisfacción de dos niveles” (TLSJ). Este mecanismo TLSJ aprovecha dos proposiciones para discernir qué conjuntos dominantes parciales son prometedores y cuáles no para añadir nuevos vértices a este conjunto utilizando la heurística híbrida. El algoritmo FastPIDS es actualmente el algoritmo de mejor rendimiento según la literatura.

Propuestas

Una propuesta novedosa introducida en este trabajo para la mejora de soluciones es la Búsqueda Local de Perforación (Piercing Local Search - PLS). Este método está diseñado para eliminar estratégicamente vértices de una región localizada de la solución actual, creando un “agujero”, y luego reconstruir inteligentemente la solución para encontrar potencialmente un conjunto dominante más pequeño, pero aún factible.

La PLS opera iterativamente: considera sistemáticamente cada vértice en el conjunto dominante actual $D$ como un potencial “centro” para una operación de Perforación (Pierce). Esta operación de Perforación elimina recursivamente el vértice central y un conjunto de sus vecinos hasta una profundidad especificada $\delta$, creando deliberadamente un “agujero” en la solución. Tras esta fase de destrucción, la solución incompleta se Reconstruye utilizando un criterio voraz, asegurando la factibilidad. Finalmente, se aplica un procedimiento RemoveRedundant para optimizar aún más la solución eliminando vértices superfluos mientras se mantiene la factibilidad. Si se encuentra una solución mejorada (es decir, una con una cardinalidad menor), el proceso se reinicia, de lo contrario, continúa hasta que no se observen más mejoras o se alcance un tiempo de ejecución máximo.

Además de este novedoso procedimiento de búsqueda local, se han estudiado varias metaheurísticas para este problema.

Greedy Randomized Adaptive Search Procedure (GRASP)

Esta metaheurística de inicio múltiple implica un proceso iterativo de construcción de una solución voraz aleatorizada y su posterior mejora mediante una búsqueda local. La fase de construcción a menudo incluye una “lista de candidatos restringidos” (RCL) de la que se seleccionan elementos aleatoriamente, introduciendo una forma de “perforación” o interrupción selectiva de las elecciones voraces para explorar soluciones diversas. [10]

Basic Variable Neighborhood Search (BVNS)

Como se describe, esta metaheurística explora sistemáticamente diferentes estructuras de vecindad. Su fase de “agitación” (shaking), que sirve para perturbar la solución actual y escapar de los óptimos locales, implica una “perforación” controlada mediante la eliminación de un número específico de nodos (determinado por el parámetro $k$) de la solución, creando agujeros que luego son reconstruidos inteligentemente.

Iterated Greedy (IG)

Este algoritmo opera a través de un ciclo iterativo de destrucción y reconstrucción. Una porción de la solución actual es “perforada” o destruida eliminando elementos, seguida de una fase constructiva que reconstruye la solución. Opcionalmente, se puede aplicar una búsqueda local después de la reconstrucción para refinar aún más la solución perturbada.

Referencias

[1] Lin, G., Guan, J., Feng, H.: An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks. Physica A: Statistical Mechanics and its Applications 500, 199–209 (Jun 2018). https://doi.org/10.1016/j.physa.2018.02.119 [2] Wang, F., Du, H., Camacho, E., Xu, K., Lee, W., Shi, Y., Shan, S.: On positive influence dominating sets in social networks. Theoretical Computer Science 412(3), 265–269 (Jan 2011). https://doi.org/10.1016/j.tcs.2009.10.001 [3] Bouamama, S., Blum, C.: An improved greedy heuristic for the minimum positive influence dominating set problem in social networks. Algorithms 14(3), 79 (Feb 2021). https://doi.org/10.3390/a14030079 [4] Pan, J., Bu, T.M.: A fast greedy algorithm for finding minimum positive influence dominating sets in social networks. In: IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). p. 360–364. IEEE (Apr 2019). https://doi.org/10.1109/infcomw.2019.8845129 [5] Raei, H., Yazdani, N., Asadpour, M.: A new algorithm for positive influence dominating set in social networks. In: 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. p. 253–257. IEEE (Aug 2012). https://doi.org/10.1109/asonam.2012.51 [6] Akbay, M.A., Blum, C.: Application of cmsa to the minimum positive influence dominating set problem. In: Artificial Intelligence Research and Development, pp. 17–26. IOS Press (Oct 2021). https://doi.org/10.3233/faia210112 [7] Akbay, M.A., López Serrano, A., Blum, C.: A self-adaptive variant of CMSA: Application to the minimum positive influence dominating set problem. International Journal of Computational Intelligence Systems 15(1) (Jul 2022). https://doi.org/10.1007/s44196-022-00098-1 [8] Shan, Y., Kang, Q., Xiao, R., Chen, Y., Kang, Y.: An iterated carousel greedy algorithm for finding minimum positive influence dominating sets in social networks. IEEE Transactions on Computational Social Systems 9(3), 830–838 (Jun 2022). https://doi.org/10.1109/tcss.2021.3096247 [9] Sun, R., Wu, J., Jin, C., Wang, Y., Zhou, W., Yin, M.: An efficient local search algorithm for minimum positive influence dominating set problem. Computers & Operations Research 154, 106197 (Jun 2023). https://doi.org/10.1016/j.cor.2023.106197 [10] Penedo, I., Lozano-Osorio, I., Sánchez-Oro, J., Cordón, O.: Resolución del problema de conjunto dominante de influencia positiva mínima en redes sociales mediante metaheurísticas. XVI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (2025). https://openreview.net/forum?id=oKfvNtHU7c

Agradecimientos

Los autores agradecen el apoyo de la Comunidad Autónoma de Madrid (grant ref. TEC-2024/COM-404), el Ministerio de Economía y Competitividad (grant ref. PID2021-125709OA-C22), y el Ministerio para la Transformación Digital y de la Función Pública (Cátedra ENIA AI4DDS, grant ref. TSI-100930-2023-3).