Skip to main content

The Motter-Lai Model

Module 5: Complex Networks

NoteReading
  • Compulsory: Motter and Lai (2002).
  • What the paper did and found: Motter and Lai define the load of a node as the number of shortest paths through it and the capacity as \(C_j = (1+\alpha)L_j(0)\). They triggered cascades by removing one node, chosen at random or among those with the highest load or degree, on networks with a power-law degree distribution (\(\gamma = 3\), \(5000 \le N \le 5100\), mean degree about 2 in the largest component) and on a homogeneous network with \(N = 5000\) and exactly 3 links per node. For the scale-free networks the largest component stays close to its original size after a random trigger, while a load-based attack with \(\alpha = 0.2\) affects more than 60% of the nodes (more than 3000 of 5000). The homogeneous network showed no cascade for either type of trigger at \(\alpha\) as small as 0.05. For the Internet at the autonomous-system level, an attack on one node disconnected more than 20% of the nodes for \(\alpha \le 0.4\). For the western US power grid (\(N = 4941\), mean degree 2.67), whose degree distribution is close to exponential but whose load distribution is more skewed than that of random networks with the same degrees, a load-based attack on one node reduced the largest component to less than half of its size even at \(\alpha = 1\), while random or degree-based removal triggered no global cascade.

Motter and Lai proposed a minimal model of cascades of overload failures on networks (Motter and Lai 2002). The model has one parameter and one rule. This page states the model. The next page implements it.

Load

Something travels between every pair of nodes along shortest paths: data packets, goods, or, in a crude picture, power. The load \(L_i\) of node \(i\) is the number of shortest paths between pairs of other nodes that pass through \(i\) (Motter and Lai 2002). When several shortest paths join the same pair, each one counts with equal weight. This is the betweenness centrality of Network Concepts, without normalization:

\[ L_i = \sum_{s \neq i \neq t} \frac{\sigma_{st}(i)}{\sigma_{st}}. \]

Capacity

Operators build some spare capacity into each node. Motter and Lai assume that the capacity is proportional to the initial load \(L_i(0)\) of the intact network (Motter and Lai 2002):

\[ C_i = (1 + \alpha)\, L_i(0), \qquad \alpha \ge 0. \]

The tolerance parameter \(\alpha\) is the same for every node. With \(\alpha = 0\) the network runs at full capacity; with large \(\alpha\) every node has plenty of margin.

Cascade iteration

  1. Start from the intact network and compute \(L_i(0)\) and \(C_i\) for all nodes.
  2. Remove a trigger node.
  3. Recompute the loads \(L_i\) on the remaining network. The shortest paths change, so the load redistributes.
  4. Remove every node with \(L_i > C_i\).
  5. Repeat steps 3 and 4 until no node is overloaded.

The damage is measured by the relative size of the largest connected component after the cascade (Motter and Lai 2002):

\[ G = \frac{N'}{N}, \]

where \(N\) is the number of nodes of the intact network and \(N'\) the size of its largest component at the end. \(G \approx 1\) means the network survived; \(G \ll 1\) means it broke apart.

Key results

Motter and Lai compared triggers chosen at random with triggers chosen as the node with the largest load, on model networks and on real networks including a power grid and the Internet (Motter and Lai 2002). They found that:

  • a network with a heterogeneous load distribution, such as a scale-free network, survives a random trigger with little damage but can collapse after the removal of a single high-load node;
  • a network with a homogeneous load distribution is much less sensitive to the choice of the trigger. Homogeneity of the degrees is not enough: the power grid of the paper has an almost exponential degree distribution and is nevertheless vulnerable to load-based attacks, because its loads are heterogeneous;
  • \(G\) increases with \(\alpha\), so spare capacity limits the cascade.

The first result parallels the random-failure versus attack asymmetry of Robustness and Percolation, but here one removed node is enough, because the load it carried moves to other nodes.

A small example

Figure 1 runs one cascade on a Barabási-Albert graph with 40 nodes. The trigger is the node with the largest load and \(\alpha = 0.5\).

Figure 1: One Motter-Lai cascade on a Barabási-Albert graph (N = 40, m = 2, alpha = 0.5). Black: trigger. Red: nodes that fail by overload in the first step. Orange: nodes that fail in the second step. Grey: survivors.
failed per step: [1, 9, 2], G = 0.53

Node size is proportional to the initial load. Most nodes have a small load, and a few hubs carry most shortest paths. Notice that many of the failed nodes had a small initial load: a small load means a small capacity, so a modest increase after the redistribution is enough to overload them.

NoteExercise

In a star graph with \(N\) nodes, what is the load of the centre and of a leaf? What happens to \(G\) if the centre fails? Does \(\alpha\) matter?

Every pair of leaves has exactly one shortest path, through the centre, so the centre has load \(\binom{N-1}{2}\) and each leaf has load 0. If the centre fails, no edges remain and \(G = 1/N\). The value of \(\alpha\) does not matter: the network breaks apart through the removal itself, with no overload step.

References

Motter, Adilson E., and Ying-Cheng Lai. 2002. “Cascade-Based Attacks on Complex Networks.” Physical Review E 66 (6): 065102. https://doi.org/10.1103/PhysRevE.66.065102.