Vital Nodes Identification via Evolutionary Algorithm With Percolation Optimization in Complex Networks

Abstract

The connectivity and functionality of a network can be significantly influenced by vital nodes, a subset whose behaviors are pivotal in applications like misinformation suppression and epidemic containment. In this paper, we discuss the vital nodes identification problem from the perspective of percolation transition and combinatorial optimization, then present a novel Subsequence-optimized Genetic-Relationship-related (SGR) algorithm to target the most influential nodes efficiently and effectively via integrating the genetic algorithm and the Relationship Related (RR) strategy. Specifically, we first propose a subsequence optimization strategy to, on the one hand, constrain the search space of RR, and present an adaptive approach to accelerate the RR method, such that the solution on each subsequence can converge and be obtained rapidly. SGR iteratively runs such a process on randomly chosen subsequences and, on the other hand, maintains a diversity to enlarge the search space of the entire algorithm for the global optimum. Extensive experiments on 13 empirical networks from varied real-world scenarios demonstrate the method's remarkable superiority. In tasks such as network dismantling, synchronization control, and diffusion containment, our approach outperforms state-of-the-art methods, underscoring its efficacy in identifying influential nodes.