.png){kind=icon}
返回
Measuring Network Robustness by Average Network Flow
.png){kind=icon}
OA
AI
DOI：10.1109/TNSE.2022.3150289.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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) with unit edge capacity as a robustness metric, and shows that it satisfies these three properties. Especially, an algorithm by leveraging Gomory-Hu trees is proposed to compute ANF. The Gomory-Hu tree for a network embeds the all-pairs maximum flows of this network into its edges, thus enabling our algorithm to achieve the quadratic complexity. Moreover, this paper compares ANF with seven existing representative metrics. By experimenting on the scenario in which network topologies preserve the numbers of nodes and links, several new phenomena of robustness metrics are reported.
Keyword:
Measurement
Robustness
Complexity theory
Network topology
Topology
Sparse matrices
Eigenvalues and eigenfunctions
Network topologies
network robustness
network flow
gomory-hu tree
期刊
I
IF:
7.9
论文数:
2.6K
被引数:
10.0K
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容