A comparative analysis of approaches to network-dismantling

Area of Science:

• Network Science
• Complex Systems Analysis
• Computational Network Theory

Background:

• Estimating and improving network robustness is vital across diverse fields like bioinformatics and transportation.
• Numerous network dismantling methods exist, but the state-of-the-art is fragmented across various publications and datasets.
• A comprehensive benchmark is needed to clarify the performance of existing network robustness estimation techniques.

Purpose of the Study:

• To conduct the largest benchmark analysis of network dismantling methods to date.
• To compare the performance and execution time of 13 different network dismantling algorithms.
• To provide a reference for selecting appropriate network dismantling methods based on network characteristics, accuracy needs, and computational constraints.

Main Methods:

• Reimplementation and comparative analysis of 13 network dismantling algorithms.
• Testing on 12 distinct types of random networks (e.g., Erdős-Rényi, Barabási-Albert, Watts-Strogatz) with varied generation parameters.
• Evaluation of algorithm performance based on node rankings, solution quality, and execution time, validated on real-world networks.

Main Results:

• Many established network metrics (over 20 years old) are often outperformed by other methods.
• Recently developed techniques show strong performance but are frequently specialized to specific network types.
• Analysis reveals significant variation in competitor similarity based on induced node rankings.

Conclusions:

• The study provides a comprehensive comparison of network dismantling methods, highlighting their strengths and weaknesses.
• Findings suggest that no single method universally dominates across all network types and performance criteria.
• This research serves as a crucial reference for researchers and practitioners needing to select optimal network dismantling strategies.