Robustness and Algebraic Connectivity of Random Interdependent Networks∗

We investigate certain structural properties of random interdependent networks. We start by studying a property known as r-robustness, which is a strong indicator of the ability of a network to tolerate structural perturbations and dynamical attacks. We show that random /c-partite graphs exhibit a threshold for r-robustness, and that this threshold is the same as the one for the graph to have minimum degree r. We then extend this characterization to random interdependent networks with arbitrary intra-layer topologies. Finally we characterize the algebraic connectivity of such networks, and provide an asymptotically tight rate of growth of this quantity for a certain range of inter-layer edge formation probabilities. Our results arise from a characterization of the isoperimetric constant of random interdependent networks, and yield new insights into the structure and robustness properties of such networks.