Complex systems, usually represented as complex networks, are rarely isolated but usually interdependent and interact with other systems^{1, 2, 3}. The vulnerability of a single network is usually described by the percolation model in which the order parameter is the size of the giant connected component and the external parameter is the fraction of nodes that survived the initial failure⁴. Recently it was shown that a coupled-networks system is considerably more vulnerable than its isolated component networks. In interdependent networks, nodes’ interactions are represented by two different types of link, connectivity and dependency links. The requirement to be connected to the giant connected component, as in single-network percolation, represents the need of a node (to function) to be connected to the system, but it does not matter through which path. In contrast, a dependency link represents the need of a node to get a critical supply to function from one other specific node. This type of model is based on the idea of mutual percolation in which the order parameter is the size of the mutual giant component^{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}. The coupling between different networks induces a dynamical process of cascading failures; a failure of nodes in one network leads to a failure of dependent nodes in other networks, which in turn may cause further damage to the first network and so on. This sequence of cascading failures may totally fragment the entire system and the size of the mutual giant component collapses to zero. It was shown that the coupling strength of the networks, represented by the fraction q of interdependent nodes, determines the way the system collapses^{6, 8, 20}. For strong coupling, that is, for a high fraction of interdependent nodes, an initial damage event can lead to cascading failures that yield an abrupt collapse of the system, in a form of a first-order phase transition. Reducing the coupling strength below a critical value, q_c, leads to a change from an abrupt collapse to a continuous decrease of the size of the network, in a form of a second-order phase transition. This new paradigm is in marked contrast to the common knowledge represented by a single network behaviour. In any single network the percolation transition is always continuous; therefore, the damage due to a failure is a continuous function of the amount of damage. In sharp contrast, in interdependent networks, owing to the cascading failures, the percolation transition may be discontinuous. In this case, damage of even a single node can lead to failure of a finite fraction of the whole system, which is clearly different from the continuous behaviour in single networks. The existence of an abrupt collapse phenomenon in interdependent networks makes such systems extremely risky. Thus, understanding this phenomenon is critical for evaluating the systems’ risks and vulnerability and for designing robust infrastructures²¹.

Present models focus on interdependent networks where space restrictions are not considered. Indeed, in some complex systems the spatial location of the nodes is not relevant or not even defined, such as in protein interaction networks^{22, 23, 24} and the World Wide Web^{25, 26}. However, in many real-world systems, such as power grid networks, ad hoc communication networks and computer networks, nodes and links are located in Euclidean two-dimensional (2D) space²⁷. On the basis of universality principles, the dimension of a network is a fundamental quantity to characterize its structure and basic physical properties^{28, 29}. Indeed, all percolation models whose links have a characteristic length, embedded in a space of same dimensions, belong to the same universality class²⁸. For example, in random geometric networks the distance between two connected nodes is below a given characteristic length. Another example is power grid networks where the links have a characteristic length because their lengths follow an exponential distribution²⁹. Therefore, these examples, as well as any 2D network with a characteristic length scale, belong to the same universality class as regular lattices. Thus, to obtain the main features of an arbitrary system of interdependent networks embedded in 2D space, we model these spatially embedded networks as 2D lattices. Typically, real spatial networks in 2D space are characterized by a lower average degree than a square lattice ²⁷. As seen in Supplementary Fig. S7, the case of coupled lattices is not only a representative example for all of its universality class but may serve as a lower bound case, and real coupled spatial networks are even more vulnerable.

Here, we study analytically and numerically the stability of systems of two interdependent spatially embedded networks, modelled as two interdependent lattices (as illustrated in Fig. 1a). We find that in such systems q_c = 0; that is, any coupling q>0 leads to an abrupt first-order transition. We show that the origin of this extreme vulnerability of spatially embedded networks lies in the critical behaviour of percolation of a single lattice, which is characterized by a critical exponent β<1 (refs 28, 30). This is in contrast to random networks for which β = 1, leading to q_c>0 in the case of interdependent random networks. Here the dependency links are between lattices’ nodes located in different random spatial positions (Fig. 1a) or between lattice nodes and nodes of random networks where the space does not play a role at all (Fig. 1b). In the case of dependency links between lattice nodes with exactly the same position, the transition is always continuous, as for percolation in a single lattice³¹. Note that the fully interdependent limit of q = 1 of coupled lattices was studied in ref. 19. Our results suggest that the effect of spatial embedding is qualitatively different from all other studied network properties that show only a quantitative change of the percolation threshold p_c and of the critical coupling q_c.

In random networks with no space restrictions, such as Erdös–Rényi and RR, the connectivity links (blue lines) do not have a defined length. In contrast, in spatially embedded networks nodes are connected only to nodes in their geometrical neighbourhood creating a 2D network, modelled here as a square lattice. The red arrows represent directed dependency relations between nodes in different networks, which can be of different types. a, Coupled lattices. b, A coupled lattice–random network. c, Coupled random networks. d, A real-world spatial network coupled with a random network. Models b and d belong to the same universality class.

• Full size image (400 KB)

Our theoretical and numerical approaches predict that a real-world system of interdependent spatially embedded networks that are characterized by β<1 will, for any q>0, abruptly disintegrate. As for percolation of lattice networks it is known that for any dimension d<6, β<1 (ref. 28), we expect that also interdependent systems embedded in d = 3 (or any d<6) will collapse abruptly for any finite fraction of dependency q. Indeed, an analysis of the statistics of many real-world outage events showed that they are commonly caused by cascading failures³². Our results show that an important possible mechanism in these events is the interdependencies in spatial networks.

Consider a system of two interdependent networks, i = 1 and i = 2, where a fraction 1−p_i of nodes of each network is initially randomly removed. We assume that only the nodes that belong to the giant component of the remaining networks that constitute a fraction of the original network remain functional. Each node that has been removed or disconnected from the giant component causes its dependent node in the other network to also fail. This leads to further disconnections in the other network and to cascading failures. The size of the networks’ giant components at the end of the cascade is given by , where x_i are the solutions of the self-consistent equations⁸

where q_i is the fraction of nodes in network i that depends on nodes in the other network. Here we assume no restrictions on the selection of the directed dependency links. The results for the case of the no feedback condition, where the dependency links are bidirectional⁸, are qualitatively the same (see Supplementary Fig. S8). The function can be obtained either analytically or numerically from the percolation behaviour of a single network.

For simplicity, we focus on a symmetric case, where both networks have the same degree distribution P(k) and the same topology, and where p₁ = p₂≡p and q₁ = q₂≡q. Still, the results are valid for any system of interdependent spatially embedded networks (such as planar graph) that belong to the same universality class. In particular, to study the role of spatial embedding, we compare the percolation transition in the case of a pair of interdependent lattices (Fig. 1a) with the case of a pair of interdependent random-regular (RR) networks (Fig. 1c). The RR networks have the same degree distribution, P(k) = δ_k,4, as for the lattices with the only difference being that the lattice networks are embedded in space, in contrast to RR networks.

In the symmetric case, equations (1) and (2) can be reduced to a single equation

where the size of the giant component at steady state is . For any values of p and q, the solution of equation (3) can be graphically presented as the intersection between the curve and the straight line y = x representing the right-hand side and the left-hand side of equation (3) respectively, as demonstrated in Fig. 2. The form of for conventional percolation is obtained from numerical simulations of a single lattice and analytically for a single RR network¹⁷. From the solution of equation (3) we obtain as a function of p for several values of q. This is the new percolation behaviour for a system of interdependent networks, shown in Fig. 3a, for the case of coupled lattices and in Fig. 3b for the case of coupled RR networks. In the case of interdependent lattices, only for q = 0, no coupling between the networks (the single network limit), the transition is the conventional second-order percolation transition, whereas for any q>0 the collapse is abrupt in the form of a first-order transition. In marked contrast, in the case of interdependent RR networks, for the transition is abrupt, whereas for q<q_c the transition is continuous.

The left-hand side and right-hand side of equation (3) are plotted as a straight (red) line and a (blue) curve respectively. The tangential touching point, x*, marked with a black circle, represents the new percolation threshold in the system of interdependent networks. a, In the case of coupled lattices, owing to the infinite slope of the curve at p_c, x* is always larger than p_c and, thus, there is always (for any q>0) a discontinuous jump in the size of the giant component as p decreases. b, In contrast, in coupled random networks the slope of the curves is finite for any value of x. Therefore, values of q<q_c exist for which x* is equal to p_c, leading to a continuous behaviour in the network’s size.

• Full size image (68 KB)

a,b, The size of at steady state after random failure of a fraction 1−p of the nodes of two interdependent lattice networks with periodic boundary conditions (PBC; a) and two RR networks (b). All networks are of size 16×10⁶ nodes and the same degree distribution P(k) = δ_k,4. The coupling between the lattices and between the RR networks changes from q = 0 to q = 0.8 with step 0.1 (from left to right). The solid lines are the solutions of equation (3) and the symbols represent simulation results. In the case of interdependent lattices, only for q = 0 (no coupling, that is, a single lattice) the transition is the conventional second-order percolation, whereas for any q>0 the collapse is abrupt in the form of a first-order transition. This is in marked contrast to the case of interdependent RR networks, where only for the transition is abrupt, whereas for q<q_c the transition is continuous. c,d, A characteristic behaviour in a first-order percolation transition in coupled networks is the sharp divergence of the number of iterations (NOI) when p approaches (ref. 16) as seen for coupled lattices for any q>0 (c) and for coupled RR networks for q>q_c (d). Models of coupled lattices with PBC have the same behaviour as models without PBC as shown in Supplementary Fig S6.

• Full size image (175 KB)

A discontinuity of is a result of a discontinuity of x(p), represented graphically as the tangential touching point of the curve and the straight line (Fig. 2a). At this point, is the new percolation threshold in the case of interdependent networks, and yields the size of the giant component at the transition, , which abruptly jumps to zero as p slightly decreases. The condition for a first-order transition , for a given q, is thus given by solving equation (3) together with its tangential condition,

The size of the giant component at the transition depends on the coupling strength q such that reducing q leads to a smaller value of and thus a smaller discontinuity in the size of the giant component. In general, of a single network has a critical threshold at x = p_c such that whereas and monotonically increases with x (ref. 28). As long as , the size of the discontinuity is larger than zero. However, for a certain critical coupling q≡q_c, and the size of the jump becomes zero (Fig. 2b). In this case the percolation transition becomes continuous.

Therefore, the critical dependency q_c below which the discontinuous transition becomes continuous must satisfy equations (3) and (4) for xp_c given by

A markedly different behaviour between random and spatial coupled networks is derived from equations (5) and (6). This difference is a consequence of the critical behaviour of percolation in a single network. In the case of a single random network is finite for any value of x. This allows an exact solution of equation (6), yielding a finite non-zero value for q_c. However, for the case of a single lattice network the derivative of diverges at the critical point, , yielding q_c = 0. Therefore, from equation (6) follows that any coupling q>0 between lattices leads to an abrupt first-order transition. Figure 2 demonstrates how the infinite slope of the percolation curve of a single lattice leads to a discontinuous percolation transition for any q>0 in coupled lattices.

The behaviour of the percolation order parameter of a single network near the critical point is defined by the critical exponent β, where . As for a single 2D lattice β = 5/36<1, it follows that diverges for xp_c for all networks embedded in 2D space^{28, 30, 33, 34}. In contrast, for random networks, such as Erdös–Rényi and RR, β = 1, which yields a finite value of ^{28, 30} and therefore a finite value for q_c.

We next study the effect of spatial embedding, comparing the size of the network at criticality, that is, the size of the jump, in three models: two non-embedded coupled RR networks (k = 4); two coupled lattices; and a lattice coupled with a non-embedded RR network. The last model is relevant to real-world systems in which a spatially embedded network is coupled to a non-embedded network, such as in the case of a power grid (embedded in 2D space) coupled to a communication network (non-embedded) as studied in ref. 5.

Figure 4 shows the size of the giant component at criticality as a function of coupling strength q, demonstrating the significantly increased vulnerability of the lattice network in the coupled system compared with the random networks system. For coupled lattice–lattice and coupled lattice–RR systems for any q>0, whereas for a coupled RR–RR system for q<q_c = 0.43. Moreover, in coupled lattices even for weak coupling, the size of the discontinuity is relatively large. For example, for q = 0.1 the size of the network just before the collapse is about 42% of the original network.

Comparison of the size of the giant component at criticality for two coupled lattices (squares), coupled lattice and RR networks (circles) and two coupled RR networks (diamonds) as a function of the coupling strength q. The RR networks have the same degree distribution as the lattice, k = 4 for all nodes. Whereas for random networks with q<q_c = 0.43 the size of the networks at criticality is zero, in coupled lattice network the networks abruptly collapse for any finite q>0. Note also the significant differences in the network sizes at the collapse transition. The coupled lattices collapse at a significantly larger giant component compared with the coupled RR case. The solid line represents the theory for coupled lattices given by equations (5) and (6), and the symbols are from simulations. The solid line for coupled RR networks represents the theory derived in ref. 6. The scaling behaviour (as obtained from equations (7) and (8)) in the case of coupled lattices and coupled lattice–RR for qq_c = 0 is and respectively, whereas for coupled RR (see insets).

• Full size image (229 KB)

We next test the stability of two real-world spatially embedded networks: the western United States power grid and the European power grid. Figure 5 compares the mutual percolation of three systems of interdependent networks: the power grid of the western US, embedded in 2D space, coupled to a random network; the power grid of Europe, embedded in 2D space, coupled to a random network; and a model of two coupled random networks, not embedded in space, showing the pronounced effect of the spatial embedding on the stability of the system. Weak coupling leads to an abrupt collapse of the spatial embedded systems whereas the non-embedded networks, with the same coupling strength between them, undergo a smooth continuous transition.

A comparison of mutual percolation transition in three systems: the western United States electrical power grid coupled to a random network; the European power grid coupled to a random network; and a model of two coupled random networks with the same parameters (size, k and q). The size of the largest component at steady state after initial random removal of 1−p of the nodes, versus p. The circles (red) and squares (green) represent simulation results of the electrical power grid of the western United States (US_PG, embedded in 2D space with k = 2.7, N≃5,000) and RR network (k = 3, N≃5,000) with coupling q = 0.2 and q = 0.4 respectively. The crosses (grey) and stars (pink) represent simulation results of the electrical power grid of Europe (Europe_PG, embedded in 2D space with k = 2.88, N≃1,250) and a RR network (k = 3, N≃1,250) with coupling q = 0.2 and q = 0.4 respectively. The diamonds (blue) and the triangles (black) represent simulation results of two interdependent random networks (k = 3, N = 5,000) with coupling q = 0.2 and q = 0.4 respectively

• Full size image (262 KB)

We calculate explicitly the scaling behaviour of the size of the discontinuity near the critical coupling, , as qq_c. The size of the giant component at the transition is , where is the solution of equation (3) together with its tangential condition equation (4). We solve the equations for q = q_c+δ, and , where δ,ε,Δ0. Near the critical point ; thus, , where A is a constant. Equations (3) and (4) become

In the case of coupled lattices q_c = 0; thus, from equation (7) it follows that near the critical coupling . Therefore, from equation (8) follows that ε~δ^1/(1−β) and the scaling behaviour of the size of the giant component at criticality for q0 is

The small value of the exponent, in equation (9). demonstrates analytically the sharp increase of with q, for very small q values, as seen in Fig. 4. This is indeed the origin of the critical role of dependencies for the extreme vulnerability of spatially embedded coupled networks.

In the case of a square lattice coupled to a RR network with k = 4 with the same q₁ = q₂ = q, similar analytical treatment of equations (1) and (2) yields that . This larger critical exponent expresses that the singularity in the case of a lattice coupled to a random network is slightly weaker compared with the singularity of the symmetric case of coupled lattices. The fact that indicates that even a weak coupling between spatial networks leads to relatively large-scale collapses. For the case of coupled random networks, however, for qq_c the discontinuity size does not have a singular point, , that is, . The above approximations are numerically validated as shown in the insets of Fig. 4.

1. Rosato, V. et al. Modeling interdependent infrastructures using interacting dynamical models. Int. J. Crit. Infrastruct. 4, 63–79 (2008).
   • Article
   • Show context
2. Peerenboom, J. P., Fischer, R. E. & Whitfield, R. in Proc. 40th Ann. Hawaii Int. Conf. Syst. Sci. 112–119 (2007); available at http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4076595.
   • Show context
3. Rinaldi, S., Peerenboom, J. & Kelly, T. Identifying, understanding, and analyzing critical infrastructure interdependencies. IEEE Control. Syst. Magn. 21, 11–25 (2001).
   • Article
   • Show context
4. Cohen, R. & Havlin, S. Complex Networks: Structure, Robustness and Function (Cambridge Univ. Press, 2010).
   • Show context
5. Buldyrev, S. V., Parshani, R., Paul, G., Stanley, H. E. & Havlin, S. Catastrophic cascade of failures in interdependent networks. Nature 464, 1025–1028 (2010).
   • CAS
   • ISI
   • PubMed
   • Article
   • Show context
6. Parshani, R., Buldyrev, S. V. & Havlin, S. Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition. Phys. Rev. Lett. 105, 048701 (2010).
   • CAS
   • ADS
   • PubMed
   • Article
   • Show context
7. Vespignani, A. The fragility of interdependency. Nature 464, 984–985 (2010).
   • CAS
   • ADS
   • ISI
   • PubMed
   • Article
   • Show context
8. Gao, J., Buldyrev, S. V., Havlin, S. & Stanley, H. E. Robustness of a network of networks. Phys. Rev. Lett. 107, 195701 (2011).
   • CAS
   • PubMed
   • Article
   • Show context
9. Leicht, E. A. & D’Souza, R. M. Percolation on interacting networks. Preprint at http://arxiv.org/abs/0907.0894 (2009).
   • Show context
10. Brummitt, C. D., D’Souza, R. M. & Leicht, E. A. Suppressing cascades of load in interdependent networks. Proc. Natl Acad. Sci. USA 109, 680–689 (2012).
    • ADS
    • PubMed
    • Article
    • Show context
11. Hao, J., Cai, S., He, Q. & Liu, Z. The interaction between multiplex community networks. Chaos 21, 016104 (2011).
    • ADS
    • PubMed
    • Article
    • Show context
12. Bashan, A., Bartsch, R. P., Kantelhardt, J. W., Havlin, S. & Ivanov, P. Ch. Network physiology reveals relations between network topology and physiological function. Nature Commun. 3, 702 (2012).
    • CAS
    • ADS
    • Article
    • Show context
13. Huang, X., Gao, J., Buldyrev, S. V., Havlin, S. & Stanley, H. E. Robustness of interdependent networks under targeted attack. Phys. Rev. E (R) 83, 065101 (2011).
    • CAS
    • ADS
    • Article
    • Show context
14. Buldyrev, S. V., Shere, N. W. & Cwilich, G. A. Interdependent networks with identical degrees of mutually dependent nodes. Phys. Rev. E 83, 016112 (2011).
    • CAS
    • ADS
    • Article
    • Show context
15. Hu, Y., Ksherim, B., Cohen, R. & Havlin, S. Percolation in interdependent and interconnected networks: Abrupt change from second to first order transition. Phys. Rev. E 84, 066116 (2011).
    • CAS
    • ADS
    • Article
    • Show context
16. Parshani, R., Buldyrev, S. V. & Havlin, S. Critical effect of dependency groups on the function of networks. Proc. Natl Acad. Sci. USA 108, 1007–1010 (2011).
    • PubMed
    • Article
    • Show context
17. Bashan, A., Parshani, R. & Havlin, S. Percolation in networks composed of connectivity and dependency links. Phys. Rev. E 83, 051127 (2011).
    • CAS
    • ADS
    • Article
    • Show context
18. Schneider, C. M., Yazdani, N., Araujo, N. A. M., Havlin, S. & Herrmann, H. J. Towards designing robust coupled networks. Sci. Rep. 3, 1969 (2013).
    • PubMed
    • Article
    • Show context
19. Li, W., Bashan, A., Buldyrev, S. V., Stanley, H. E. & Havlin, S. Cascading failures in interdependent lattice networks: The critical role of the length of dependency links. Phys. Rev. Lett. 108, 228702 (2012).
    • CAS
    • PubMed
    • Article
    • Show context
20. Gao, J., Buldyrev, S. V., Stanley, H. E. & Havlin, S. Networks formed from interdependent networks. Nature Phys. 8, 40–48 (2012).
    • CAS
    • ADS
    • Article
    • Show context
21. Schneider, C. M., Moreira, A. A., Andrade, J. S.Jr., Havlin, S. & Herrmann, H. J. Mitigation of malicious attacks on networks. Proc. Natl Acad. Sci. USA 108, 3838–3841 (2011).
    • ADS
    • PubMed
    • Article
    • Show context
22. Milo, R. et al. Network motifs: Simple building blocks of complex networks. Science 298, 824–827 (2002).
    • CAS
    • ADS
    • ISI
    • PubMed
    • Article
    • Show context
23. Alon, U. Biological networks: The tinkerer as an engineer. Science 301, 1866 (2003).
    • CAS
    • ISI
    • PubMed
    • Article
    • Show context
24. Khanin, R. & Wit, E. How scale-free are biological networks. J. Comput. Biol. 13, 810–818 (2006).
    • CAS
    • PubMed
    • Article
    • Show context
25. Cohen, R., Erez, K., Ben-Avraham, D. & Havlin, S. Resilience of the internet to random breakdown. Phys. Rev. Lett. 85, 4626–4628 (2000).
    • CAS
    • ADS
    • ISI
    • PubMed
    • Article
    • Show context
26. Dorogovtsev, S. N. & Mendes, J. F. F. Evolution of Networks: From Biological Nets to the Internet and WWW (Physics) (Oxford Univ. Press, 2003).
    • Show context
27. Barthelemy, M. Spatial networks. Phys. Rep. 499, 1–101 (2011).
    • CAS
    • ADS
    • Article
    • Show context
28. Bunde, A. & Havlin, S. Fractals and Disordered Systems (Springer, 1991).
    • Show context
29. Li, D., Kosmidis, K., Bunde, A. & Havlin, S. Dimension of spatially embedded networks. Nature Phys. 7, 481–484 (2011).
    • CAS
    • ADS
    • Article
    • Show context
30. Stauffer, D. & Aharony, A. Introduction to Percolation Theory 2nd edn (Taylor & Francis, 2003).
    • Show context
31. Son, S., Grassberger, P. & Paczuski, M. Percolation transitions are not always sharpened by making networks interdependent. Phys. Rev. Lett. 107, 195702 (2011).
    • CAS
    • PubMed
    • Article
    • Show context
32. Dobson, I., Carreras, B. A., Lynch, V. E. & Newman, D. E. Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization. Chaos 17, 026103 (2007).
    • ADS
    • PubMed
    • Article
    • Show context
33. Den Nijs, M. P. M. A relation between the temperature exponents of the eight-vertex and q-state Potts model. J. Phys. A 12, 1857–1868 (1979).
    • Article
    • Show context
34. Nienhuis, B. Analytical calculation of two leading exponents of the dilute Potts model. J. Phys. A 15, 199–213 (1982).
    • Article
    • Show context

Download references

We acknowledge the European EPIWORK and MULTIPLEX (EU-FET project 317532) projects, the Deutsche Forschungsgemeinschaft (DFG), the Israel Science Foundation, ONR and DTRA for financial support.