Robustness of a network formed by n interdependent networks with a one-to-one correspondence of dependent nodes

Abstract

Many real-world networks interact with and depend upon other networks. We develop an analytical framework for studying a network formed by n fully interdependent randomly connected networks, each composed of the same number of nodes N. The dependency links connecting nodes from different networks establish a unique one-to-one correspondence between the nodes of one network and the nodes of the other network. We study the dynamics of the cascades of failures in such a network of networks (NON) caused by a random initial attack on one of the networks, after which a fraction p of its nodes survives. We find for the fully interdependent loopless NON that the final state of the NON does not depend on the dynamics of the cascades but is determined by a uniquely defined mutual giant component of the NON, which generalizes both the giant component of regular percolation of a single network (n=1) and the recently studied case of the mutual giant component of two interdependent networks (n=2). We also find that the mutual giant component does not depend on the topology of the NON and express it in terms of generating functions of the degree distributions of the network. Our results show that, for any n≥2 there exists a critical p=p(c)>0 below which the mutual giant component abruptly collapses from a finite nonzero value for p≥p(c) to zero for p<p(c), as in a first-order phase transition. This behavior holds even for scale-free networks where p(c)=0 for n=1. We show that, if at least one of the networks in the NON has isolated or singly connected nodes, the NON completely disintegrates for sufficiently large n even if p=1. In contrast, in the absence of such nodes, the NON survives for any n for sufficiently large p. We illustrate this behavior by comparing two exactly solvable examples of NONs composed of Erdős-Rényi (ER) and random regular (RR) networks. We find that the robustness of n coupled RR networks of degree k is dramatically higher compared to the n-coupled ER networks of the same average degree k[over ¯]=k. While for ER NONs there exists a critical minimum average degree k[over ¯]=k[over ¯](min)∼lnn below which the system collapses, for RR NONs k(min)=2 for any n (i.e., for any k>2, a RR NON is stable for any n with p(c)<1). This results arises from the critical role played by singly connected nodes which exist in an ER NON and enhance the cascading failures, but do not exist in a RR NON.