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
Module 5: Complex Networks
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).
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\).
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.} \]
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).
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
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.
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}")
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.
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.