Infrastructure networks such as the Internet backbone and power grids are essential for our everyday lives. With the prevalence of cyber-attacks on them, measuring their robustness has become an important issue. To date, many robustness metrics have been proposed. It is desirable for a robustness metric to possess the following three properties: considering global network topologies, strictly increasing upon link additions, and having a quadratic complexity in terms of the number of nodes on sparse networks. This paper proposes to use Average Network Flow (ANF) as a robustness metric, and proves that it increases strictly, and gives an algorithm to compute ANF with a quadratic complexity by leveraging Gomory-Hu trees. Thus, with ANF intrinsically considering global network topologies, ANF is unveiled to be a new robustness metric satisfying those three properties. Moreover, this paper compares ANF with seven existing representative metrics, showing that each metric has its own characteristics, so there is no silver bullet in measuring network robustness and it is recommended to apply several metrics together to gain a comprehensive view. Finally, by experimenting on the scenarios in which network topologies preserve the same numbers of nodes and links, some interesting behaviors of robustness metrics are reported.
翻译:互联网主干网和电网等基础设施网络对我们日常生活至关重要。 随着网络攻击的普遍存在, 测量其稳健性已成为一个重要的问题。 到目前为止, 已经提出了许多稳健度量度。 强健度度度指标应该拥有以下三种特性: 考虑全球网络地形, 严格通过连通增加而增加, 并且从稀少网络上的节点数量来看具有四级复杂性。 本文建议使用平均网络流动(ANF)作为稳健度指标, 并证明它严格地增加, 并给出一种算法, 通过利用果莫里- Hua 树来以等量复杂度来计算ANF。 因此, 与ANF 内在地考虑全球网络地形学, ANF是满足这三个特性的新稳健度度度指标。 此外, 本文将ANF与现有的7个代表性指标进行比较, 表明每个指标都有自己的特点, 所以没有银球在测量网络稳健性方面, 因此建议它一起应用数度指标来获得全面的观点。 最后, 通过实验网络顶端连接的图象, 。