Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Progress Article
  • Published:

Networks formed from interdependent networks

Abstract

Complex networks appear in almost every aspect of science and technology. Although most results in the field have been obtained by analysing isolated networks, many real-world networks do in fact interact with and depend on other networks. The set of extensive results for the limiting case of non-interacting networks holds only to the extent that ignoring the presence of other networks can be justified. Recently, an analytical framework for studying the percolation properties of interacting networks has been developed. Here we review this framework and the results obtained so far for connectivity properties of ‘networks of networks’ formed by interdependent random networks.

This is a preview of subscription content, access via your institution

Access options

Rent or buy this article

Prices vary by article type

from$1.95

to$39.95

Prices may be subject to local taxes which are calculated during checkout

Figure 1: Schematic demonstration of first- and second-order percolation transitions.
Figure 2: Differences between the feedback condition and no-feedback condition.
Figure 3: Description of the dynamic process of cascading failures on two partially interdependent networks, which can be generalized to n partially interdependent networks.
Figure 4: Cascade of failures in two partially interdependent Erdős–Rényi networks.
Figure 5: Schematic representation of a NON.
Figure 6: Three types of loopless NON composed of five coupled networks.
Figure 7: The fraction of nodes in the giant component as a function of p for three different examples.

Similar content being viewed by others

References

  1. Watts, D. J. & Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998).

    Article  ADS  Google Scholar 

  2. Barabási, A. L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999).

    ADS  MathSciNet  MATH  Google Scholar 

  3. Faloutsos, M., Faloutsos, P. & Faloutsos, C. On power-law relationships of the internet topology. Comput. Commun. Rev. 29, 378–382 (2000).

    MATH  Google Scholar 

  4. Albert, R., Jeong, H. & Barabási, A. L. Error and attack tolerance of complex networks. Nature 406, 378–382 (2000).

    ADS  Google Scholar 

  5. Cohen, R., Erez, K., Ben-Avraham, D. & Havlin, S. Resilience of the Internet to random breakdown. Phys. Rev. Lett. 85, 4626–4628 (2000).

    ADS  Google Scholar 

  6. Callaway, D. S., Newman, M. E. J., Strogatz, S. H. & Watts, D. J. Network robustness and fragility: Percolation on random graphs. Phys. Rev. Lett. 85, 5468–5471 (2000).

    ADS  Google Scholar 

  7. Cohen, R., Erez, K., Ben-Avraham, D. & Havlin, S. Breakdown of the Internet under intentional attack. Phys. Rev. Lett. 86, 3682–3685 (2001).

    ADS  Google Scholar 

  8. Strogatz, S. H. Exploring complex networks. Nature 410, 268–276 (2001).

    ADS  MATH  Google Scholar 

  9. Milo, R. et al. Network motifs: Simple building blocks of complex networks. Science 298, 824–827 (2002).

    ADS  Google Scholar 

  10. Albert, R. & Barabási, A. L. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002).

    ADS  MathSciNet  MATH  Google Scholar 

  11. Watts, D. J. A simple model of global cascades on random networks. Proc. Natl Acad. Sci. USA 99, 5766–5771 (2002).

    ADS  MathSciNet  MATH  Google Scholar 

  12. Newman, M. E. J. The structure and function of complex networks. SIAM Rev. 45, 167–256 (2003).

    Article  ADS  MathSciNet  Google Scholar 

  13. Dorogovtsev, S. N. & Mendes, J. F. F. Evolution of Networks: From Biological Nets to the Internet and WWW (Physics) (Oxford Univ. Press, 2003).

    MATH  Google Scholar 

  14. Bonanno, G., Caldarelli, G., Lillo, F. & Mantegna, R. N. Topology of correlation-based minimal spanning trees in real and model markets. Phys. Rev. E 68, 046130 (2003).

    ADS  Google Scholar 

  15. Barrat, A., Barthelemy, M., Pastor-Satorras, R. & Vespignani, A. The architecture of complex weighted networks. Proc. Natl Acad. Sci. USA 101, 3747–3752 (2004).

    ADS  Google Scholar 

  16. Newman, M. E. J. & Girvan, M. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004).

    ADS  Google Scholar 

  17. Satorras, R. P. & Vespignani, A. Evolution and Structure of the Internet: A Statistical Physics Approach (Cambridge Univ. Press, 2004).

    MATH  Google Scholar 

  18. Gallos, L. K., Cohen, R. & Argyrakis, P. et al. Stability and topology of scale-free networks under attack and defense strategies. Phys. Rev. Lett. 94, 188701 (2005).

    ADS  Google Scholar 

  19. Song, C., Havlin, S. & Makse, H. A. Self-similarity of complex networks. Nature 433, 392–395 (2005).

    ADS  Google Scholar 

  20. Boccaletti, S., Latora, V., Moreno, Y., Chavez, M. & Hwang, D. U. Complex networks: Structure and dynamics. Phys. Rep. 424, 175–308 (2006).

    ADS  MathSciNet  MATH  Google Scholar 

  21. Newman, M. E. J., Barabási, A-L. & Watts, D. J. The Structure and Dynamics of Networks (Princeton Univ. Press, 2006).

    MATH  Google Scholar 

  22. Caldarelli, G. & Vespignani, A. Large Scale Structure and Dynamics of Complex Webs (World Scientific, 2007).

    MATH  Google Scholar 

  23. Barrát, A., Barthélemy, M. & Vespignani, A. Dynamical Processes on Complex Networks (Cambridge Univ. Press, 2008).

    MATH  Google Scholar 

  24. Cohen, R. & Havlin, S. Complex Networks: Structure, Robustness and Function (Cambridge Univ. Press, 2010).

    MATH  Google Scholar 

  25. Kitsak, M. et al. Identification of influential spreaders in complex networks. Nature Phys. 6, 888–893 (2010).

    ADS  Google Scholar 

  26. Newman, M. E. J. Networks: An Introduction (Oxford Univ. Press, 2010).

    MATH  Google Scholar 

  27. Cohen, R. & Havlin, S. Complex Networks: Structure, Robustness, and Function (Cambridge Univ. Press, 2010).

    MATH  Google Scholar 

  28. West, B. J. & Grigolini, P. Complex Webs: Anticipating the Improbable (Cambridge Univ. Press, 2011).

    MATH  Google Scholar 

  29. Barthélemy, M. Spatial networks. Phys. Rep. 499, 1–101 (2011).

    ADS  MathSciNet  Google Scholar 

  30. Li, D., Kosmidis, K., Bunde, A. & Havlin, S. Dimension of spatially embedded networks. Nature Phys. 7, 481–484 (2011).

    ADS  Google Scholar 

  31. Snijders, T. A. B., Pattison, P. E., Robins, G. L. & Handcock, M. S. New specifications for exponential random graph models. Sociol. Methodol. 36, 99–153 (2006).

    Google Scholar 

  32. Borgatti, S. P. Identifying sets of key players in a network. Comput. Math. Org. Theor. 12, 21–34 (2006).

    MATH  Google Scholar 

  33. Onnela, J-P. et al. Structure and tie strengths in mobile communication networks. Proc. Natl Acad. Sci. USA 104, 7332–7336 (2007).

    ADS  Google Scholar 

  34. Faust, K. & Zvezki, M. Comparing social networks: Size, density and local structure. Linear Algebr. Appl. 3, 185–216 (2006).

    Google Scholar 

  35. Handcock, M. S., Raftery, A. E. & Tantrum, J. M. Model-based clustering for social networks. J. R. Stat. Soc. A 170, 301–354 (2007).

    MathSciNet  Google Scholar 

  36. Jackson, M. O. & Rogers, B. W. Meeting strangers and friends of friends: How random are social networks? Am. Econom. Rev. 97, 890–915 (2007).

    Google Scholar 

  37. Kleinberg, J. The convergence of social and technological networks. Commun. ACM 51, 66–72 (2008).

    Google Scholar 

  38. Liben-Nowell, D. & Kleinberg, J. Tracing information flow on a global scale using internet chain-letter data. Proc. Natl Acad. Sci. USA 105, 4633–4638 (2008).

    ADS  Google Scholar 

  39. Borgatti, S. P., Mehra, A., Brass, D. & Labianca, G. Network analysis in the social sciences. Science 323, 892–895 (2009).

    ADS  Google Scholar 

  40. Joost, R. Inoperability input–output modeling of disruptions to interdependent economic systems. Syst. Eng. 9, 20–34 (2006).

    Google Scholar 

  41. Jackson, M. O. Social and Economic Networks (Economics, Physics, Sociology) (Princeton Univ. Press, 2008).

    Google Scholar 

  42. Zimmerman, R. Decision-making and the vulnerability of interdependent critical infrastructure. 2004 IEEE Int. Conf. Syst. Man Cybern. 5, 4059–4063 (2005).

    Google Scholar 

  43. Mendonca, D. & Wallace, W. A. Impacts of the 2001 World Trade Center attack on New York City critical infrastructures. J. Infrast. Syst. 12, 260–270 (2006).

    Google Scholar 

  44. Robert, B., Morabito, L. & Christie, R. D. The operational tools for managing physical interdependencies among critical infrastructures. Int. J. Crit. Infrastruct. 4, 353–367 (2008).

    Google Scholar 

  45. Reed, D. A., Kapur, K. C. & Christie, R. D. Methodology for assessing the resilience of networked infrastructure. IEEE Syst. J. 3, 174–180 (2009).

    ADS  Google Scholar 

  46. Bagheri, E. & Ghorbani, A. A. UML-CI: A reference model for profiling critical infrastructure systems. Inform. Syst. Front. 12, 115–139 (2009).

    Google Scholar 

  47. Mansson, D., Thottappillil, R., Backstrom, M. & Ludvika, H. V. V. Methodology for classifying facilities with respect to intentional EMI. IEEE Trans. Electromagn. Compat. 95, 46–52 (2009).

    Google Scholar 

  48. Johansson, J. & Hassel, H. An approach for modelling interdependent infrastructures in the context of vulnerability analysis. Reliab. Eng. Syst. Saf. 95, 1335–1344 (2010).

    Google Scholar 

  49. Alon, U. Biological networks: The tinkerer as an engineer. Science 301, 1866–1867 (2003).

    ADS  Google Scholar 

  50. Khanin, R. & Wit, E. How scale-free are biological networks. J. Comput. Biol. 13, 810–818 (2006).

    MathSciNet  Google Scholar 

  51. Colizza, V., Barrat, A., Barthelemy, M. & Vespignani, A. Prediction and predictability of global epidemics: The role of the airline transportation network. Proc. Natl Acad. Sci. USA 103, 2015–2020 (2006).

    ADS  MATH  Google Scholar 

  52. Bunde, A. & Havlin, S. Fractals and Disordered Systems (Springer, 1996).

    MATH  Google Scholar 

  53. Schneider, C. M., Araújo, N. A. M., Moreira, A. A., Havlin, S. & Herrmann, H. J. Mitigation of malicious attacks on networks. Proc. Natl Acad. Sci. USA 108, 3838–3841 (2011).

    ADS  Google Scholar 

  54. Cohen, R., Havlin, S. & Ben-Avraham, D. Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett. 91, 247901 (2003).

    ADS  Google Scholar 

  55. Chen, Y., Paul, G., Havlin, S., Liljeros, F. & Stanley, H. E. Finding a better immunization strategy. Phys. Rev. Lett. 101, 058701 (2008).

    ADS  Google Scholar 

  56. Braunstein, L. A., Buldyrev, S. V., Cohen, Havlin, S. & Stanley, H. E. Optimal paths in disordered complex networks. Phys. Rev. Lett. 91, 168701 (2003).

    ADS  Google Scholar 

  57. Pastor-Satorras, R. & Vespignani, A. Epidemic spreading in scale-free network. Phys. Rev. Lett. 86, 3200–3203 (2001).

    ADS  Google Scholar 

  58. Balcan, D. et al. Multiscale mobility networks and the large scale spreading of infectious diseases. Proc. Natl Acad. Sci. USA 106, 21484–21489 (2009).

    ADS  Google Scholar 

  59. Palla, G., Derenyi, I., Farkas, I. & Vicsek, T. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005).

    ADS  Google Scholar 

  60. Kossinets, G. & Watts, D. Empirical analysis of an evolving social network. Science 311, 88–90 (2006).

    ADS  MathSciNet  MATH  Google Scholar 

  61. Newman, M. E. J. The structure of scientific collaboration networks. Proc. Natl Acad. Sci. USA 98, 404–409 (2001).

    ADS  MathSciNet  MATH  Google Scholar 

  62. Girvan, M. & Newman, M. E. J. Community structure in social and biological networks. Proc. Natl Acad. Sci. USA 99, 7821–7826 (2002).

    ADS  MathSciNet  MATH  Google Scholar 

  63. Moreira, A. A., Andrade, J. S. Jr, Herrmann, H. J. & Indekeu, J. O. How to make a fragile network robust and vice versa. Phys. Rev. Lett. 102, 019701 (2009).

    ADS  Google Scholar 

  64. Lopez, E., Buldyrev, S. V., Havlin, S. & Stanley, H. E. Anomalous transport in scale-free networks. Phys. Rev. Lett. 94, 248701 (2005).

    ADS  Google Scholar 

  65. Boguñá, M. & Krioukov, D. Navigating ultrasmall worlds in ultrashort time. Phys. Rev. Lett. 102, 058701 (2009).

    ADS  Google Scholar 

  66. Leicht, E. A. & D’Souza, R. M. Percolation on interacting networks. Preprint at http://arxiv.org/abs/0907.0894. (2009).

  67. Rosato, V. Modeling interdependent infrastructures using interacting dynamical models. Int. J. Crit. Infrastruct. 4, 63–79 (2008).

    Google Scholar 

  68. US–Canada Power System Outage Task Force Final Report on the August 14th 2003 Blackout in the United States and Canada: Causes and Recommendations (The Task Force, 2004).

  69. Peerenboom, J., Fischer, R. & Whitfield, R. in Proc. CRIS/DRM/IIIT/NSF Workshop Mitigating the Vulnerability of Critical Infrastructures to Catastrophic Failures (2001).

  70. Rinaldi, S., Peerenboom, J. & Kelly, T. Identifying, understanding, and analyzing critical infrastructure interdepedencies. IEEE Control. Syst. Magn. 21, 11–25 (2001).

    Google Scholar 

  71. Yaǧan, O., Qian, D., Zhang, J. & Cochran, D. Optimal allocation of interconnecting links in cyber-physical systems: Interdependence, cascading failures and robustness. http://www.ece.umd.edu/ oyagan/Journals/Interdependent_Journal.pdf (2011).

  72. Vespignani, A. The fragility of interdependency. Nature 464, 984–985 (2010).

    ADS  Google Scholar 

  73. Buldyrev, S. V., Parshani, R., Paul, G., Stanley, H. E. & Havlin, S. Catastrophic cascade of failures in interdependent networks. Nature 464, 1025–1028 (2010).

    ADS  Google Scholar 

  74. Newman, M. E. J., Strogatz, S. H. & Watts, D. J. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118 (2001).

    ADS  Google Scholar 

  75. Shao, J., Buldyrev, S. V., Braunstein, L. A., Havlin, S. & Stanley, H. E. Structure of shells in complex networks. Phys. Rev. E 80, 036105 (2009).

    ADS  Google Scholar 

  76. 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).

    ADS  Google Scholar 

  77. 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).

    ADS  Google Scholar 

  78. Shao, J., Buldyrev, S. V., Havlin, S. & Stanley, H. E. Cascade of failures in coupled network systems with multiple support-dependence relations. Phys. Rev. E 83, 036116 (2011).

    ADS  MathSciNet  Google Scholar 

  79. Parshani, R., Rozenblat, C., Ietri, D., Ducruet, C. & Havlin, S. Inter-similarity between coupled networks. Europhys. Lett. 92, 68002–68006 (2010).

    ADS  Google Scholar 

  80. Gu, C. et al. Onset of cooperation between layered networks. Phys. Rev. E 84, 026101 (2011).

    ADS  Google Scholar 

  81. Cho, W., Coh, K. & Kim, I. Correlated couplings and robustness of coupled networks. Preprint at http://arxiv.org/abs/1010.4971. (2010).

  82. Buldyrev, S. V., Shere, N. W. & Cwilich, G. A. Interdependent networks with identical degrees of mutually dependent nodes. Phys. Rev. E 83, 016112 (2011).

    ADS  MathSciNet  Google Scholar 

  83. 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 (in the press). Preprint at http://arxiv.org/abs/1106.4128 (2011).

  84. Sachtjen, M. L., Carreras, B. A. & Lynch, V. E. Disturbances in a power transmission system. Phys. Rev. E 61, 4877–4882 (2000).

    ADS  Google Scholar 

  85. Motter, A. E. & Lai, Y. C. Cascade-based attacks on complex networks. Phys. Rev. E 66, 065102 (2002).

    ADS  Google Scholar 

  86. Moreno, Y., Pastor, S. R., Vázquez, A. & Vespignani, A. Critical load and congestion instabilities in scale-free networks. Europhys. Lett. 62, 292–298 (2003).

    ADS  Google Scholar 

  87. Motter, A. E. Cascade control and defense in complex networks. Phys. Rev. Lett. 93, 098701 (2004).

    ADS  Google Scholar 

  88. 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).

    ADS  Google Scholar 

  89. Bashan, A., Parshani, R. & Havlin, S. Percolation in networks composed of connectivity and dependency links. Phys. Rev. E 83, 051127 (2011).

    ADS  Google Scholar 

  90. Bashan, A. & Havlin, S. The combined effect of connectivity and dependency links on percolation of networks. J. Stat. Phys. 145, 686–695 (2011).

    ADS  MathSciNet  MATH  Google Scholar 

  91. Molloy, M. & Reed, B. The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput. 7, 295–305 (1998).

    MathSciNet  MATH  Google Scholar 

  92. Erdős, P. & Rényi, A. On random graphs I. Publ. Math. 6, 290–297 (1959).

    MathSciNet  MATH  Google Scholar 

  93. Erdős, P. & Rényi, A. On the evolution of random graphs. Inst. Hung. Acad. Sci. 5, 17–61 (1960).

    MathSciNet  MATH  Google Scholar 

  94. Bollobás, B. Random Graphs (Academic, 1985).

    MATH  Google Scholar 

  95. Schneider, C. M., Araújo, N. A. M., Havlin, S. & Herrmann, H. J. Towards designing robust coupled networks. Preprint at http://arxiv.org/abs/1106.3234 (2011).

  96. Gao, J., Buldyrev, S. V., Havlin, S. & Stanley, H. E. Robustness of a network of networks. Phys. Rev. Lett. 107, 195701 (2011).

    ADS  Google Scholar 

  97. Gao, J, Buldyrev, S. V., Havlin, S. & Stanley, H. E. Robustness of a tree-like network of interdependent networks. Preprint athttp://arxiv.org/abs/1108.5515 (2011).

  98. Suchecki, K. & Holyst, J. A. Ising model on two connected Barabasi–Albert networks. Phys. Rev. E 74, 011122 (2006).

    ADS  MathSciNet  Google Scholar 

  99. Donges, J. F., Schultz, H. C. H., Marwan, N., Zou, Y. & Kurths, J. Investigating the topology of interacting networks. Eur. Phys. J. B (2011, in the press).

Download references

Acknowledgements

We thank R. Parshani for helpful discussions. We thank the DTRA (Defense Threat Reduction Agency) and the Office of Naval Research for support. J.G. also thanks the Shanghai Key Basic Research Project (grant no 09JC1408000) and the National Natural Science Foundation of China (grant no 61004088) for support. S.V.B. acknowledges the partial support of this research through the B. W. Gamson Computational Science Center at Yeshiva College. S.H. thanks the European EPIWORK project, Deutsche Forschungsgemeinschaft (DFG) and the Israel Science Foundation for financial support.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Shlomo Havlin.

Ethics declarations

Competing interests

The authors declare no competing financial interests.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gao, J., Buldyrev, S., Stanley, H. et al. Networks formed from interdependent networks. Nature Phys 8, 40–48 (2012). https://doi.org/10.1038/nphys2180

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/nphys2180

This article is cited by

Search

Quick links

Nature Briefing

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing