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

Yang Liu

doi:10.1109/TNSE.2024.3388994

2024-07-01

PRE

DOI：10.1109/TNSE.2024.3388994

原文链接

原文求助

摘要

En 中文

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.

Keyword:

Optimization

Genetic algorithms

Adaptive systems

Task analysis

Statistics

Sociology

Optics

Complex network

vital nodes identification

robustness

percolation transition