Deep Q-Learning Enhanced Variable Neighborhood Search for Influence Maximization in Social Networks

A social network consists of individuals and the relationships between them, which often influence each other. This influence can propagate behaviors or ideas through the network, a phenomenon known as influence propagation. This concept is crucial in applications like advertising, marketing, and public health. The influence maximization (IM) problem aims to identify key individuals in a social network who, when influenced, can maximize the spread of a behavior or idea. Given the NP-hard nature of IM, non-exact algorithms, especially metaheuristics, are commonly used. However, traditional metaheuristics like the variable neighborhood search (VNS) struggle with large networks due to vast solution spaces. This paper introduces DQVNS (Deep Q-learning Variable Neighborhood Search), which integrates VNS with deep reinforcement learning (DRL) to enhance neighborhood structure determination in VNS. By using DQVNS, we aim to achieve performance similar to population-based algorithms and utilize the information created step by step during the algorithm's execution. This adaptive approach helps the VNS algorithm choose the most suitable neighborhood structure for each situation and find better solutions for the IM problem. Our method significantly outperforms existing metaheuristics and IM-specific algorithms. DQVNS achieves a ۶۳% improvement over population-based algorithms on various datasets. The results of implementation on different real-world social networks of varying sizes demonstrate the superiority of this algorithm compared to existing metaheuristic, IM-specific algorithms, and network-specific measures.

Keywords:

Social Networks , Deep reinforcement learning , influence maximization , DQN