On the sensitivity of centrality metrics

Area of Science:

• Network science
• Graph theory
• Computational complexity

Background:

• Centrality metrics are crucial for understanding network topology.
• The impact of minor topological changes on centrality vector norms is largely unknown.
• Efficiently updating centrality measures after network alterations could yield significant computational savings.

Purpose of the Study:

• To investigate the effects of small topological alterations on network centrality metrics.
• To determine if centrality calculations can be avoided after minor network changes.
• To compare the robustness of Degree, Eigenvector, and Katz centralities.

Main Methods:

• Formalized the concept of network centrality.
• Simulated network topology alterations using Uniform and Best Connected probabilistic failure models.
• Analyzed the impact of node deletions on Degree, Eigenvector, and Katz centrality.

Main Results:

• Degree centrality exhibited small variations in response to minor topological changes, irrespective of graph features.
• Eigenvector and Katz centralities demonstrated high sensitivity to topological alterations.
• Specific graph features can lead to catastrophic effects on Eigenvector and Katz centralities due to small topology changes.

Conclusions:

• Degree centrality is a robust measure against minor network perturbations.
• Eigenvector and Katz centralities are sensitive to network topology changes, potentially requiring recalculation.
• Understanding centrality metric sensitivity is key for efficient network analysis and management.