Redundant Interdependencies Boost the Robustness of Multiplex Networks

In the analysis of the robustness of multiplex networks, it is commonly assumed that a node is functioning only if its interdependent nodes are simultaneously functioning. According to this model, a multiplex network becomes more and more fragile as the number of layers increases. In this respect, the addition of a new layer of interdependent nodes to a preexisting multiplex network will never improve its robustness. Whereas such a model seems appropriate to understand the effect of interdependencies in the simplest scenario of a network composed of only two layers, it may seem unsuitable to characterize the robustness of real systems formed by multiple network layers. In fact, it seems unrealistic that a real system evolved, through the development of multiple layers of interactions, towards a fragile structure. In this paper, we introduce a model of percolation where the condition that makes a node functional is that the node is functioning in at least two of the layers of the network. The model reduces to the commonly adopted percolation model for multiplex networks when the number of layers equals two. For larger numbers of layers, however, the model describes a scenario where the addition of new layers boosts the robustness of the system by creating redundant interdependencies among layers. We prove this fact thanks to the development of a message-passing theory that is able to characterize the model in both synthetic and real-world multiplex graphs.

Popular Summary

Global infrastructures are often dependent on one another. A power grid relies on a robust water supply, for example, and air traffic can affect usage of a rail system. Similar scenarios show up in financial networks as well as metabolic pathways within a cell. In all of these situations, a node in one layer of a network can control or regulate nodes in another layer. Typically in such multiplex networks with more than two layers, it is assumed that every node must be interdependent on each of its linked nodes in other layers. This assumption predicts that a multiplex network becomes increasingly susceptible to failure as the number of layers grows. We have come to the opposite conclusion: Increasing the number of layers can actually boost the robustness of a network if there are redundant interdependencies.

Network robustness is often characterized using what is known as a percolation model, a mathematical framework that monitors how global connectivity changes as individual components are damaged—for example, how travel across a subway system is impacted by closures of one or several stations. We have developed and analyzed a new percolation model where a node is still considered functional if it is operating in at least two network layers. In the case of the subway system, for instance, perhaps a bus line and an intercity rail system can still use the closed station.

Our model allows for a more comprehensive understanding of how complex systems respond to damage. This framework could be generalized, for example, to handle a variable number of minimal functioning layers or other realistic scenarios.

Figure 1

A multiplex network with $M=3$ layers and $N=5$ nodes is shown. Every node $i$ has $M=3$ interdependent replica nodes $(i,\alpha )$ with $\alpha =1$, 2, 3. In this figure, triplets of replica nodes are also identified by their color.

Figure 2

Percolation transition in the US air transportation network [39]. We consider only US domestic flights operated in January 2014 by the three major carriers in the US (American Airlines, Delta, and United), and we construct a multiplex network where airports are nodes, and connections on the layers are determined by the existence of at least one flight operated by a given carrier between the two locations. The number of nodes in the network is $N=183$. Please note that some of the nodes appear as connected only in one layer; therefore, the relative size of the largest cluster is always smaller than one. (a) We consider a single realization of the random damage by assigning to every replica node $(i,\alpha )$ a random number extracted uniformly in the interval [0, 1]. Replica nodes are considered damaged if their associated random number is smaller than $p$. Note that the same exact configuration of random damage is considered in all cases. In the percolation diagram, we consider the size of the MCGC and RMCGC as a function of $p$. Large symbols are results of numerical simulations, whereas the tick line is obtained from the solution of our mathematical framework [system of Eqs. (1)–(4)]. In particular, we consider the three possible multiplex networks composed of only two layers: American–Delta (black circles), American–United (blue triangles), and Delta–United (red squares). Diagrams obtained by considering the system as composed of all three layers are represented as green triangles for the model of Ref. [4] and as purple triangles for the redundant model. (b) Same as in panel (a) but for average values over 100 independent realizations of the random damage. Purple thin lines stand for the 100 independent realizations of random damage considered in the case of the redundant model. As is apparent from the figure, the average does not capture the behavior of single instances of disorder well, and fluctuations are rather large for a wide range of possible values of $p$.

Figure 3

The percolation threshold $p_c$ is plotted versus the average degree $z$ of each layer for Poisson multiplex networks with $M=2$, 3, 4, 5 layers indicated, respectively, with blue solid, red dashed, green dot-dashed, and orange dotted lines.

Figure 4

The discontinuous jump $S_c=S(p_c)$ of the RMCGC at the percolation threshold $p=p_c$ is plotted versus the average degree $z$ of each layer for Poisson multiplex networks with $M=2$, 3, 4, 5 layers indicated, respectively, with blue solid, red dashed, green dot-dashed, and orange dotted lines.

Figure 5

Comparison between the MCGC and the RMCGC models in Poisson multiplex networks. (a) Critical value $z^{\star }$ of the average degree as a function of the number of network layers $M$. Results for the RMCGC model are displayed as red diamonds. Results for the MCGC model are denoted by blue triangles. (b) Height of the jump $S^{\star }$ at the transition point as a function of the number of network layers.

Figure 6

Comparison between simulation results of the RMCGC for a multiplex network with $M=3$ Poisson layers with average degree $z$ and no link overlap, and the message-passing results over single-network realization and given configuration damage. We consider different values of the average degree $z=2.5$, 3.0, 4.0, 5.0. Points indicate results of numerical simulations: blue circles ($z=2.5$), red squares ($z=3.0$), green diamonds ($z=4.0$), and orange triangles ($z=5.0$). Message-passing predictions are denoted by lines with the same color scheme used for numerical simulations. Simulation results are performed on a single instance of a multiplex network with $N=10^4$ nodes.

Figure 7

Same as in Fig. 6, but for averages over 20 instances of the multiplex network model and configurations of random initial damage.

Figure 8

Diagrams for Eqs. (33) determining $x_{\mu \nu }^{(\xi )}$ in the case of multiplex networks with three layers ($M=3$) and Poisson multidegree distribution with $⟨k^{(1,1,1)}⟩=z_3$, $⟨k^{(1,1,0)}⟩=⟨k^{(1,0,1)}⟩=⟨k^{(0,1,1)}⟩=z_2$ and $⟨k^{(1,0,0)}⟩=⟨k^{(0,1,0)}⟩=⟨k^{(0,0,1)}⟩=z_1$.

Figure 9

Comparison between the simulation results of the RMCGC for a multiplex network with $M=3$ layers and Poisson multidegree distribution with $⟨k^{(1,1,1)}⟩=c_3$, $⟨k^{(1,1,0)}⟩=⟨k^{(1,0,1)}⟩=⟨k^{(0,1,1)}⟩=c_2$ and $⟨k^{(1,0,0)}⟩=⟨k^{(0,1,0)}⟩=⟨k^{(0,0,1)}⟩=c_1$ and the theoretic predictions over the same multilayer network ensemble. Data are shown for $c_1=0$, $c_2=3$, $c_3=2$ (blue circles), $c_1=1$, $c_2=3$, $c_3=0$ (red squares), and $c_1=2$, $c_2=0$, $c_3=2$ (green diamonds). The theoretical predictions are indicated with lines. The simulation results are performed on multilayer networks with $N=10^4$ nodes and are averaged over 20 multilayer network realizations.