- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Rapid Communication
  • Access by Xinjiang University

Cascade-based attacks on complex networks

Adilson E. Motter1,* and Ying-Cheng Lai1,2

  • 1Department of Mathematics, Center for Systems Science and Engineering Research, Arizona State University, Tempe, Arizona 85287
  • 2Departments of Electrical Engineering and Physics, Arizona State University, Tempe, Arizona 85287

  • *Electronic address: motter@chaos3.la.asu.edu
PDF

Phys. Rev. E 66, 065102(R) – Published 20 December, 2002

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

Abstract

We live in a modern world supported by large, complex networks. Examples range from financial markets to communication and transportation systems. In many realistic situations the flow of physical quantities in the network, as characterized by the loads on nodes, is important. We show that for such networks where loads can redistribute among the nodes, intentional attacks can lead to a cascade of overload failures, which can in turn cause the entire or a substantial part of the network to collapse. This is relevant for real-world networks that possess a highly heterogeneous distribution of loads, such as the Internet and power grids. We demonstrate that the heterogeneity of these networks makes them particularly vulnerable to attacks in that a large-scale cascade may be triggered by disabling a single key node. This brings obvious concerns on the security of such systems.

View figure in article

References (36)

  1. S.H. Strogatz, Nature (London) 410, 268 (2001).
  2. R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  3. R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 406, 378 (2000).
  4. D.J. Watts and S.H. Strogatz, Nature (London) 393, 440 (1998).
  5. A.-L. Barabási and R. Albert, Science 286, 509 (1999).
  6. R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 85, 4626 (2000).
  7. D.S. Callaway, M.E.J. Newman, S.H. Strogatz, and D.J. Watts, Phys. Rev. Lett. 85, 5468 (2000).
  8. R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 86, 3682 (2001).
  9. A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, Comput. Netw. 33, 309 (2000).
  10. D. J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness (Princeton University Press, Princeton, 1999).
  11. A. P. S. de Moura, Y.-C. Lai, A. E. Motter, and P. Dasgupta (unpublished).
  12. D.J. Watts, Proc. Natl. Acad. Sci. U.S.A. 99, 5766 (2002).
  13. Y. Moreno, J.B. Gómez, and A.F. Pacheco, Europhys. Lett. 58, 630 (2002).
  14. 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).
  15. M.L. Sachtjen, B.A. Carreras, and V.E. Lynch, Phys. Rev. E 61, 4877 (2000).
  16. R. Pastor-Satorras, A. Vázquez, and A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001).
  17. W. Willinger, R. Govindan, S. Jamin, V. Paxson, and S. Shenker, Proc. Natl. Acad. Sci. U.S.A. 99, 2573 (2002).
  18. K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 88, 108701 (2002).
  19. R. Guimerà, A. Arenas, A. Días-Guilera, and F. Giralt, Phys. Rev. E 66, 026704 (2002).
  20. V. Jacobson, Comput. Commun. Rev. 18, 314 (1988).
  21. M.E.J. Newman, Phys. Rev. E 64, 016132 (2001).
  22. K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 87, 278701 (2001).
  23. P. Holme and B.J. Kim, Phys. Rev. E 65, 066109 (2002).
  24. A different model and mechanism for overload breakdown in growing networks has been considered by Holme and Kim in Ref. [23]. These authors focus on overloads caused by the growth of the network. Their model assigns the same capacity to every node in the network. In their analysis, when a node is overloaded, the links to that node are removed, but the node itself is not removed and can be reconnected in the future. Their conclusion is that, to avoid overloads, the capacity must grow with the size of the network. Our model is different from the model in Ref. [23] as we assume the capacity to be node dependent and the failed nodes to be permanently removed from the network. More importantly, we address the issues of intentional attack and random breakdown, and we study how the network collapses under overload failures induced by them. We assume that the time scale for these events is much smaller than the time scale in which the network grows.
  25. S. Redner, Eur. Phys. J. B 4, 131 (1998).
  26. M. Faloutsos, P. Faloutsos, and C. Faloutsos, Comput. Commun. Rev. 29, 251 (1999).
  27. M.E.J. Newman, S.H. Strogatz, and D.J. Watts, Phys. Rev. E 64, 026118 (2001).
  28. A.E. Motter, T. Nishikawa, and Y.-C. Lai, Phys. Rev. E (to be published).
  29. P. Erdös and A. Rényi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
  30. http://moat.nlanr.net/AS/Data/ASconnlist.20000102.946809601
  31. ftp://ftp.santafe.edu/pub/duncan/power_unweighted
  32. L.A.N. Amaral, A. Scala, M. Barthélémy, and H.E. Stanley, Proc. Natl. Acad. Sci. U.S.A. 97, 11149 (2000).
  33. D. Kennedy, Science 295, 405 (2002).
  34. R.V. Solé and J.M. Montoya, Proc. R. Soc. London, Ser. B 268, 2039 (2001).
  35. H. Jeong, S.P. Mason, A.-L. Barabási, and Z.N. Oltvai, Nature (London) 411, 41 (2001).
  36. P. Holme, B.J. Kim, C.N. Yoon, and S.K. Han, Phys. Rev. E 65, 056109 (2002).

Outline

Information

Phys. Rev. E 66, 065102(R)– Published 20 December, 2002
  • Received 6 August 2002

© 2002 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation