A Survey on Centrality Metrics and Their Implications in Network Resilience

Zelin Wan, Yash Mahajan, Beom Woo Kang, Terrence J. Moore, Jin-Hee Cho

Introduction: The Evolution of Network Science

Identifying vital nodes within a network is a fundamental challenge across numerous scientific domains. From the early foundations of graph theory laid by Leonhard Euler in the 1730s to the formal definition of "Network Science" by the US NRC in 2006, the field has expanded into a multi-disciplinary powerhouse.

Timeline of the evolution of graph theory and network science across various disciplines.

Despite this long history, a significant gap remains: while hundreds of centrality metrics have been developed over decades, researchers often default to "classic" measures like Degree or Betweenness without a rigorous justification for their specific application. This paper addresses this gap by providing a massive-scale survey of over 60 centrality metrics and evaluating their impact on network resilience—the ability of a system to maintain connectivity under targeted attack.

Diverse Applications of Centrality

Centrality metrics are not one-size-fits-all. Their utility varies significantly depending on the domain-specific goals, whether it is measuring influence in social groups, identifying vital controllers in chemical processes, or detecting central nodes in biological networks.

Summary of disciplines and their specific applications of network centrality and analysis.

As shown in the table above, the application of these metrics spans from Psychiatry to Computer Science. The lack of a standardized framework for choosing metrics across these diverse fields often leads to sub-optimal analysis of network vulnerabilities. This survey aims to move beyond popularity, providing a rigorous comparison of how different metrics impact resilience across various topologies.

Methodology: Categorization and Attack Simulation

The authors categorize the surveyed metrics into three primary types:

  1. Point Centrality: Focused on individual nodes, further divided into local, iterative, and global metrics.
  2. Graph Centrality: Assessing the overall compactness or dominance of the network structure.
  3. Group Selection Metrics: Strategies for identifying sets of nodes that collectively maximize impact, such as "Degree Punishment" to avoid redundant targeting of adjacent high-degree nodes.

To test these metrics, the study simulated two distinct attack vectors on four real-world datasets (UCI Social, Rocketfuel, URV Email, and EU Email):

  • Non-infectious Attacks: Surgical strikes (e.g., hardware failures or DoS attacks) where nodes are removed based on their centrality rank.
  • Infectious Attacks: Using the SIR (Susceptible-Infected-Removed) model to simulate spreading phenomena like malware outbreaks or viral social trends.

The primary performance metric was the Size of the Giant Component, representing the largest remaining connected portion of the network after a percentage of nodes are removed.

Key Findings on Network Resilience

The experimental results highlight several critical insights into how networks fail and how they can be defended:

  • The Power of Bridges: To effectively dissolve a network, targeting "bridges" via metrics like Betweenness or GDSP (Generalized Degree and Shortest Paths) is far more effective than targeting locally dense clusters. Local importance often fails to translate to global network fragmentation.
  • The 40% Threshold: Across various topologies, networks typically begin to collapse entirely once approximately 40% of the most central nodes are removed. This suggests a common structural vulnerability in many real-world systems.
  • Infection Dynamics: In infectious scenarios, the initial seed's centrality is less critical than in non-infectious attacks. Once an infection begins, its inherent spreading power tends to dominate the network, regardless of the starting point's rank.
  • Density as a Double-Edged Sword: Dense networks are highly vulnerable to infectious spread but remarkably resilient to non-infectious node removal, requiring a massive percentage of removals before the Giant Component breaks apart.
  • Computational Trade-offs: While global metrics offer high precision, their $O(n^3)$ complexity often makes them impractical for modern massive-scale networks. This explains why simpler $O(n+m)$ metrics like Degree remain the industry standard despite their limitations.

Conclusion and Future Outlook

This survey underscores that network resilience is highly dependent on both topology and the nature of the threat (infectious vs. non-infectious). While current metrics provide a strong foundation for understanding connectivity, the authors suggest that future research must pivot toward dynamic networks, where centrality shifts over time, and focus on "controllability"—the ability of a node to dictate the state of the entire system rather than just its connectivity.

Summary updated

Abstract

Centrality metrics have been studied in the network science research. They have been used in various networks, such as communication, social, biological, geographic, or contact networks under different disciplines. In particular, centrality metrics have been used in order to study and analyze targeted attack behaviors and investigated their effect on network resilience. Although a rich volume of centrality metrics has been developed from 1940s, only some centrality metrics (e.g., degree, betweenness, or cluster coefficient) have been commonly in use. This paper aims to introduce various existing centrality metrics and discusses their applicabilities in various networks. In addition, we conducted extensive simulation study in order to demonstrate and analyze the network resilience of targeted attacks using the surveyed centrality metrics under four real network topologies. We also discussed algorithmic complexity of centrality metrics surveyed in this work. Through the extensive experiments and discussions of the surveyed centrality metrics, we encourage their use in solving various computing and engineering problems in networks.
BibTeX
@article{wan2021survey,
  author = {Zelin Wan and Yash Mahajan and Beom Woo Kang and Terrence J. Moore and Jin-Hee Cho},
  title = {{A Survey on Centrality Metrics and Their Implications in Network Resilience}},
  journal = {IEEE Access},
  year = {2021},
  doi = {10.1109/access.2021.3094196},
}
Figure