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.
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.
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:
- Point Centrality: Focused on individual nodes, further divided into local, iterative, and global metrics.
- Graph Centrality: Assessing the overall compactness or dominance of the network structure.
- 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