.png){kind=icon}
Return
Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2012.02.008.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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' subset of V of k > 0 nodes from a given graph G = (V,E) such that 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. (c) 2012 Elsevier Ltd. All rights reserved.
Keywords:
Critical node detection
Complex networks
Random graph
Simulated annealing
Population-based incremental learning
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
No organization information available
Cited Papers
ShareSaveShareSaveShareSave
A novel snoRNA (U73) is encoded within the introns of the human and mouse ribosomal protein S3a genes.png)
Gene
GeneIF0
PREAI
ShareSaveShareSaveShareSaveShareSave
View more