Robust Graph Topologies for Networked Systems

Robustness of networked systems against noise corruption and structural changes in an underlying network topology is a critical issue for a reliable performance. In this paper, we investigate this issue of robustness in networked systems both from structural and functional viewpoints. Structural robustness deals with the effect of changes in a graph structure due to link or edge failures, while functional robustness addresses how well a system behaves in the presence of noise. We discuss that both of these aspects are inter-related, and can be measured through a common graph invariant. A graph process is introduced where edges are added to an existing graph in a step-wise manner to maximize robustness. Moreover, a relationship between the symmetry of an underlying network structure and robustness is also discussed.