Finding weaknesses in networks using Greedy Randomized Adaptive Search Procedure and Path Relinking. Issue 6 (17th February 2020)

• Record Type: Journal Article
• Authors: Pérez‐Peló, Sergio; Sánchez‐Oro, Jesús; Duarte, Abraham
• Other Names: Gonzalez‐Pardo Antonio guestEditor.; Tallón‐Ballesteros Antonio J. guestEditor.; Yin Hujun guestEditor.; Cortez Paulo guestEditor.; Bifet Albert guestEditor.
• Is Part Of: Expert systems. Volume 37:Issue 6(2020)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-02-17
• Subjects: critical nodes -- GRASP -- metaheuristic -- Path Relinking -- α‐separator problem; Expert systems (Computer science); 006.33
• DOI: 10.1111/exsy.12540
• Languages: English
• ISSNs: 0266-4720

Abstract

Abstract: In recent years, the relevance of cybersecurity has been increasingly evident to companies and institutions, as well as to final users. Because of that, it is important to ensure the robustness of a network. With the aim of improving the security of the network, it is desirable to find out which are the most critical nodes in order to protect them from external attackers. This work tackles this problem, named the α ‐separator problem, from a heuristic perspective, proposing an algorithm based on the Greedy Randomized Adaptive Search Procedure (GRASP). In particular, a novel approach for the constructive procedure is proposed, where centrality metrics derived from social network analysis are used as a greedy criterion. Furthermore, the quality of the provided solutions is improved by means of a combination method based on Path Relinking (PR). This work explores different variants of PR, also adapting the most recent one, Exterior PR, for the problem under consideration. The combination of GRASP + PR allows the algorithm to obtain high‐quality solutions within a reasonable computing time. The proposal is supported by a set of intensive computational experiments that show the quality of the proposal, comparing it with the most competitive algorithm found in the state of art.