arrow
返回

The bi-objective critical node detection problem

delete2018-03-01
delete28
delete
OA
AI
M
Mario Ventresca *
K
Kyle Robert Harrison
B
Beatrice Ombuki-Berman
DOI:10.1016/j.ejor.2017.08.053delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

En 中文
Identifying critical nodes in complex networks has become an important task across a variety of application domains. The Critical Node Detection Problem (CNDP) is an optimization problem that aims to minimize pairwise connectivity in a graph by removing a subset of K nodes. Despite the CNDP being recognized as a bi-objective problem, until now only single-objective problem formulations have been proposed. In this paper, we propose a bi-objective version of the problem that aims to maximize the number of connected components in a graph while simultaneously minimizing the variance of their cardinalities by removing a subset of K nodes. We prove that our bi-objective formulation is distinct from the CNDP, despite their common motivation. Finally, we give a brief comparison of six common multi objective evolutionary algorithms using sixteen common benchmark problem instances, including for the node-weighted CNDP. We find that of the examined algorithms, NSGAII generally produces the most desirable approximation fronts. (C) 2017 Elsevier B.V. All rights reserved.
Keyword:
Networks
Critical node detection
Multi-objective
Evolutionary algorithms
AI总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

European Journal of Operational Research 封面图
European Journal of Operational Research
IF:
6
论文数:
2.2W
被引数:
8.1W

机构

Purdue University System 封面图
Purdue University System
学者数:
4.0W
论文数: 3.6W
被引数: 4.7W
U
university of pretoria
学者数:
488
论文数: 251
被引数: 4.8K
P
Purdue University
学者数:
2.0K
论文数: 710
被引数: 1.5W
学者 查看更多机构
引用论文

引用论文

On New Approaches of Assessing Network Vulnerability: Hardness and Approximation
err2012-04-01
err114
errOAAI
errDinh, Thang N.; Xuan, Ying; Thai, My T.; Pardalos, Panos M.; Znati, Taieb
err分享
err收藏
Detecting critical nodes in sparse graphs
err2009-07-01
err292
PREAI
errArulselvan, Ashwin; Commander, Clayton W.; Elefteriadou, Lily; Pardalos, Panos M.
err分享
err收藏
First Report of Zoonotic Genotype of Giardia duodenalis in Mussels (Mytilus edulis) from Patagonia Argentina来自阿根廷巴塔哥尼亚的贻贝 (Mytilus edulis) 中 十二指肠贾第鞭毛虫 的人畜共患病基因型的第一份报告
err2021-02-01
err0
errOAAI
errClaudia Torrecillas; María Angélica Fajardo; María Alejandra Córdoba; Marco Sánchez; Ivana Mellado; Betiana Garrido; Isabel Aleixandre-Górriz; Paula Sánchez-Thevenet; David Carmena
err分享
err收藏
Complexity of the critical node problem over trees
err2011-12-01
err64
errOAAI
errDi Summa, Marco; Grosso, Andrea; Locatelli, Marco
err分享
err收藏
Effects of Different Processing Methods of Coffee Arabica on Colour, Acrylamide, Caffeine, Chlorogenic Acid, and Polyphenol Content
err2022-10-21
err0
errOAAI
errOlga Cwiková; Tomas Komprda; Viera Šottníková; Zdeněk Svoboda; Jana Simonová; Jan Slováček; Miroslav Jůzl
err分享
err收藏
学者 查看更多内容