An efficient spectral bound for link vulnerability assessment in large-scale networks

Simultaneous attacks can cause devastating damage, breaking down communication networks into small fragments. To mitigate the risk and develop proactive responses, it is essential to assess the robustness of network in the worst-case scenarios. In this paper, we propose a spectral lower-bound on the number of removed links to incur a certain level of disruption in terms of pairwise connectivity. Our lower-bound explores the latent structural information in the network Laplacian spectrum, the set of eigenvalues of the Laplacian matrix, to provide guarantees on the robustness of the network against intentional attacks. Such guarantees often cannot be found in heuristic methods for identifying critical infrastructures. For the first time, the attack-resistant proofs of large scale communication networks against link attacks are presented.