کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
473375 | 698787 | 2012 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem](/preview/png/473375.png)
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.
Journal: Computers & Operations Research - Volume 39, Issue 11, November 2012, Pages 2763–2775