Topological Approach to Measure Network Recoverability

Abstract

Network recoverability refers to the ability of a network to return to a desired performance level after suffering malicious attacks or random failures. This paper proposes a general topological approach and recoverability indicators to measure the network recoverability in two scenarios: 1) recovery of damaged connections and 2) any disconnected pair of nodes can be connected to each other. Our approach presents the effect of the random attack and recovery processes on the network performance by the robustness envelopes of realizations and the histograms of two recoverability indicators. By applying the effective graph resistance and the network efficiency as robustness metrics, we employ the proposed approach to assess 10 realworld communication networks. Numerical results verify that the network recoverability is coupled to the network topology, the robustness metric and the recovery strategy. We also show that a greedy recovery strategy could provide a near-optimal recovery performance for the investigated robustness metrics.