The bi-objective critical node detection problem

Loading...
Thumbnail Image

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.