A Pseudo-Deterministic Noisy Extremal Optimization algorithm for the pairwise connectivity Critical Node Detection Problem

Logic Journal of the IGPL (forthcoming)
  Copy   BIBTEX

Abstract

The critical node detection problem is a central task in computational graph theory due to its large applicability, consisting in deleting $k$ nodes to minimize a certain graph measure. In this article, we propose a new Extremal Optimization-based approach, the Pseudo-Deterministic Noisy Extremal Optimization (PDNEO) algorithm, to solve the Critical Node Detection variant in which the pairwise connectivity is minimized. PDNEO uses an adaptive pseudo-deterministic parameter to switch between random nodes and articulation points during the search, as well as other features, such as noise induction to preserve diversity, greedy search to better exploit the search space and a greater search space exploration mechanism. Numerical experiments on synthetic and real-world networks show the effectiveness of the proposed algorithm compared with existing methods.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,991

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2024-05-22

Downloads
2 (#1,817,687)

6 months
2 (#1,259,303)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references