Balancing Speed and Accuracy in Influence Maximization: A Reinforcement Learning Solution

Influence maximization involves selecting an optimal subset of nodes within a graph to activate as many nodes as possible in a network. This approach is categorized as non-polynomial time, and no specific algorithm is currently available to run efficiently within a reasonable time frame, especially for large-scale networks. Numerous methods have been introduced to resolve this challenge, including greedy algorithms, structural heuristics, and metaheuristic approaches. Although greedy algorithms and their improved versions achieve high accuracy, they often suffer from poor scalability and slow execution times on large graphs. In contrast, structural methods offer faster computation but at the cost of reduced accuracy. Metaheuristic algorithms, while promising, face difficulties in balancing speed and accuracy due to the expansive search space inherent in complex social networks. This study introduces a novel method that leverages Q-learning, a reinforcement learning technique, to optimize influence maximization. The proposed method narrows down the search space by focusing on high-degree influential nodes. It dynamically updates the Q-table by assigning rewards and penalties based on the nodes’ impact during influence propagation, modeled using the Independent Cascade framework. This approach effectively balances exploration and exploitation, enabling the identification of a highly influential seed set with improved efficiency. Experiments conducted on various real-world datasets show that the Q-learning-based method significantly reduces execution time compared to genetic, particle swarm optimization, random, degree centrality, and K-shell algorithms while achieving higher influence spread in most cases. These results underscore the promise of reinforcement learning techniques in addressing complex network optimization problems such as influence maximization.