Robustness of spatial networks and networks of networks

Louis M. Shekhtman; Michael M. Danziger; Dana Vaknin; Shlomo Havlin

doi:10.1016/j.crhy.2018.09.005

Robustness of spatial networks and networks of networks

Louis M. Shekhtman ¹ ; Michael M. Danziger ²; Dana Vaknin ¹; Shlomo Havlin ^1,³

¹ Department of Physics, Bar-Ilan University, Ramat Gan, Israel
² Network Science Institute and Department of Physics, Northeastern University, Boston, USA
³ Tokyo Institute of Technology, Tokyo, Japan

Comptes Rendus. Physique, Spatial networks / Réseaux spatiaux, Volume 19 (2018) no. 4, pp. 233-243.

Abstract
Résumé

Many complex networks have recently been recognized to involve significant interdependence between different systems. Motivation comes primarily from infrastructures like power grids and communications networks, but also includes areas such as the human brain and finance. Interdependence implies that when components in one system fail, they lead to failures in the same system or other systems. This can then lead to additional failures finally resulting in a long cascade that can cripple the entire system. Furthermore, many of these networks, in particular infrastructure networks, are embedded in space and thus have unique spatial properties that significantly decrease their resilience to failures. Here we present a review of novel results on interdependent spatial networks and how cascading processes are affected by spatial embedding. We include various aspects of spatial embedding such as cases where dependencies are spatially restricted and localized attacks on nodes contained in some spatial region of the network. In general, we find that spatial networks are more vulnerable when they are interdependent and that they are more likely to undergo abrupt failure transitions than interdependent non-embedded networks. We also present results on recovery in spatial networks, the nature of cascades due to overload failures in these networks, and some examples of percolation features found in real-world traffic networks. Finally, we conclude with an outlook on future possible research directions in this area.

Récemment, il a été montré que de nombreux réseaux complexes font intervenir une interdépendence fondamentale entre différents systèmes. La motivation provient principalement des infrastructures telles que les réseaux électriques et les réseaux de communication, mais comprend également des domaines tels que le cerveau humain et la finance. L'interdépendance implique que, lorsque des composants d'un système tombent en panne, ils entraînent des défaillances dans le même système ou dans d'autres. Cela peut conduire à des défaillances supplémentaires, aboutissant finalement à une longue cascade susceptible de paralyser l'ensemble du système. En outre, nombre de ces réseaux, en particulier certaines infrastructures, sont intégrés dans l'espace et possèdent des propriétés spatiales uniques qui ont pour effet de réduire considérablement leur résilience aux pannes. Nous présentons également des résultats sur la guérison des réseaux spatiaux, la nature des cascades dues à des défaillances de surcharge dans ces réseaux, ainsi que quelques exemples choisis dans les réseaux de trafic réel et qui présentent des caractéristiques similaires à celles de la percolation. Enfin, nous concluons sur une discussion des futures directions de recherche possibles dans ce domaine.

Published online: 2018-05-01

DOI: 10.1016/j.crhy.2018.09.005

Keywords: Spatial networks, Networks of networks, Coupled networks, Infrastructure resilience
Mots-clés : Réseaux spatiaux, Réseaux de réseaux, Réseaux couplés, Résilience des infrastructures

Author's affiliations:

Louis M. Shekhtman ¹; Michael M. Danziger ²; Dana Vaknin ¹; Shlomo Havlin ^{1, 3}

¹ Department of Physics, Bar-Ilan University, Ramat Gan, Israel
² Network Science Institute and Department of Physics, Northeastern University, Boston, USA
³ Tokyo Institute of Technology, Tokyo, Japan

@article{CRPHYS_2018__19_4_233_0,
     author = {Louis M. Shekhtman and Michael M. Danziger and Dana Vaknin and Shlomo Havlin},
     title = {Robustness of spatial networks and networks of networks},
     journal = {Comptes Rendus. Physique},
     pages = {233--243},
     publisher = {Elsevier},
     volume = {19},
     number = {4},
     year = {2018},
     doi = {10.1016/j.crhy.2018.09.005},
     language = {en},
}

TY  - JOUR
AU  - Louis M. Shekhtman
AU  - Michael M. Danziger
AU  - Dana Vaknin
AU  - Shlomo Havlin
TI  - Robustness of spatial networks and networks of networks
JO  - Comptes Rendus. Physique
PY  - 2018
SP  - 233
EP  - 243
VL  - 19
IS  - 4
PB  - Elsevier
DO  - 10.1016/j.crhy.2018.09.005
LA  - en
ID  - CRPHYS_2018__19_4_233_0
ER  -

%0 Journal Article
%A Louis M. Shekhtman
%A Michael M. Danziger
%A Dana Vaknin
%A Shlomo Havlin
%T Robustness of spatial networks and networks of networks
%J Comptes Rendus. Physique
%D 2018
%P 233-243
%V 19
%N 4
%I Elsevier
%R 10.1016/j.crhy.2018.09.005
%G en
%F CRPHYS_2018__19_4_233_0

Louis M. Shekhtman; Michael M. Danziger; Dana Vaknin; Shlomo Havlin. Robustness of spatial networks and networks of networks. Comptes Rendus. Physique, Spatial networks / Réseaux spatiaux, Volume 19 (2018) no. 4, pp. 233-243. doi : 10.1016/j.crhy.2018.09.005. https://comptes-rendus.academie-sciences.fr/physique/articles/10.1016/j.crhy.2018.09.005/

References
Cited by

[1] R. Albert; H. Jeong; A.-L. Barabási Internet: diameter of the world-wide web, Nature, Volume 401 (1999) no. 6749, pp. 130-131

[2] D.J. Watts; S.H. Strogatz Collective dynamics of ‘small-world’ networks, Nature, Volume 393 ( Jun 1998 ) no. 6684, pp. 440-442

[3] A.-L. Barabási; R. Albert Emergence of scaling in random networks, Science, Volume 286 (1999) no. 5439, pp. 509-512

[4] D. Lazer; A.S. Pentland; L. Adamic; S. Aral; A.L. Barabasi; D. Brewer; N. Christakis; N. Contractor; J. Fowler; M. Gutmann et al. Life in the network: the coming age of computational social science, Science (N. Y.), Volume 323 (2009) no. 5915, p. 721

[5] A.-L. Barabasi; Z.N. Oltvai Network biology: understanding the cell's functional organization, Nat. Rev. Genet., Volume 5 (2004) no. 2, pp. 101-113

[6] O. Levy; B.A. Knisbacher; E.Y. Levanon; S. Havlin Integrating networks and comparative genomics reveals retroelement proliferation dynamics in hominid genomes, Sci. Adv., Volume 3 (2017) no. 10

[7] D. Helbing Traffic and related self-driven many-particle systems, Rev. Mod. Phys., Volume 73 (2001) no. 4, p. 1067

[8] D. Li; B. Fu; Y. Wang; G. Lu; Y. Berezin; H.E. Stanley; S. Havlin Percolation transition in dynamical traffic network with evolving critical bottlenecks, Proc. Natl. Acad. Sci. USA, Volume 112 (2015) no. 3, pp. 669-672

[9] R.N. Mantegna; H.E. Stanley Introduction to Econophysics: Correlations and Complexity in Finance, Cambridge University Press, 1999

[10] L. Wei; D.Y. Kenett; K. Yamasaki; H.E. Stanley; S. Havlin Ranking the economic importance of countries and industries, J. Netw. Theory Financ., Volume 3 (2017) no. 3, pp. 1-17

[11] J. Fan; J. Meng; Y. Ashkenazy; S. Havlin; H.J. Schellnhuber Network analysis reveals strongly localized impacts of El Niño, Proc. Natl. Acad. Sci. USA, Volume 114 (2017) no. 29, pp. 7543-7548

[12] J.F. Donges; Y. Zou; N. Marwan; J. Kurths Complex networks in climate dynamics, Eur. Phys. J. Spec. Top., Volume 174 (2009) no. 1, pp. 157-179

[13] R. Albert; H. Jeong; A.-L. Barabási Error and attack tolerance of complex networks, Nature, Volume 406 (2000) no. 6794, pp. 378-382

[14] R. Cohen; K. Erez; D. ben Avraham; S. Havlin Resilience of the Internet to random breakdowns, Phys. Rev. Lett., Volume 85 (2000), pp. 4626-4628

[15] D.S. Callaway; M.E.J. Newman; S.H. Strogatz; D.J. Watts Network robustness and fragility: percolation on random graphs, Phys. Rev. Lett., Volume 85 (2000), pp. 5468-5471

[16] R. Cohen; K. Erez; D. ben Avraham; S. Havlin Breakdown of the Internet under intentional attack, Phys. Rev. Lett., Volume 86 ( Apr. 2001 ), pp. 3682-3685

[17] S. Kirkpatrick Percolation and conduction, Rev. Mod. Phys., Volume 45 (1973), pp. 574-588

[18] D. Stauffer; A. Aharony Introduction to Percolation Theory, Taylor & Francis, 1994

[19] A. Bunde; S. Havlin Fractals and Disordered Systems, Springer Science & Business Media, 2012

[20] P. Hines; S. Blumsack; E.C. Sanchez; C. Barrows The topological and electrical structure of power grids, HICSS, IEEE (2010), pp. 1-10

[21] M. Barthélémy Spatial networks, Phys. Rep., Volume 499 (2011) no. 1–3, pp. 1-101

[22] S.V. Buldyrev; R. Parshani; G. Paul; H.E. Stanley; S. Havlin Catastrophic cascade of failures in interdependent networks, Nature, Volume 464 (2010) no. 7291, pp. 1025-1028

[23] J. Gao; S.V. Buldyrev; H.E. Stanley; S. Havlin Networks formed from interdependent networks, Nat. Phys., Volume 8 (2012) no. 1, pp. 40-48

[24] E.A. Leicht, R.M. D'Souza, Percolation on interacting networks. ArXiv e-prints, July 2009.

[25] M. De Domenico; A. Solé-Ribalta; E. Cozzo; M. Kivelä; Y. Moreno; M.A. Porter; S. Gómez; A. Arenas Mathematical formulation of multilayer networks, Phys. Rev. X, Volume 3 (2013)

[26] M. Kivelä; A. Arenas; M. Barthélémy; J.P. Gleeson; Y. Moreno; M.A. Porter Multilayer networks, J. Complex Netw., Volume 2 (2014) no. 3, pp. 203-271

[27] S.M. Rinaldi; J.P. Peerenboom; T.K. Kelly Identifying, understanding, and analyzing critical infrastructure interdependencies, IEEE Control Syst., Volume 21 (2001) no. 6, pp. 11-25

[28] D.S. Bassett; N.F. Wymbs; M.A. Porter; P.J. Mucha; J.M. Carlson; S.T. Grafton Dynamic reconfiguration of human brain networks during learning, Proc. Natl. Acad. Sci. USA, Volume 108 (2011) no. 18, pp. 7641-7646

[29] M.J.O. Pocock; D.M. Evans; J. Memmott The robustness and restoration of a network of ecological networks, Science, Volume 335 (2012) no. 6071, pp. 973-977

[30] D.Y. Kenett; S. Havlin Network science: a useful tool in economics and finance, Mind Soc. (2015), pp. 1-13

[31] G.J. Baxter; S.N. Dorogovtsev; A.V. Goltsev; J.F.F. Mendes Avalanche collapse of interdependent networks, Phys. Rev. Lett., Volume 109 (2012)

[32] F. Radicchi; A. Arenas Abrupt transition in the structural formation of interconnected networks, Nat. Phys., Volume 9 (2013) no. 11, pp. 717-720

[33] D. Zhou; A. Bashan; R. Cohen; Y. Berezin; N. Shnerb; S. Havlin Simultaneous first- and second-order percolation transitions in interdependent networks, Phys. Rev. E, Volume 90 ( Jul 2014 )

[34] J. Gao; D. Li; S. Havlin From a single network to a network of networks, Nat. Sci. Rev., Volume 1 (2014) no. 3, pp. 346-356

[35] R. Parshani; S.V. Buldyrev; S. Havlin Critical effect of dependency groups on the function of networks, Proc. Natl. Acad. Sci. USA, Volume 108 (2011) no. 3, pp. 1007-1010

[36] J. Gao; S.V. Buldyrev; H.E. Stanley; X. Xu; S. Havlin Percolation of a general network of networks, Phys. Rev. E, Volume 88 (2013)

[37] R. Parshani; S.V. Buldyrev; S. Havlin Interdependent networks: reducing the coupling strength leads to a change from a first to second order percolation transition, Phys. Rev. Lett., Volume 105 (2010)

[38] J. Gao; S.V. Buldyrev; S. Havlin; H.E. Stanley Robustness of a network formed by n interdependent networks with a one-to-one correspondence of dependent nodes, Phys. Rev. E, Volume 85 (2012)

[39] J. Gao; S.V. Buldyrev; S. Havlin; H.E. Stanley Robustness of a network of networks, Phys. Rev. Lett., Volume 107 (2011)

[40] J. Gao; S.V. Buldyrev; H.E. Stanley; S. Havlin Networks formed from interdependent networks, Nat. Phys., Volume 8 (2012) no. 1, pp. 40-48

[41] P. Erdős; A. Rényi On the strength of connectedness of a random graph, Acta Math. Acad. Sci. Hung., Volume 12 (1964) no. 1–2, pp. 261-267

[42] Y. Hu; D. Zhou; R. Zhang; Z. Han; C. Rozenblat; S. Havlin Percolation of interdependent networks with intersimilarity, Phys. Rev. E, Volume 88 (2013)

[43] J.Y. Kim; K.-I. Goh Coevolution and correlated multiplexity in multiplex networks, Phys. Rev. Lett., Volume 111 (2013)

[44] S.D.S. Reis; Y. Hu; A. Babino; J.S. Andrade; S. Canals; M. Sigman; H.A. Makse Avoiding catastrophic failure in correlated networks of networks, Nat. Phys., Volume 10 (2014) no. 10, pp. 762-767

[45] G. Bianconi; S.N. Dorogovtsev; J.F.F. Mendes Mutually connected component of networks of networks with replica nodes, Phys. Rev. E, Volume 91 (2015) no. 1

[46] R. Parshani; C. Rozenblat; D. Ietri; C. Ducruet; S. Havlin Inter-similarity between coupled networks, Europhys. Lett., Volume 92 (2010) no. 6

[47] B. Min; S.D. Yi; K.-M. Lee; K-I. Goh Network robustness of multiplex networks with interlayer degree correlations, Phys. Rev. E, Volume 89 (2014) no. 4

[48] B. Min; S. Lee; K.-M. Lee; K-I. Goh Link overlap, viability, and mutual percolation in multiplex networks, Chaos Solitons Fractals, Volume 72 (2015), pp. 49-58

[49] D. Cellai; E. López; J. Zhou; J.P. Gleeson; G. Bianconi Percolation in multiplex networks with overlap, Phys. Rev. E, Volume 88 (2013)

[50] G. Bianconi Statistical mechanics of multiplex networks: entropy and overlap, Phys. Rev. E, Volume 87 (2013)

[51] F. Radicchi; G. Bianconi Redundant interdependencies boost the robustness of multiplex networks, Phys. Rev. X, Volume 7 (2017) no. 1

[52] X. Yuan; Y. Hu; H.E. Stanley; S. Havlin Eradicating catastrophic collapse in interdependent networks via reinforced nodes, Proc. Natl. Acad. Sci. USA, Volume 114 (2017) no. 13, pp. 3311-3315

[53] N.K. Panduranga; J. Gao; X. Yuan; H.E. Stanley; S. Havlin Generalized model for k-core percolation and interdependent networks, Phys. Rev. E, Volume 96 (2017)

[54] X. Yuan; Y. Dai; H.E. Stanley; S. Havlin k-Core percolation on complex networks: comparing random, localized, and targeted attacks, Phys. Rev. E, Volume 93 (2016) no. 6

[55] N. Azimi-Tafreshi; J. Gómez-Gardenes; S.N. Dorogovtsev k-Core percolation on multiplex networks, Phys. Rev. E, Volume 90 (2014) no. 3

[56] A. Bashan; Y. Berezin; S.V. Buldyrev; S. Havlin The extreme vulnerability of interdependent spatially embedded networks, Nat. Phys., Volume 9 (2013), pp. 667-672

[57] L. Daqing; K. Kosmidis; A. Bunde; S. Havlin Dimension of spatially embedded networks, Nat. Phys., Volume 7 (2011) no. 6, pp. 481-484

[58] B. Gross; M.M. Danziger; S.V. Buldyrev; S. Havlin Bi-universality characterizes a realistic spatial network model, 2017 (arXiv preprint) | arXiv

[59] L. Wei; A. Bashan; S.V. Buldyrev; H.E. Stanley; S. Havlin Cascading failures in interdependent lattice networks: the critical role of the length of dependency links, Phys. Rev. Lett., Volume 108 (2012)

[60] L.M. Shekhtman; Y. Berezin; M.M. Danziger; S. Havlin Robustness of a network formed of spatially embedded networks, Phys. Rev. E, Volume 90 (2014)

[61] M.M. Danziger; A. Bashan; Y. Berezin; S. Havlin Percolation and cascade dynamics of spatial networks with partial dependency, J. Complex Netw., Volume 2 (2014) no. 4, pp. 460-474

[62] M.M. Danziger; L.M. Shekhtman; Y. Berezin; S. Havlin The effect of spatiality on multiplex networks, Europhys. Lett., Volume 115 (2016) no. 3

[63] S. Gómez; A. Díaz-Guilera; J. Gómez-Gardeñes; C.J. Pérez-Vicente; Y. Moreno; A. Arenas Diffusion dynamics on multiplex networks, Phys. Rev. Lett., Volume 110 (2013)

[64] B.M. Waxman Routing of multipoint connections, IEEE J. Sel. Areas Commun., Volume 6 (1988) no. 9, pp. 1617-1622

[65] B. Gross; D. Vaknin; M.M. Danziger; S. Havlin Multi-universality and localized attacks in spatially embedded networks, APEC-SSS2016 (2017), p. 011002

[66] S.-W. Son; P. Grassberger; M. Paczuski Percolation transitions are not always sharpened by making networks interdependent, Phys. Rev. Lett., Volume 107 (2011)

[67] Y. Berezin; A. Bashan; S. Havlin Comment on “percolation transitions are not always sharpened by making networks interdependent”, Phys. Rev. Lett., Volume 111 (2013) no. 18

[68] Y. Berezin; A. Bashan; M.M. Danziger; D. Li; S. Havlin Localized attacks on spatially embedded networks with dependencies, Sci. Rep., Volume 5 (2015)

[69] S. Shao; X. Huang; H.E. Stanley; S. Havlin Percolation of localized attack on complex networks, New J. Phys., Volume 17 (2015) no. 2

[70] B. Sapoval; M. Rosso; J.F. Gouyet The fractal nature of a diffusion front and the relation to percolation, J. Phys. Lett., Volume 46 (1985) no. 4, pp. 149-156

[71] D. Vaknin; M.M. Danziger; S. Havlin Spreading of localized attacks in spatial multiplex networks, New J. Phys., Volume 19 (2017) no. 7

[72] J. Zhao; D. Li; H. Sanhedrai; R. Cohen; S. Havlin Spatio-temporal propagation of cascading overload failures in spatially embedded networks, Nat. Commun., Volume 7 (2016)

[73] R. Kinney; P. Crucitti; R. Albert; V. Latora Modeling cascading failures in the North American power grid, Eur. Phys. J. B, Condens. Matter Complex Syst., Volume 46 (2005) no. 1, pp. 101-107

[74] Y. Kim; W.C. Lau; M.C. Chuah; H.J. Chao Packetscore: statistics-based overload control against distributed denial-of-service attacks, INFOCOM 2004. Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 4, IEEE, 2004, pp. 2594-2604

[75] A.E. Motter; Y.-C. Lai Cascade-based attacks on complex networks, Phys. Rev. E, Volume 66 (2002)

[76] A. Majdandzic; B. Podobnik; S.V. Buldyrev; D.Y. Kenett; S. Havlin; H.E. Stanley Spontaneous recovery in dynamical networks, Nat. Phys., Volume 10 (2013) no. 1, pp. 34-38

[77] A. Majdandzic; L.A. Braunstein; C. Curme; I. Vodenska; S. Levy-Carciente; H.E. Stanley; S. Havlin Multiple tipping points and optimal repairing in interacting networks, Nat. Commun., Volume 7 (2016)

[78] L. Böttcher; M. Luković; J. Nagler; S. Havlin; H.J. Herrmann Failure and recovery in dynamical networks, Sci. Rep., Volume 7 (2017)

[79] Y. Shang Localized recovery of complex networks against failure, Sci. Rep., Volume 6 (2016)

[80] F. Hu; C.H. Yeung; S. Yang; W. Wang; A. Zeng Recovery of infrastructure networks after localised attacks, Sci. Rep., Volume 6 (2016)

[81] M.A. Di Muro; C.E. La Rocca; H.E. Stanley; S. Havlin; L.A. Braunstein Recovery of interdependent networks, Sci. Rep., Volume 6 (2016)

[82] S. Shai; D.Y. Kenett; Y.N. Kenett; M. Faust; S. Dobson; S. Havlin Critical tipping point distinguishing two types of transitions in modular network structures, Phys. Rev. E, Volume 92 (2015)

[83] L.M. Shekhtman; S. Shai; S. Havlin Resilience of networks formed of interdependent modular networks, New J. Phys., Volume 17 (2015) no. 12

[84] F. Wang; D. Li; X. Xu; R. Wu; S. Havlin Percolation properties in a traffic model, Europhys. Lett., Volume 112 (2015) no. 3

[85] G. Zeng; D. Li; L. Gao; Z. Gao; S. Havlin Switch of critical percolation modes in dynamical city traffic, 2017 (arXiv preprint) | arXiv

Cited by Sources:

Comments - Policy