GRASP Heuristics for the stochastic weighted graph fragmentation problem

Abstract

Critical nodes play a major role in network connectivity. Identifying them is important to design efficient strategies to prevent malware or epidemics spread through a network. In this context, the Stochastic Weighted Graph Fragmentation Problem (SWGFP) is a combinatorial optimization problem that belongs to the N P − Complete class. Its objective consists in minimizing the impact of a random attack on a singleton, choosing appropiately a set of nodes to immunize given a restricted budget. In the SWGFP, it is assumed that the attack follows a known probability law and that it affects the whole connected component of the attacked node. In this thesis, a GRASP enriched with Path Relinking algorithm is developed to solve the SWGFP. Its performance is studied under three attack scenarios and compared with a GRASP variant that was previously developed in literature and with a Random heuristic for the problem that picks a set of nodes uniformly at random. Computational experiments show that the algorithm based on Independent Sets which is developed in this thesis, outperforms the other two, with lower expected loss scores and higher robustness.

Los nodos críticos juegan un rol fundamental en la conectividad de las redes. Su identificación es importante para el diseño de estrategias eficientes para prevenir que tanto un software malicioso como una epidemia se propaguen por la red. En este contexto, el Stochastic Weighted Graph Fragmentation Problem (SWGFP) es un problema de optimización combinatoria perteneciente a la clase de problemas NP−Completos. El objetivo consiste en miniminizar el impacto de un ataque aleatorio en un nodo de la red, seleccionando adecuadamente nodos a inmunizar con un presupuesto acotado. En el SWGFP se asume que el ataque sigue una ley de probabilidad conocida en los nodos, y que afecta a toda la componente conexa del nodo seleccionado. En esta tesis se desarrolla una solución GRASP enriquecida con Path-Relinking para abordar el SWGFP. Se estudia el rendimiento de la propuesta ante tres escenarios de ataque, en comparación con una variante de GRASP anteriormente desarrollada de la literatura y una heurística aleatoria o Random para el problema en la cual los nodos son elegidos al azar. Los experimentos computacionales muestran que el algoritmo basado en Conjuntos Independientes que se desarrolla en esta tesis, presenta un mejor desempeño que los dos restantes, con valores inferiores del número esperado de pérdidas y mayor robustez.