A proposal for ranking through selective computation of centrality measures.

Area of Science:

• Network Science
• Computational Complexity
• Graph Theory

Background:

• Assessing complex network robustness involves analyzing structural changes after node or edge removal, typically ranked by centrality measures.
• Sequential recalculation of centralities after each node removal is computationally intensive for large networks.
• Initial centrality rankings may not accurately reflect network dynamics during sequential node elimination.

Purpose of the Study:

• To analyze the computational complexity of sequential centrality calculations in complex network analysis.
• To develop and present efficient strategies for reducing the computational burden of sequential centrality computations.
• To apply these findings to evaluate the robustness of synthetic and real-world networks.

Main Methods:

• Investigating the computational complexity of sequential node removal based on matrix function centrality measures.
• Developing and theoretically supporting two novel strategies to optimize sequential centrality computations.
• Applying the proposed methods to assess the robustness of various network structures.

Main Results:

• Provides the first computational complexity results for sequential centrality-based node removal using matrix functions.
• Introduces two strategies that significantly reduce the computational cost of sequential centrality calculations.
• Demonstrates the practical application of these methods in analyzing network robustness.

Conclusions:

• The sequential removal of nodes based on centrality measures presents significant computational challenges.
• The proposed strategies offer efficient solutions for analyzing complex network alterations and robustness.
• This research contributes to a more practical and accurate assessment of network resilience.