critical node detection

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

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…

An Extremal Optimization Approach to the Pairwise Connectivity Critical Node Detection Problem (2022)

The critical node detection is a computational challenging problem with several applications in biology, sociology, etc. Minimizing the pairwise connectivity after removing k critical nodes is one of the most studied problem. In this paper we approach this problem by using a standard Extremal Optimization algorithm, and another variant with incorporated network shifting mechanism.…

A Simple Genetic Algorithm for the Critical Node Detection Problem (2021)

The critical node detection problem describes a class of graph problems that involves identifying sets of nodes that influence a given graph metric. One variant of this problem is to find the nodes that – when removed from the graph – maximize the number of connected components in the remaining graph. This is an…

Critical Node Detection for Maximization of Connected Components: An Extremal Optimization Approach (2021)

Determining the critical nodes in a network given a certain network measure is a computational challenging problem that requires the design of adaptive and scalable algorithms. The number of connected components in a graph is an example of such a measure: in this case the nodes considered critical are those that, if removed from…

An Evolutionary Approach for Critical Node Detection in Hypergraphs. A Case Study of an Inflation Economic Network (2021)

Critical node detection is a crucial task in network analysis. In this article a new problem is proposed, the critical node detection in hypergraphs, which are a generalization of the ‘traditional’ graphs. A genetic algorithm is proposed to solve this problem and as an application an inflation dataset is transformed in a hypergraph and…