文献类型：期刊文献

英文题名：Memetic Search for Identifying Critical Nodes in Sparse Graphs

作者：Zhou, Yangming[1];Hao, Jin-Kao[2,3];Glover, Fred[4]

机构：[1]East China Univ Sci & Technol, Dept Comp Sci & Engn, Shanghai 200237, Peoples R China;[2]Univ Angers, Dept Comp Sci, F-49045 Angers, France;[3]Inst Univ France, F-75231 Paris, France;[4]Univ Colorado, Leeds Sch Business, Boulder, CO 80309 USA

年份：2019

卷号：49

期号：10

起止页码：3699

外文期刊名：IEEE TRANSACTIONS ON CYBERNETICS

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

基金：The work of Y. Zhou was supported by the China Scholarship Council (2014-2017). This paper was recommended by Associate Editor Y. S. Ong. (Corresponding author: Jin-Kao Hao.)

语种：英文

外文关键词：Complex networks; critical node problems (CNPs); heuristics; memetic search; sparse graph

摘要：Critical node problems (CNPs) involve finding a set of critical nodes from a graph whose removal results in optimizing a predefined measure over the residual graph. As useful models for a variety of practical applications, these problems are computationally challenging. In this paper, we study the classic CNP and introduce an effective memetic algorithm for solving CNP. The proposed algorithm combines a double backbone-based crossover operator (to generate promising offspring solutions), a component-based neighborhood search procedure (to find high-quality local optima), and a rank-based pool updating strategy (to guarantee a healthy population). Extensive evaluations on 42 synthetic and real-world benchmark instances show that the proposed algorithm discovers 24 new upper bounds and matches 15 previous best-known bounds. We also demonstrate the relevance of our algorithm for effectively solving a variant of the classic CNP, called the cardinality-constrained CNP. Finally, we investigate the usefulness of each key algorithmic component.