Late acceptance-based heuristic algorithms for identifying critical nodes of weighted graphs

摘要

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.