Skip to main content

Robustness and Percolation

Module 5: Complex Networks

NoteReading
  • Compulsory: Albert et al. (2000) (Figures 2 and 3).
  • Recommended: Newman (2003), Sections 3.4 and 8.1; Molloy and Reed (1995).
  • What the paper did: Albert, Jeong and Barabási compared an exponential network (Poisson degrees) with a scale-free network with the same number of nodes and links (10,000 nodes in the simulations) and removed nodes either at random or from the highest degree down, following the diameter and the size of the largest cluster. For the scale-free network the diameter did not change under random removal of up to 5% of the nodes, while removing the 5% most connected nodes doubled it; the scale-free network broke apart under attack at a critical fraction of about 0.18, below the value of about 0.28 for the exponential network. They found the same qualitative behaviour in a sample of the Internet at the autonomous-system level and in a sample of the World-Wide Web with 325,729 nodes: for the Internet, random removal of 2.5% of the nodes left the diameter unchanged while attack on the same percentage more than tripled it. The paper is a numerical study; the analytical treatment of the same question came later (Callaway et al. 2000; Cohen et al. 2000).

How much of a network can you remove before it falls apart? You measure the answer with the giant component: the largest connected component, when its size is a finite fraction of \(N\). Let \(S(f)\) be the fraction of the original nodes that stay in the largest component after you remove a fraction \(f\) of the nodes. Removing nodes and asking whether a giant component survives is a site percolation problem (Callaway et al. 2000; Newman 2003, sec. 8.1).

The Molloy-Reed criterion

Consider a random graph with a given degree distribution \(p_k\) and no other structure (the configuration model). Molloy and Reed proved that, as \(N \to \infty\), a giant component exists almost surely when

\[ \sum_k k(k-2)\, p_k > 0 \quad \Longleftrightarrow \quad \kappa \equiv \frac{\langle k^2 \rangle}{\langle k \rangle} > 2, \]

and does not exist when the sum is negative (Molloy and Reed 1995). The intuition: follow a random edge to a node. That node has on average \(\kappa - 1\) further edges. The branching process started this way keeps growing when \(\kappa - 1 > 1\).

Random failure

Remove each node independently with probability \(f\). Cohen et al. applied the criterion to the diluted graph and found the critical fraction (Cohen et al. 2000)

\[ f_c = 1 - \frac{1}{\kappa_0 - 1}, \qquad \kappa_0 = \frac{\langle k^2 \rangle}{\langle k \rangle} \text{ of the intact network.} \]

  • For an Erdős-Rényi graph, \(p_k\) is Poisson, \(\kappa_0 = \langle k \rangle + 1\), and \(f_c = 1 - 1/\langle k \rangle\).
  • For a scale-free distribution \(p_k \sim k^{-\gamma}\) with \(2 < \gamma \le 3\), \(\langle k^2 \rangle\) diverges as \(N \to \infty\), so \(f_c \to 1\). An infinite network of this type keeps a giant component under almost any rate of random failure. A finite network has a finite \(\kappa_0\) and a threshold \(f_c < 1\) (Cohen et al. 2000).

Targeted attack

Now remove the nodes with the highest degree first. Albert, Jeong and Barabási showed in simulations that scale-free networks are tolerant to random failure but fragile under this attack: removing a few hubs breaks them apart much faster than an Erdős-Rényi graph with the same \(N\) and \(E\) (Albert et al. 2000). Callaway et al. derived the same behaviour analytically for degree-dependent removal (Callaway et al. 2000).

Generated example

Figure 1 compares a Barabási-Albert graph with an Erdős-Rényi graph that has the same number of nodes and edges. The attack uses the degree ranking of the intact graph.

BA: <k> = 3.99, kappa0 = 11.13, predicted f_c (random) = 0.90
ER: <k> = 3.99, kappa0 = 4.92, predicted f_c (random) = 0.75
Figure 1: Fraction of nodes in the largest component after removing a fraction f of nodes, at random (circles) or by decreasing degree (squares). N = 1000, close to 4. Dashed lines: the Cohen et al. prediction f_c for random failure, computed from the degree sequence of each graph.

The prediction assumes an uncorrelated configuration model with \(N \to \infty\). Under random failure, the curves of both graphs approach zero close to their dashed lines, but with a tail: for this single BA graph the largest component still holds 4.7% of the nodes at \(f = 0.8\) and 0.8% at \(f = 0.9\), against a predicted \(f_c = 0.90\). Such a tail is expected in a finite graph and is not a failure of the formula. The qualitative result is the one of Albert, Jeong and Barabási (Albert et al. 2000): the BA graph survives random failure about as long as the ER graph (the prediction is even higher, 0.90 against 0.75), but under attack it breaks apart after the removal of about 20% of its nodes, against about 40% for the ER graph.

Which feature of the BA graph explains this?

The BA model differs from a configuration model in two ways: its wiring is not uniformly random given the degrees (it has some degree correlations, and its older nodes are connected among themselves), and its degree sequence is heavy-tailed. To separate the two, we keep the degrees of each BA graph and randomise everything else with \(10E\) double-edge swaps, a degree-preserving null model (see The Configuration Model). If the correlations of the BA model mattered, the randomised graph would behave differently from the original.

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


def giant_curve(G, mode, fractions, rng):
    n = G.number_of_nodes()
    A = nx.to_scipy_sparse_array(G, nodelist=range(n), format="csr")
    if mode == "random":
        order = rng.permutation(n)
    else:
        order = np.argsort(-np.array([G.degree(i) for i in range(n)]), kind="stable")
    out = []
    for f in fractions:
        keep = np.ones(n, bool)
        keep[order[: int(f * n)]] = False
        idx = np.where(keep)[0]
        if idx.size == 0:
            out.append(0.0)
            continue
        _, labels = connected_components(A[idx][:, idx], directed=False)
        out.append(np.bincount(labels).max() / n)
    return np.array(out)


fractions = np.linspace(0, 0.95, 20)
rng = np.random.default_rng(0)
curves = {(name, mode): [] for name in ("BA", "BA randomised", "ER") for mode in ("random", "attack")}
for s in range(20):
    G = nx.barabasi_albert_graph(N, 2, seed=s)
    H = G.copy()
    nx.double_edge_swap(H, nswap=10 * G.number_of_edges(), max_tries=10**7, seed=s)
    E = nx.gnm_random_graph(N, G.number_of_edges(), seed=s)
    for name, graph in (("BA", G), ("BA randomised", H), ("ER", E)):
        for mode in ("random", "attack"):
            curves[(name, mode)].append(giant_curve(graph, mode, fractions, rng))

fig, axes = plt.subplots(1, 2, figsize=(9.5, 3.8), sharey=True)
for ax, mode, title in zip(axes, ("random", "attack"), ("random failure", "attack on the highest degrees")):
    for name, style in (("BA", "o-"), ("BA randomised", "s--"), ("ER", "^:")):
        ax.plot(fractions, np.mean(curves[(name, mode)], axis=0), style, ms=4, label=name)
    ax.set_title(title)
    ax.set_xlabel("fraction of removed nodes f")
axes[0].set_ylabel("largest component S")
axes[0].legend()
plt.tight_layout()
plt.show()

for mode in ("random", "attack"):
    ba = np.mean(curves[("BA", mode)], axis=0)
    null = np.mean(curves[("BA randomised", mode)], axis=0)
    er = np.mean(curves[("ER", mode)], axis=0)
    f_half = lambda c: fractions[np.argmax(c < 0.5)]
    f_zero = lambda c: fractions[np.argmax(c < 0.05)]
    print(f"{mode:7s} max |BA - randomised BA| = {np.abs(ba - null).max():.3f};  max |BA - ER| = {np.abs(ba - er).max():.3f};  "
          f"first f with S < 0.05: BA {f_zero(ba):.2f}, randomised {f_zero(null):.2f}, ER {f_zero(er):.2f}")
Figure 2: Largest component S after removing a fraction f of the nodes, for BA graphs (m = 2, N = 1000), the same graphs after degree-preserving randomisation (double-edge swaps) and Erdős-Rényi graphs with the same number of edges. Averages over 20 graphs. Left: random failure. Right: removal by decreasing degree of the intact graph. The BA graph and its randomised version are almost indistinguishable; the ER graph differs under attack.
random  max |BA - randomised BA| = 0.040;  max |BA - ER| = 0.053;  first f with S < 0.05: BA 0.80, randomised 0.80, ER 0.75
attack  max |BA - randomised BA| = 0.061;  max |BA - ER| = 0.672;  first f with S < 0.05: BA 0.20, randomised 0.20, ER 0.40

The measured differences between the BA graphs and their randomised versions are at most 0.04 under random failure and 0.06 under attack, in a quantity that runs from 1 to 0, and both versions fall below \(S = 0.05\) at the same removal fraction (0.80 under random failure and 0.20 under attack). The ER graph, which has the same mean degree but a narrow degree distribution, differs from the BA graph by up to 0.67 under attack. The evidence therefore supports the following reading: the degree sequence alone accounts for the behaviour of the BA graph under both kinds of removal, and the details of its wiring and its degree correlations are at most a small correction at this size (\(N = 1000\), 20 graphs per curve). This test does not show that degree correlations are irrelevant in other networks, and it does not resolve effects smaller than a few per cent.

NoteExercise

Use the formula for \(f_c\) to predict the random-failure threshold of an Erdős-Rényi graph with \(\langle k \rangle = 2\) and with \(\langle k \rangle = 10\).

\(f_c = 1 - 1/\langle k \rangle\) gives \(f_c = 0.5\) for \(\langle k \rangle = 2\) and \(f_c = 0.9\) for \(\langle k \rangle = 10\). A denser random graph survives the removal of a larger fraction of nodes. At \(\langle k \rangle = 1\) the intact graph is already at its percolation threshold.

See also: The Configuration Model, the setting in which the Molloy-Reed criterion holds exactly.

References

Albert, Réka, Hawoong Jeong, and Albert-László Barabási. 2000. “Error and Attack Tolerance of Complex Networks.” Nature 406 (6794): 378–82. https://doi.org/10.1038/35019019.
Callaway, Duncan S., M. E. J. Newman, Steven H. Strogatz, and Duncan J. Watts. 2000. “Network Robustness and Fragility: Percolation on Random Graphs.” Physical Review Letters 85 (25): 5468–71. https://doi.org/10.1103/PhysRevLett.85.5468.
Cohen, Reuven, Keren Erez, Daniel ben-Avraham, and Shlomo Havlin. 2000. “Resilience of the Internet to Random Breakdowns.” Physical Review Letters 85 (21): 4626–28. https://doi.org/10.1103/PhysRevLett.85.4626.
Molloy, Michael, and Bruce Reed. 1995. “A Critical Point for Random Graphs with a Given Degree Sequence.” Random Structures & Algorithms 6 (2–3): 161–80. https://doi.org/10.1002/rsa.3240060204.
Newman, M. E. J. 2003. “The Structure and Function of Complex Networks.” SIAM Review 45 (2): 167–256. https://doi.org/10.1137/S003614450342480.