文献类型：期刊文献

英文题名：Late acceptance-based heuristic algorithms for identifying critical nodes of weighted graphs

作者：Zhou, Yangming[1,2];Wang, Zhe[1,2];Jin, Yan[3];Fu, Zhang-Hua[4,5]

机构：[1]East China Univ Sci & Technol, Key Lab Adv Control & Optimizat Chem Proc, Minist Educ, Shanghai 200237, Peoples R China;[2]East China Univ Sci & Technol, Sch Informat Sci & Engn, Shanghai 200237, Peoples R China;[3]Huazhong Univ Sci & Technol, Sch Comp Sci & Technol, Wuhan 430074, Peoples R China;[4]Shenzhen Inst Artificial Intelligence & Robot Soc, Shenzhen 518172, Peoples R China;[5]Chinese Univ Hong Kong, Inst Robot & Intelligent Mfg, Shenzhen 518172, Peoples R China

年份：2021

卷号：211

外文期刊名：KNOWLEDGE-BASED SYSTEMS

收录：;EI(收录号：20204509453888);WOS:【SCI-EXPANDED(收录号:WOS:000600316500014)】；

基金：We would like to thank the anonymous reviewers for their insightful comments that helped to considerably improve the paper. This research was supported by the Shanghai Sailing Program, China under Grant 19YF1412400, the National Natural Science Foundation of China under Grant 61903144, the Shenzhen Science and Technology Innovation Commission, China under Grant JCYJ20180508162601910, the Funding from the Shenzhen Institute of Artificial Intelligence and Robotics for Society, China under Grant 2019-INT003 and Open Project, and the Open Fund of Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University under Grant 2019MIP004.

语种：英文

外文关键词：Combinatorial optimization; Metaheuristics; Late acceptance strategy; Critical node problem; Node-weighted graph

摘要：Identifying critical nodes is an efficient way to analyze and apprehend the properties, structures, and functions of complex networks, which is a challenging NP-hard problem. This paper studies a node-weighted version of the critical node problem (NWCNP) that involves minimization of pairwise connectivity measure of a given node-weighted graph via the removal of a subset of nodes (i.e., critical nodes), subject to a budgetary constraint. In this paper, we present two effective iterated local search algorithms for NWCNP. Our proposed algorithms iterate through two complementary search procedures. A local search procedure adopting a constrained neighborhood and late acceptance strategy is employed to find a local optimum from a given starting solution. Then, a destructive-constructive perturbation procedure is used to escape from a local optimum. We conduct extensive computational experiments with two categories of 32 benchmark instances that reveal our proposed algorithms can achieve the best upper bounds for 28 instances and are highly competitive compared to baseline algorithm. In particular, our algorithms achieved better performance on the first category of instances with random weighting than that on the second category of instances with logarithmic weighting. We also investigate the influence of history length and perturbation coefficient on the performance of the proposed algorithms. (C) 2020 Elsevier B.V. All rights reserved.