- Letter
- Published:
Error and attack tolerance of complex networks
Naturevolume 406, pages378–382 (2000)Cite this article
53kAccesses
6144Citations
89Altmetric
ACorrigendum to this article was published on 25 January 2001
Abstract
Many complex systems display a surprising degree of tolerance against errors. For example, relatively simple organisms grow, persist and reproduce despite drastic pharmaceutical or environmental interventions, an error tolerance attributed to the robustness of the underlying metabolic network1. Complex communication networks2 display a surprising degree of robustness: although key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these and other complex systems is often attributed to the redundant wiring of the functional web defined by the systems' components. Here we demonstrate that error tolerance is not shared by all redundant systems: it is displayed only by a class of inhomogeneously wired networks, called scale-free networks, which include the World-Wide Web3,4,5, the Internet6, social networks7 and cells8. We find that such networks display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates. However, error tolerance comes at a high price in that these networks are extremely vulnerable to attacks (that is, to the selection and removal of a few nodes that play a vital role in maintaining the network's connectivity). Such error tolerance and attack vulnerability are generic properties of communication networks.
This is a preview of subscription content,access via your institution
Access options
Subscription info for Japanese customers
We have a dedicated website for our Japanese customers. Please go tonatureasia.com to subscribe to this journal.
Prices may be subject to local taxes which are calculated during checkout
Similar content being viewed by others
Component response rate variation underlies the stability of highly complex finite systems
References
Hartwell, L. H., Hopfield, J. J., Leibler, S. & Murray, A. W. From molecular to modular cell biology.Nature402, 47–52 (1999).
Claffy, K., Monk, T. E. et al. Internet tomography.Nature Web Matters [online] (7 Jan. 99) 〈http://helix.nature.com/webmatters/tomog/tomog.html〉 (1999).
Albert, R., Jeong, H. & Barabási, A.-L. Diameter of the World-Wide Web.Nature401, 130–131 ( 1999).
Kumar, R., Raghavan, P., Rajalopagan, S. & Tomkins, A. in Proc. 9th ACM Symp. on Principles of Database Systems 1–10 (Association for Computing Machinery, New York, 2000).
Huberman, B. A. & Adamic, L. A. Growth dynamics of the World-Wide Web.Nature401, 131 (1999).
Faloutsos, M., Faloutsos, P. & Faloutsos, C. On power-law relationships of the internet topology, ACM SIGCOMM '99.Comput. Commun. Rev.29, 251–263 (1999).
Wasserman, S. & Faust, K.Social Network Analysis (Cambridge Univ. Press, Cambridge, 1994).
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. & Barabási, A.-L. The large-scale organization of metabolic networks.Nature (in the press).
Erdös, P. & Rényi, A. On the evolution of random graphs.Publ. Math. Inst. Hung. Acad. Sci.5, 17–60 (1960).
Bollobás, B. Random Graphs (Academic, London, 1985).
Watts, D. J. & Strogatz, S. H. Collective dynamics of ‘small-world’ networks.Nature393, 440– 442 (1998).
Zegura, E. W., Calvert, K. L. & Donahoo, M. J. A quantitative comparison of graph-based models for internet topology.IEEE/ACM Trans. Network.5, 770–787 (1997).
Williams, R. J. & Martinez, N. D. Simple rules yield complex food webs.Nature404, 180 –183 (2000).
Maritan, A., Colaiori, F., Flammini, A., Cieplak, M. & Banavar, J. Universality classes of optimal channel networks.Science272, 984– 986 (1996).
Banavar, J. R., Maritan, A. & Rinaldo, A. Size and form in efficient transportation networks.Nature399, 130–132 (1999).
Barthélémy, M. & Amaral, L. A. N. Small-world networks: evidence for a crossover picture.Phys. Rev. Lett.82, 3180–3183 ( 1999).
Barabási, A.-L. & Albert, R. Emergence of scaling in random networks.Science286, 509– 511 (1999).
Barabási, A.-L., Albert, R. & Jeong, H. Mean-field theory for scale-free random networks. Physica A272, 173–187 ( 1999).
Redner, S. How popular is your paper? An empirical study of the citation distribution.Euro. Phys. J. B4, 131– 134 (1998).
Lawrence, S. & Giles, C. L. Accessibility of information on the web.Nature400, 107– 109 (1999).
Milgram, S. The small-world problem.Psychol. Today2, 60–67 (1967).
Bunde, A. & Havlin, S. (eds)Fractals and Disordered Systems (Springer, New York, 1996).
Paxson, V. End-to-end routing behavior in the internet.IEEE/ACM Trans. Network.5, 601–618 ( 1997).
Adamic, L. A. The small world web.Lect. Notes Comput. Sci.1696, 443–452 (1999).
Acknowledgements
We thank B. Bunker, K. Newman, Z. N. Oltvai and P. Schiffer for discussions. This work was supported by the NSF.
Author information
Authors and Affiliations
Department of Physics, 225 Nieuwland Science Hall, University of Notre Dame, Notre Dame, 46556, Indiana, USA
Réka Albert, Hawoong Jeong & Albert-László Barabási
- Réka Albert
You can also search for this author inPubMed Google Scholar
- Hawoong Jeong
You can also search for this author inPubMed Google Scholar
- Albert-László Barabási
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toAlbert-László Barabási.
Rights and permissions
About this article
Cite this article
Albert, R., Jeong, H. & Barabási, AL. Error and attack tolerance of complex networks.Nature406, 378–382 (2000). https://doi.org/10.1038/35019019
Received:
Accepted:
Issue Date:
