A comparative analysis of approaches to network-dismantling

Sebastian Wandelt, Xiaoqian Sun, Daozhong Feng, Massimiliano Zanin, Shlomo Havlin

Research output: Contribution to journalArticle

20 Citations (Scopus)
5 Downloads (Pure)

Abstract

Estimating, understanding, and improving the robustness of networks has many application areas such as bioinformatics, transportation, or computational linguistics. Accordingly, with the rise of network science for modeling complex systems, many methods for robustness estimation and network dismantling have been developed and applied to real-world problems. The state-of-the-art in this field is quite fuzzy, as results are published in various domain-specific venues and using different datasets. In this study, we report, to the best of our knowledge, on the analysis of the largest benchmark regarding network dismantling. We reimplemented and compared 13 competitors on 12 types of random networks, including ER, BA, and WS, with different network generation parameters. We find that network metrics, proposed more than 20 years ago, are often non-dominating competitors, while many recently proposed techniques perform well only on specific network types. Besides the solution quality, we also investigate the execution time. Moreover, we analyze the similarity of competitors, as induced by their node rankings. We compare and validate our results on real-world networks. Our study is aimed to be a reference for selecting a network dismantling method for a given network, considering accuracy requirements and run time constraints.

Original languageEnglish
Article number13513
JournalScientific Reports
Volume8
Issue number1
DOIs
Publication statusPublished - 1 Dec 2018

Fingerprint Dive into the research topics of 'A comparative analysis of approaches to network-dismantling'. Together they form a unique fingerprint.

Cite this