National Key Laboratory of CNS/ATM, School of Electronic and Information Engineering, Beihang University, 100191, Beijing, China.
National Engineering Laboratory of Multi-Modal Transportation Big Data, 100191, Beijing, China.
Sci Rep. 2018 Sep 10;8(1):13513. doi: 10.1038/s41598-018-31902-8.
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.
估计、理解和改进网络的鲁棒性在生物信息学、交通运输或计算语言学等许多应用领域都有应用。因此，随着网络科学在复杂系统建模中的兴起，已经开发并应用了许多用于鲁棒性估计和网络拆解的方法来解决实际问题。该领域的最新进展相当模糊，因为研究结果发表在各种特定领域的场所，并使用不同的数据集。在这项研究中，我们根据自己的知识，报告了对网络拆解最大基准的分析。我们重新实现并比较了 13 个竞争对手在 12 种随机网络（包括 ER、BA 和 WS）上的表现，这些网络具有不同的网络生成参数。我们发现，20 多年前提出的网络指标往往是非常具有竞争力的，而许多最近提出的技术仅在特定类型的网络上表现良好。除了求解质量，我们还研究了执行时间。此外，我们还分析了由节点排序引起的竞争对手之间的相似性。我们在真实网络上比较和验证了我们的结果。我们的研究旨在为给定网络选择网络拆解方法提供参考，同时考虑准确性要求和运行时间限制。
