Solving the Minimum Positive Influence Dominating Set Problem in Social Networks Using Metaheuristics

Resumen

The rise of the internet and social networks has posed new challenges in studying people’s behavior on these platforms. People tend to trust or align with a small group of users, leading to the development of viral marketing techniques to effectively propagate information about products or services. This has led to the definition of problems related to social influence maximization/minimization and dominance sets. The Minimum Positive Influence Dominating Sets (MPIDS) problem involves finding a minimum cardinality dominance set to influence an entire social network. For a vertex to be influenced, at least half of its neighbors must be in the dominance set. Considering that MPIDS is an $mathcalNmathcalP$-hard problem, where exact approximations are impractical due to the size of social networks, this work proposes using Basic Variable Neighborhood Search (BVNS). Given an initial solution generated by a constructive method, this metaheuristic consists of two phases: a shaking and an improvement phase. In the shaking phase, the solution is modified by removing and reconstructing it using a randomized greedy approach. The improvement phase involves an innovative local search strategy based on generating holes, which removes the $δ$-neighborhood of a vertex to facilitate a greedy solution reconstruction.

Iván Penedo

Máster en Inteligencia Artificial

Iván Penedo se graduó en Ingeniería Informática e Ingeniería del Software en la Universidad Rey Juan Carlos en 2024. Actualmente trabaja como investigador centrado en problemas de análisis de redes sociales.

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.