Improving Critical Node Detection Using Neural Network-based Initialization in a Genetic Algorithm

作     者：Liu, Chanjuan Ge, Shike Chen, Zhihan Pei, Wenbin Zhu, Enqiang Mei, Yi Ishibuchi, Hisao 

作者机构：The School of Computer Science and Technology Dalian University of Technology 116024 China The Institute of Software Chinese Academy of Science Beijing100190 China The Institute of Computing Science and Technology Guangzhou University Guangzhou510006 China The School of Engineering and Computer Science Victoria University of Wellington Wellington6012 New Zealand The Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation Department of Computer Science and Engineering Southern University of Science and Technology Shenzhen518055 China 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Combinatorial optimization 

摘      要：The Critical Node Problem (CNP) is concerned with identifying the critical nodes in a complex network. These nodes play a significant role in maintaining the connectivity of the network, and removing them can negatively impact network performance. CNP has been studied extensively due to its numerous real-world applications. Among the different versions of CNP, CNP-1a has gained the most popularity. The primary objective of CNP-1a is to minimize the pair-wise connectivity in the remaining network after deleting a limited number of nodes from a network. Due to the NP-hard nature of CNP-1a, many heuristic/metaheuristic algorithms have been proposed to solve this problem. However, most existing algorithms start with a random initialization, leading to a high cost of obtaining an optimal solution. To improve the efficiency of solving CNP-1a, a knowledge-guided genetic algorithm named K2GA has been proposed. Unlike the standard genetic algorithm framework, K2GA has two main components: a pretrained neural network to obtain prior knowledge on possible critical nodes, and a hybrid genetic algorithm with local search for finding an optimal set of critical nodes based on the knowledge given by the trained neural network. The local search process utilizes a cut node-based greedy strategy. The effectiveness of the proposed knowledge-guided genetic algorithm is verified by experiments on 26 real-world instances of complex networks. Experimental results show that K2GA outperforms the state-of-the-art algorithms regarding the best, median, and average objective values, and improves the best upper bounds on the best objective values for eight real-world instances. Copyright © 2024, The Authors. All rights reserved.