GA-Based Multipopulation Synergistic Gene Screening Strategy on Critical Nodes Detection
- 31 October 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Social Systems
- Vol. 11 (3) , 3839-3850
Abstract
Critical node detection (CND) is commonly used to detect nodes with a high impact on network robustness. It has been widely used in disease propagation, social networks, communications, and other fields. As a nondeterministic polynomial-time (NP)-complete problem, the efficiency of solving CND severely limits the scale of the available network. Fortunately, the evolutionary algorithm (EA) is an effective method to solve this problem. However, although EA improves the global search capability of the algorithm by preserving gene diversity, it also introduces many inferior genes, thus expanding the candidate solution space, reducing the search efficiency, and making it difficult to apply the pruning algorithm directly to its solution space. Hence, indirectly reducing the solution space of EA by deleting inferior genes is a feasible pruning method; however, the interaction of multiple genes affects the quality of CND solutions, making it a challenge to pick out inferior individual genes. Therefore, this work proposes a multipopulation synergistic gene screening algorithm based on the parallelism of EA and combined with Ensemble learning for identifying low-quality genes and removing them as a way of pruning the solution space of the algorithm and improving the search efficiency. The algorithm encodes all nodes in the graph as the gene pool of EA and treats a single population as a weak learner to screen the dominant genes in the gene pool and achieve fast pruning of EA’s solution space by integrating the dominant individuals in multiple populations. In this work, the experiments demonstrate the effectiveness of the proposed method and analyze the effect of different network structures on the algorithm.Keywords
Funding Information
- National Natural Science Foundation of China (62103374)
- Key Research and Development Projects in Zhejiang Province (2021C01117)
- National Key Research and Development Program of China (2018AAA0100800)
- Key Research and Development Program of Zhejiang (2022C01018)
- National Natural Science Foundation of China (U21B2001)
- National Natural Science Foundation of China (61973273)
- National Key Research and Development Program of China (2020YFB1006104)
This publication has 65 references indexed in Scilit:
- A novel method to evaluate node importance in complex networksPhysica A: Statistical Mechanics and its Applications, 2019
- GA-Based Q-Attack on Community DetectionIEEE Transactions on Computational Social Systems, 2019
- Computational methods for identifying the critical nodes in biological networksBriefings in Bioinformatics, 2019
- Differential Evolution: A survey of theoretical analysesSwarm and Evolutionary Computation, 2019
- The Critical Node Detection Problem in networks: A surveyComputer Science Review, 2018
- Ensemble learning: A surveyWIREs Data Mining and Knowledge Discovery, 2018
- Detecting Critical Nodes in Interdependent Power Networks for Vulnerability AssessmentIEEE Transactions on Smart Grid, 2013
- Cascade-based attack vulnerability on the US power gridSafety Science, 2009
- Optimal Design of Water Networks Using a Modified Genetic Algorithm with Reduction in Search SpaceJournal of Water Resources Planning and Management, 2008
- The human disease networkProceedings of the National Academy of Sciences, 2007