An Improved Differential Evolution Framework Using Network Topology Information for Critical Nodes Detection

Critical nodes detection (CND) focuses on identifying the nodes that significantly impact the network's robustness and is applied in various fields such as power grids, communication networks, and disease spreading. However, detecting the critical nodes is a challenging nondeterministic polynom...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computational social systems 2023-04, Vol.10 (2), p.1-10
Main Authors: Yu, Shanqing, Wang, Yongqi, Li, Jiaxiang, Fang, Xu, Chen, Jinyin, Zheng, Ziwan, Fu, Chenbo
Format: Article
Language:English
Subjects:
Communication networks
Complex network
critical nodes detection (CND)
differential evolution (DE)
Evolutionary algorithms
Evolutionary computation
Genetic algorithms
Network topologies
Nodes
Polynomials
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Critical nodes detection (CND) focuses on identifying the nodes that significantly impact the network's robustness and is applied in various fields such as power grids, communication networks, and disease spreading. However, detecting the critical nodes is a challenging nondeterministic polynomial time complete (NP-complete) problem. One possible solution is using the evolutionary algorithm which has a high global search capability. However, the existing evolutionary algorithms for CND only focus on independent nodes, ignoring the underlying relationship among the nodes. Thus, in this work, we proposed a new topology-combined differential evolution framework called TDE to explore the possibility of improving the performance by fusing topology information, which designs individual genotypes through node degree, and new mutation and decoding-based selection operators are designed for these genotypes to use topology information effectively. The experiments on synthetic and real networks show that it is feasible to improve the search capability of the algorithm by fusing node degree information.
ISSN:2329-924X
2373-7476
DOI:10.1109/TCSS.2022.3217071