Algorithms for determining network robustness

Abstract

In this paper, we study algorithms for determining the robustness of a network. Network robustness is a novel graph theoretic property that provides a measure of redundancy of directed edges between all pairs of nonempty, disjoint subsets of nodes in a graph. The robustness of a graph has been shown recently to be useful for characterizing the class of network topologies in which resilient distributed algorithms that use purely local strategies are able to succeed in the presence of adversary nodes. Therefore, network robustness is a critical property of resilient networked systems. While methods have been given to construct robust networks, algorithms for determining the robustness of a given network have not been explored. This paper introduces several algorithms for determining the robustness of a network, and includes centralized, decentralized, and distributed algorithms.