The critical node problem(CNP)aims to deal with critical node identification in a graph,which has extensive applications in many fields.Solving CNP is a challenging task due to its computational complexity,and it attr...The critical node problem(CNP)aims to deal with critical node identification in a graph,which has extensive applications in many fields.Solving CNP is a challenging task due to its computational complexity,and it attracts much attention from both academia and industry.In this paper,we propose a population-based heuristic search algorithm called CPHS(Cut Point Based Heuristic Search)to solve CNP,which integrates two main ideas.The first one is a cut point based greedy strategy in the local search,and the second one involves the functions used to update the solution pool of the algorithm.Besides,a mutation strategy is applied to solutions with probability based on the overall average similarity to maintain the diversity of the solution pool.Experiments are performed on a synthetic benchmark,a real-world benchmark,and a large-scale network benchmark to evaluate our algorithm.Compared with state-of-the-art algorithms,our algorithm has better performance in terms of both solution quality and run time on all the three benchmarks.展开更多
基金supported by the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant Nos.XDA0320000 and XDA0320300the National Natural Science Foundation of China under Grant No.61972063.
文摘The critical node problem(CNP)aims to deal with critical node identification in a graph,which has extensive applications in many fields.Solving CNP is a challenging task due to its computational complexity,and it attracts much attention from both academia and industry.In this paper,we propose a population-based heuristic search algorithm called CPHS(Cut Point Based Heuristic Search)to solve CNP,which integrates two main ideas.The first one is a cut point based greedy strategy in the local search,and the second one involves the functions used to update the solution pool of the algorithm.Besides,a mutation strategy is applied to solutions with probability based on the overall average similarity to maintain the diversity of the solution pool.Experiments are performed on a synthetic benchmark,a real-world benchmark,and a large-scale network benchmark to evaluate our algorithm.Compared with state-of-the-art algorithms,our algorithm has better performance in terms of both solution quality and run time on all the three benchmarks.
