Model for cascading failures in complex networks

Paolo Crucitti; Vito Latora; Massimo Marchiori

doi:10.1103/PhysRevE.69.045104

Rapid Communication
Access by Xinjiang University

Model for cascading failures in complex networks

Paolo Crucitti¹, Vito Latora², and Massimo Marchiori³

¹Scuola Superiore di Catania, Via S. Paolo 73, 95123 Catania, Italy
²Dipartimento di Fisica e Astronomia, Università di Catania, and INFN, Sezione di Catania, Via S. Sofia 64, 95123 Catania, Italy
³W3C and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA

PDF

Phys. Rev. E 69, 045104(R) – Published 29 April, 2004

DOI: https://doi.org/10.1103/PhysRevE.69.045104

Abstract

Large but rare cascades triggered by small initial shocks are present in most of the infrastructure networks. Here we present a simple model for cascading failures based on the dynamical redistribution of the flow on the network. We show that the breakdown of a single node is sufficient to collapse the efficiency of the entire system if the node is among the ones with largest load. This is particularly important for real-world networks with a highly hetereogeneous distribution of loads as the Internet and electrical power grids.

References (32)

S.N. Dorogovtesev and J.F.F. Mendes, Evolution of Networks (Oxford University Press, Oxford, 2003).
S.H. Strogatz, Nature (London) 410, 268 (2001).
V. Jacobson, Comput. Commun. Rev. 18, 314 (1988).
R. Guimerà, A. Arenas, A. Díaz-Guilera, and F. Giralt, Phys. Rev. E 66, 026704 (2002).
B.A. Carreras, D.E. Newman, I. Dolrou, and A.B. Poole, in Proceedings of Hawaii International Conference on System Sciences, Maui, Hawaii, 2000 (unpublished).
M.L. Sachtjen, B.A. Carreras, and V.E. Lynch, Phys. Rev. E 61, 4877 (2000).
J. Glanz and R. Perez-Pena, “90 Seconds That Left Tens of Millions of People in the Dark,” New York Times, August 26, 2003.
D.J. Watts, Proc. Natl. Acad. Sci. U.S.A. 99, 5766 (2002).
R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 406, 378 (2000); 409, 542(E) (2001).
P. Holme, B.J. Kim, C.N. Yoon, and S.K. Han, Phys. Rev. E 65, 056109 (2002).
P. Crucitti, V. Latora, M. Marchiori, and A. Rapisarda, Physica A 320, 622 (2003).
M. Girvan and M.E.J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 8271 (2002).
A.E. Motter, T. Nishikawa, and Y. Lai, Phys. Rev. E 66, 065103 (2002).
A.E. Motter and Y. Lai, Phys. Rev. E 66, 065102(R) (2002).
Y. Moreno, R. Pastor-Satorras, A. Vázquez, and A. Vespignani, Europhys. Lett. 62, 292 (2003).
Y. Moreno, J.B. Gomez, and A.F. Pacheco, Europhys. Lett. 58, 630 (2002).
V. Latora and M. Marchiori, Phys. Rev. Lett. 87, 198701 (2001).
S. Wasserman and K. Faust, Social Networks Analysis (Cambridge University Press, Cambridge, 1994).
The model can be easily generalized to directed graphs.
In the case of an unweighted graph $e_{ij}$ is 1 if there is an arc joining node i to node j, and 0 otherwise.
J. Smith, Commun. ACM 31, 1202 (1988).
R. Jain, The Art of Computer Systems Performance Analysis (Wiley, New York, 1991).
The harmonic composition of N numbers $x_{1} {, x}_{2}, \dots {, x}_{N}$ is defined as $[\sum_{i = 1}^{N} {(1 / x}_{N})]^{- 1} .$
K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 87, 278701 (2001).
Another possibility which gives the same results is to set $C_{i} = α \max_{j} L_{j} (0) \forall i = 1, 2, \dots, N .$
As an initial damage to the network here we consider the removal of a node, although the dynamics of the model can be started by the removal of one arc if one wants to simulate, for instance, the breakdown of a line in an electrical power grid.
P. Erdös and A. Rényi, Publ. Math. (Debrecen) 6, 290 (1959).
A.-L. Barabási and R. Albert, Science 286, 509 (1999).
For load-based removals in BA scale-free graphs we have found that $α_{c}$ is independent of the size of the system. In fact, we have obtained $α_{c} = 1.28 \pm 0.05,$ 1.3±0.05, 1.28±0.05, respectively, for $N = 1500,$ 2000, 2500. Such a result is similar to that which is obtained in a simpler model, the fiber-bundle model, studied in Ref. [16].
R. Pastor-Satorras, A. Vázquez, and A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001).
http://moat.nlanr.net/AS/Data/ASconnlist.20000102.946809601.
D.J. Watts and S.H. Strogatz, Nature (London) 393, 440 (1998).

[c1] S.N. Dorogovtesev and J.F.F. Mendes, Evolution of Networks (Oxford University Press, Oxford, 2003).

[c2] S.H. Strogatz, Nature (London) 410, 268 (2001).

[c3] V. Jacobson, Comput. Commun. Rev. 18, 314 (1988).

[c4] R. Guimerà, A. Arenas, A. Díaz-Guilera, and F. Giralt, Phys. Rev. E 66, 026704 (2002).

[c5] B.A. Carreras, D.E. Newman, I. Dolrou, and A.B. Poole, in Proceedings of Hawaii International Conference on System Sciences, Maui, Hawaii, 2000 (unpublished).

[c6] M.L. Sachtjen, B.A. Carreras, and V.E. Lynch, Phys. Rev. E 61, 4877 (2000).

[c7] J. Glanz and R. Perez-Pena, “90 Seconds That Left Tens of Millions of People in the Dark,” New York Times, August 26, 2003.

[c8] D.J. Watts, Proc. Natl. Acad. Sci. U.S.A. 99, 5766 (2002).

[c9] R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 406, 378 (2000); 409, 542(E) (2001).

[c10] P. Holme, B.J. Kim, C.N. Yoon, and S.K. Han, Phys. Rev. E 65, 056109 (2002).

[c11] P. Crucitti, V. Latora, M. Marchiori, and A. Rapisarda, Physica A 320, 622 (2003).

[c12] M. Girvan and M.E.J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 8271 (2002).

[c13] A.E. Motter, T. Nishikawa, and Y. Lai, Phys. Rev. E 66, 065103 (2002).

[c14] A.E. Motter and Y. Lai, Phys. Rev. E 66, 065102(R) (2002).

[c15] Y. Moreno, R. Pastor-Satorras, A. Vázquez, and A. Vespignani, Europhys. Lett. 62, 292 (2003).

[c16] Y. Moreno, J.B. Gomez, and A.F. Pacheco, Europhys. Lett. 58, 630 (2002).

[c17] V. Latora and M. Marchiori, Phys. Rev. Lett. 87, 198701 (2001).

[c18] S. Wasserman and K. Faust, Social Networks Analysis (Cambridge University Press, Cambridge, 1994).

[c19] The model can be easily generalized to directed graphs.

[c20] In the case of an unweighted graph $e_{ij}$ is 1 if there is an arc joining node i to node j, and 0 otherwise.

[c21] J. Smith, Commun. ACM 31, 1202 (1988).

[c22] R. Jain, The Art of Computer Systems Performance Analysis (Wiley, New York, 1991).

[c23] The harmonic composition of N numbers $x_{1} {, x}_{2}, \dots {, x}_{N}$ is defined as $[\sum_{i = 1}^{N} {(1 / x}_{N})]^{- 1} .$

[c24] K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 87, 278701 (2001).

[c25] Another possibility which gives the same results is to set $C_{i} = α \max_{j} L_{j} (0) \forall i = 1, 2, \dots, N .$

[c26] As an initial damage to the network here we consider the removal of a node, although the dynamics of the model can be started by the removal of one arc if one wants to simulate, for instance, the breakdown of a line in an electrical power grid.

[c27] P. Erdös and A. Rényi, Publ. Math. (Debrecen) 6, 290 (1959).

[c28] A.-L. Barabási and R. Albert, Science 286, 509 (1999).

[c29] For load-based removals in BA scale-free graphs we have found that $α_{c}$ is independent of the size of the system. In fact, we have obtained $α_{c} = 1.28 \pm 0.05,$ 1.3±0.05, 1.28±0.05, respectively, for $N = 1500,$ 2000, 2500. Such a result is similar to that which is obtained in a simpler model, the fiber-bundle model, studied in Ref. [16].

[c30] R. Pastor-Satorras, A. Vázquez, and A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001).

[c31] http://moat.nlanr.net/AS/Data/ASconnlist.20000102.946809601.

[c32] D.J. Watts and S.H. Strogatz, Nature (London) 393, 440 (1998).

Physical Review E

Export citation

Export citation

Model for cascading failures in complex networks

Abstract

References (32)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation