A Multi-Objective Evolutionary Framework for Critical Node Detection in Social Networks

Subject Areas : Computer Engineering

Seyed Naghi Seyedaghaee-Rezaee ^{1 *} , Ali Broumandnia ² , Reza Tavakkoli-Moghaddam ³

1 - Department of Computer Engineering, ST.C., Islamic Azad University, Tehran, Iran.
2 - Department of Computer Engineering, ST.C., Islamic Azad University, Tehran, Iran.
3 - School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

Received: 2025-07-19 Accepted : 2025-10-01 Published : 2025-10-01

Keywords: social network, critical node detection, differential evolution, optimization,

Abstract :

This paper presents a novel hybrid algorithm that integrates Enhanced Critical Node Detection (ECND) with the Parallel Cell Coordinate System-based Adaptive Cross-Generation Differential Evolution (pccsACGDE) to identify critical nodes in social networks. ECND provides an effective pre-evaluation of node importance using classical centrality measures, while pccsACGDE performs a multi-objective evolutionary search to optimize the selection of node subsets that maximize network disconnection and minimize component sizes after removal. The algorithm uses a discretized PCCS grid to evaluate solution quality and guide mutation strategies via cross-generational operators (Neighborhood-Based Cross-Generation (NCG) and Population-Based Cross-Generation (PCG). To assess its effectiveness and robustness, the proposed method is evaluated on 24 artificial and real-world network datasets. Experimental results demonstrate that the hybrid method outperforms traditional centrality-based approaches, achieving a superior balance between network fragmentation and component distribution. This makes the method a powerful and adaptable solution for critical node detection across various domains.

 

References:

Albert, Réka, and Albert-László Barabási. "Statistical mechanics of complex networks." Reviews of modern physics 74.1 (2002): 47.
Crucitti, Paolo, Vito Latora, and Massimo Marchiori. "Model for cascading failures in complex networks." Physical Review E 69.4 (2004): 045104.
Freeman, Linton. C. Centrality in social networks: Conceptual clarification. Social Networks, 1979. 1(3), 215–239.
Page, Lawrence, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: Bringing order to the web. Stanford infolab, 1999.
Ugurlu, Onur. "Comparative analysis of centrality measures for identifying critical nodes in complex networks." Journal of Computational Science 62 (2022): 101738.
Saxena, Akrati, and Sudarshan Iyengar. "Centrality measures in complex networks: A survey." arXiv preprint arXiv:2011.07190 (2020).
Deb, Kalyanmoy, et al. "A fast and elitist multiobjective genetic algorithm: NSGA-II." IEEE transactions on evolutionary computation 6.2 (2002): 182-197.
Zhang, Hai-Fei, et al. "Three-stage multi-modal multi-objective differential evolution algorithm for vehicle routing problem with time windows." Intelligent Data Analysis 28.2 (2024): 485-506.
Béczi, Eliézer, and Noémi Gaskó. "Approaching the bi-objective critical node detection problem with a smart initialization-based evolutionary algorithm." PeerJ Computer Science 7 (2021): e750.
Zhang, Lei, et al. "An interactive co-evolutionary framework for multi-objective critical node detection on large-scale complex networks." IEEE Transactions on Network Science and Engineering 10.3 (2023): 1722-1735.
Nematalla Mottaki, Homayun Motameni, and Hosein Mohamadi. "Multi-objective optimization for coverage aware sensor node scheduling in directional sensor networks." Journal of Applied Dynamic Systems and Control 4.1 (2021): 43-52.
Ajam, Leila, Ali Nodehi, and Hosein Mohamadi. "A Genetic-based algorithm to solve priority-based target coverage problem in directional sensor networks." Journal of Applied Dynamic Systems and Control 4.1 (2021): 89-96.
Seyed Naghi Seyedaghaee, Ali Broumandnia, Reza Tavakkoli-Moghadam. Adaptive Multiobjective Differential Evolution Based on Parallel Cell Coordinate System. Journal of Cluster computing, Springer. (2025).
Ajam, Leila, and Seyed Naghi Seyedaghaee. "Enhanced Critical Node Detection in Social Networks." Computing and Informatics 40.6 (2021): 1422-1443.
Arulselvan, Ashwin, et al. "Detecting critical nodes in sparse graphs." Computers & Operations Research 36.7 (2009): 2193-2200.
Zhou, Yangming, Jin-Kao Hao, and Fred Glover. "Memetic search for identifying critical nodes in sparse graphs." IEEE transactions on cybernetics 49.10 (2018): 3699-3712.
Liu, Chanjuan, et al. "Improving Critical Node Detection Using Neural Network-based Initialization in a Genetic Algorithm." arXiv preprint arXiv:2402.00404 (2024).
Ventresca, Mario, Kyle Robert Harrison, and Beatrice M. Ombuki-Berman. "An experimental evaluation of multi-objective evolutionary algorithms for detecting critical nodes in complex networks." European Conference on the Applications of Evolutionary Computation. Cham: Springer International Publishing, 2015.
Ding, Hongyuan, et al. "Research on Combining Pattern Mining and Evolutionary Algorithm for Critical Node Detection Problems." International Journal of Frontiers in Engineering Technology 4.4 (2022).
Wang, Xue-Guang. "An algorithm for critical nodes problem in social networks based on owen value." The Scientific World Journal 2014.1 (2014): 414717.