GRASP Heuristics for the Stochastic Weighted Graph Fragmentation Problem

摘要

Vulnerability metrics play a key role nowadays in order to cope with natural disasters and deliberate attacks. The scientific literature is vast, sometimes focused on connectivity aspects in networks or cascading failures, among others. The Graph Fragmentation Problem (GFP) has its origin in epidemiology, and it represents the worst case analysis of a random attack. The contributions of this paper are three-fold. First, a valuable interplay between the GFP and a connectivity-based metric, called the Critical Node Detection (CND) problem, is here explored. Second, a novel combinatorial optimization problem is introduced. It is called Stochastic Weighted Graph Fragmentation Problem (SWGFP), and it is a generalization of the GFP. The node-importance is included in the model, as well as a level of network awareness from the attacker viewpoint. Finally, a novel GRASP (Greedy Randomized Adaptive Search Procedure) heuristic is proposed for the SWGFP. A faithful comparison with a previous heuristic shows its competitiveness.