Critical Node Detection for Enhanced Network Reliability: A Comparative Analysis Across Real-World Complex Networks

Identifying critical nodes in complex networks is crucial for assessing and improving the reliability and fault tolerance of systems across diverse domains, including communication, transportation, and infrastructure. While various critical node detection problems have been proposed, their practical implications for real-world reliability optimization still need to be explored. Most existing studies have focused on individual problems or specific types of networks, often lacking a comparative analysis across diverse real-world networks. This study conducts a comprehensive comparative analysis of three major problems: Maximizing the Number of Connected Components (MaxNum), Minimizing the size of the Largest Connected Component (MinMaxC), and the Critical Node Problem (CNP). Leveraging ten real-world networks from diverse domains, we investigate the similarities and differences between their optimal solution sets and evaluate how effectively common centrality metrics approximate them. Furthermore, a generalization of Isolating Centrality is proposed to overcome detected drawbacks. Our results reveal a high similarity (0.91) between the optimal node sets of MinMaxC and CNP, with PageRank centrality consistently showing strong alignment with these optimal critical node sets across a variety of network types. The study provides valuable insights for network reliability analysis, aiding the development of targeted strategies to enhance network stability and ensure reliable operation in crucial applications.