期刊
SOFT COMPUTING
卷 23, 期 23, 页码 12729-12744出版社
SPRINGER
DOI: 10.1007/s00500-019-03824-8
关键词
Bi-objective critical node detection problems; NP-hardness; epsilon-Approximation; Decomposition-based multi-objective evolutionary algorithms; Mating pool; Replacement pool
资金
- National Outstanding Youth Talents Support Program [61822304]
- NSFC-Zhejiang Joint Fund for the Integration of Industrialization and Informatization [U1609214]
- National Natural Science Foundation of China [61673058]
- Foundation for Innovative Research Groups of the National Natural Science Foundation of China [61621063]
- Projects of Major International (Regional) Joint Research Program NSFC [61720106011]
- Paul and Heidi Brown Preeminent Professorship in Industrial and Systems Engineering, University of Florida
An effective way to analyze and apprehend structural properties of networks is to find 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 find 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 first prove the NP-hardness of this problem for general graphs and the existence of a polynomial algorithm for constructing the epsilon-approximated Pareto front for Bi-CNDPs on trees. Then different 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-epsilon C) are modified and applied to solve the proposed Bi-CNDP. Numerical experiments on sixteen famous benchmark problems with random and logarithmic weights are firstly conducted to assess different types of the mating pool and the replacement pool. Besides, computational results between two improved algorithms, i.e., I-MOEA/D and I-DMOEA-epsilon C, demonstrate that they behave differently on these instances and I-DMOEA-epsilon 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据