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

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.