TY - JOUR
T1 - QRE: Quick Robustness Estimation for large complex networks
AU - Wandelt, Sebastian
AU - Sun, Xiaoqian
AU - Zanin, Massimiliano
AU - Havlin, Shlomo
N1 - National Natural Science Foundation of China (Grant Nos. 61650110516 and 61601013).
Sem PDF conforme despacho.
PY - 2018/6/1
Y1 - 2018/6/1
N2 - Robustness estimation is critical for the design and maintenance of resilient networks. Existing studies on network robustness usually exploit a single network metric to generate attack strategies, which simulate intentional attacks on a network, and compute a metric-induced robustness estimation, called R. While some metrics are easy to compute, e.g. degree, others require considerable computation efforts, e.g. betweenness centrality. We propose Quick Robustness Estimation (QRE), a new framework and implementation for estimating the robustness of a network in sub-quadratic time, i.e., significantly faster than betweenness centrality, based on the combination of cheap-to-compute network metrics. Experiments on twelve real-world networks show that QRE estimates the robustness better than betweenness centrality-based computation, while being at least one order of magnitude faster for larger networks. Our work contributes towards scalable, yet accurate robustness estimation for large complex networks.
AB - Robustness estimation is critical for the design and maintenance of resilient networks. Existing studies on network robustness usually exploit a single network metric to generate attack strategies, which simulate intentional attacks on a network, and compute a metric-induced robustness estimation, called R. While some metrics are easy to compute, e.g. degree, others require considerable computation efforts, e.g. betweenness centrality. We propose Quick Robustness Estimation (QRE), a new framework and implementation for estimating the robustness of a network in sub-quadratic time, i.e., significantly faster than betweenness centrality, based on the combination of cheap-to-compute network metrics. Experiments on twelve real-world networks show that QRE estimates the robustness better than betweenness centrality-based computation, while being at least one order of magnitude faster for larger networks. Our work contributes towards scalable, yet accurate robustness estimation for large complex networks.
KW - Complex networks
KW - Robustness estimation
KW - Scalability
UR - http://www.scopus.com/inward/record.url?scp=85013455494&partnerID=8YFLogxK
U2 - 10.1016/j.future.2017.02.018
DO - 10.1016/j.future.2017.02.018
M3 - Article
AN - SCOPUS:85013455494
VL - 83
SP - 413
EP - 424
JO - Future Generation Computer Systems - The International Journal of Grid Computing and eScience
JF - Future Generation Computer Systems - The International Journal of Grid Computing and eScience
SN - 0167-739X
ER -