Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem

In this paper the problem of critical node detection (CNDP) is approached using population-based incremental learning (an estimation of distribution algorithm) and simulated annealing optimization algorithms using a combinatorial unranking-based problem representation. This representation is space-efficient and alleviates the need for any repair mechanisms. CNDP is a very recently proposed problem that aims to identify a vertex set V′⊆VV′⊆V of k>0k>0 nodes from a given graph G=(V,E)G=(V,E) such that G(V⧹V′)G(V⧹V′) has minimum pairwise connectivity. Numerous practical applications for this problem exist, including pandemic disease mitigation, computer security and anti-terrorism. In order to test the proposed heuristics 16 benchmark random graph structures are additionally proposed that utilize Erdos–Renyi, Watts–Strogatz, Forest Fire and Barabasi–Albert models. Each of these models presents different network characteristics, yielding variations in problem difficulty. The relative merits of the two proposed approaches are compared and it is found that the population-based incremental learning approach, using a windowed perturbation operator is able to outperform the proposed simulated annealing method.