PaperlayerView exact revision on arXiv

Source-linked AI summary

Error and attack tolerance of complex networks

Reka Albert, Hawoong Jeong, Albert-Laszlo Barabasi

arXiv:cond-mat/0008064v1cond-mat.dis-nncond-mat.stat-mech

TL;DR

Little is known about how errors and attacks affect large-scale network connectivity despite efforts to build error-tolerant communication components. The paper uses model-based analysis of large-scale network connectivity under deliberate attacks that remove nodes in decreasing order of connectivity. Scale-free networks remain communicatively unaffected when as high as 5% of nodes fail, but targeted removal of highly connected nodes fragments them.

  • Problem

    Little is known about how errors and attacks affect large-scale network connectivity despite efforts to build error-tolerant communication components.

    Source: p. 5

  • Method

    The paper uses model-based analysis of large-scale network connectivity under deliberate attacks that remove nodes in decreasing order of connectivity.

    Source: pp. 4–5

  • Results

    Scale-free networks remain communicatively unaffected when as high as 5% of nodes fail, but targeted removal of highly connected nodes fragments them.

    Source: pp. 3, 5

  • Takeaways & Limitations

    Error tolerance is characteristic of inhomogeneously wired scale-free networks, whereas their hub dependence creates a high vulnerability to attacks.

    Source: pp. 3, 5, 6

    The World Wide Web analysis is limited to a sample because no complete topological map of the Web is available.

    Source: p. 6

Abstract

from arXiv · show

Many complex systems, such as communication networks, display a surprising degree of robustness: while key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these complex systems is often attributed to the redundant wiring of the functional web defined by the systems' components. In this paper we demonstrate that error tolerance is not shared by all redundant systems, but it is displayed only by a class of inhomogeneously wired networks, called scale-free networks. We find that scale-free networks, describing a number of systems, such as the World Wide Web, Internet, social networks or a cell, display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected by even unrealistically high failure rates. However, error tolerance comes at a high price: these networks are extremely vulnerable to attacks, i.e. to the selection and removal of a few nodes that play the most important role in assuring the network's connectivity.

FIGURES

The figures contrast homogeneous exponential networks with highly inhomogeneous scale-free networks and compare their responses to random failures and targeted attacks.

FIGURES

  • Scale-free networks concentrate connectivity in a few hubs, reaching more than 60% of nodes through the five most connected nodes versus 27% in exponential networks.Both networks contain 130 nodes and 215 links (⟨k⟩= 3.3).Source: Figure 1 · p. 11

SF E

  • The diameter of an unperturbed scale-free network is smaller than that of an exponential network, indicating more efficient use of available links.The comparison uses networks with N = 10,000 nodes and 20,000 links (⟨k⟩= 4).Source: Figure 2 · p. 12

Internet

Figure 3 compares fragmentation under random failures and targeted attacks across exponential and scale-free models, the Internet, and the World Wide Web.

Internet

  • Across the scale-free model, Internet, and World Wide Web, attacks and errors produce the same qualitative response despite differences in γ, ⟨k⟩, and clustering coefficient.Those network differences change the critical fraction and magnitudes, not the nature of the response.Source: Figure 3 · p. 13
  • Under random failures, scale-free-network fragmentation has an extremely delayed critical point, with the main cluster persisting until it is almost completely deflated.A small isolated-cluster peak appears only near fmax ≃0.75, where ⟨smax⟩≃1.06.Source: Figure 3 · p. 13
  • For the World Wide Web under attack, the average fragment size rises abruptly at f_c = 0.067, peaks near ⟨smax⟩≃60, and then rapidly declines.The attack ordering uses nodes ranked by outgoing links, kout.Source: Figure 3 · p. 13

Failure

Figure 4 summarizes distinct fragmentation scenarios: attacks rapidly destroy the large cluster, while random failures in scale-free networks detach only small fragments and preserve it.

Failure

  • At f = 0.18, targeted attack fragments the scale-free network, while random failures leave a large cluster of size 8,000 alongside isolated clusters of sizes 1 through 5.The figure contrasts the same scale-free network under attacks and random failures.Source: Figure 4 · p. 14
  • Even at the unrealistically high random-failure rate f = 0.45, the large cluster persists and broken-off fragments remain no larger than 11 nodes.This differs from the attack scenario, where the network fragments at lower removal fractions.Source: Figure 4 · p. 14
  • Exponential networks under failures or attacks, and scale-free networks under attacks, lose their large cluster at a critical fraction and then fragment into small components.Before the transition, a large cluster coexists with fragments; afterward, clusters range roughly from single nodes to size 100 and later mostly singletons or pairs.Source: Figure 4 · p. 14

Related papers

Loading cond-mat/0008064v1…