The bi-objective critical node detection problem with minimum pairwise connectivity and cost: theory and algorithms

Abstract

An efective way to analyze and apprehend structural properties of networks is to fnd their most critical nodes. This paper studies a bi-objective critical node detection problem, denoted as Bi-CNDP. In this variant, we do not make any assumptions on the psychology of decision makers and seek to fnd a set of solutions which minimize the pairwise connectivity of the induced graph and the cost of removing these critical nodes at the same time. After explicitly stating the formulation of Bi-CNDP, we frst prove the NP-hardness of this problem for general graphs and the existence of a polynomial algorithm for constructing the 휀-approximated Pareto front for Bi-CNDPs on trees. Then diferent approaches of determining the mating pool and the replacement pool are proposed for the decomposition-based multi-objective evolutionary algorithms. Based on this, two types of decomposition-based multi-objective evolutionary algorithms (MOEA/D and DMOEA-휀C) are modifed and applied to solve the proposed Bi-CNDP. Numerical experiments on sixteen famous benchmark problems with random and logarithmic weights are frstly conducted to assess diferent types of the mating pool and the replacement pool. Besides, computational results between two improved algorithms, i.e., I-MOEA/D and I-DMOEA-휀C, demonstrate that they behave diferently on these instances and I-DMOEA-휀C shows better performance on the majority of test instances. Finally, a decision-making process from the perspective of minimizing the pairwise connectivity of the induced graph given a constraint on the cost of removing nodes is presented for helping decision makers to identify the most critical nodes for further protection or attack.