The bi-objective critical node detection problem
Loading...
Date
Authors
Ventresca, Mario
Harrison, Kyle Robert
Ombuki-Berman, Beatrice M.
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
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.
Description
Keywords
Evolutionary algorithms, Problem formulation, Benchmark-problem instances, Connected component, Critical node detections, Pairwise connectivities, Optimization problems, Multi-objective, Networks
Sustainable Development Goals
Citation
Ventresca, M., Harrison, K.R. & Ombuki-Berman, B.M. 2018, 'The bi-objective critical node detection problem', European Journal of Operational Research, vol, 265, no. 3, pp. 895-908.