Abstract
Several problems related to networks are based on the identification of certain nodes which can be relevant for different tasks: network security and stability, protein interaction, or social influence analysis, among others. These problems can be modeled with the Critical Node Detection Problem (CNDP). Given a network, the CNDP consists of identifying a set of p nodes whose removal minimizes the pairwise connectivity of the network. In this work, a Basic Variable Neighborhood Search (BVNS) algorithm is presented with the aim of generating high quality solutions in short computing times. The detailed experimental results show the performance of the proposed algorithm when comparing it with the state of the art method, emerging BVNS as a competitive algorithm for the CNDP.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.