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 -