Build It Cheap, Then Watch It Break
The big question of this module. How much of a network can you destroy before it falls apart — and does it matter whether the damage is random or deliberate?
Moravia, 1926: Every Town Needs Power and There Is No Money
In the aftermath of World War I, the newly formed Czechoslovakia faced massive reconstruction challenges. Cities and towns across Moravia needed electricity, but the young nation had limited resources. Every resource spent on unnecessary infrastructure was a resource not available for hospitals, schools, or economic recovery. Engineers at the West Moravian Power Company faced a critical question: How do you connect every town and village to the electrical grid while using the minimum length of cable?
Otakar Borůvka (1899–1995), the Czech mathematician who gave the first answer.
Photograph via Wikimedia Commons.
The problem reached mathematician Otakar Borůvka through his friend at the power company. Borůvka’s 1926 solution gave us the first systematic approach to what we now call the minimum spanning tree problem: finding the cheapest way to connect all locations in a network.
The Cheapest Network That Still Reaches Everyone
Borůvka’s question is about a weighted network: a network in which every edge carries a number, here the cost of laying that stretch of cable. A minimum spanning tree (MST) of a weighted network is a set of edges that:
- Spans all nodes (connects every location in the network)
- Is a tree (connected with no cycles — no redundant loops)
- Has minimum total weight among all possible spanning trees
A tree on N nodes always has exactly N-1 edges, so every spanning tree buys you the same number of cables. Choosing the minimum one is choosing where to spend, not how much to spend.
Borůvka delivered the first algorithm to solve this problem, Borůvka’s algorithm. It is not the only one. We will cover two others, Kruskal’s algorithm and Prim’s algorithm, which are easier to understand and implement.
Two Ways to Build It, One Answer
Kruskal: Always Take the Cheapest Cable That Adds Something
Kruskal’s algorithm embodies a remarkably simple yet powerful intuition: always choose the cheapest available option, but never create wasteful loops. It sounds like a rule of thumb — a heuristic, a shortcut with no guarantee attached — and yet it provably lands on the globally cheapest tree, every time.
The algorithm works by first sorting every possible connection from cheapest to most expensive, like arranging all the cable segments by cost. Then it examines each connection in order, asking a crucial question: “If I add this cable, will it create a redundant loop?” If the answer is no, the cable joins the growing network. If adding it would create a cycle — meaning the two locations are already connected through some other path — the algorithm skips it as wasteful. This process continues until every location is connected, guaranteeing both minimum cost and complete coverage.
Why is being greedy enough? Do one swap by hand on Figure 1 and the whole argument becomes visible.
The middle panel is a spanning tree. Read its four cables off the left panel and you get its price: 1 + 5 + 2 + 6 = 14. Now cut the 5-cable, the one running across the middle. A tree carries no spare routes, so cutting any one of its cables always leaves exactly two pieces — here the three towns on the left and the two on the right. Ask what the cheapest cable joining those two pieces is: back in the left panel, it is the 3-cable from the bottom-left town to the right-hand one. Put it in. Every town is reachable again, there is still no loop, and the bill is
14 - 5 + 3 = 12,
which is the right-hand panel (1 + 2 + 3 + 6 = 12, the same five towns joined for two less). Any tree you can improve by a swap like that was not minimum to begin with. (The figure below runs the same swap once more, in motion, on a six-town grid.)
Now run the swap the other way, and it becomes Kruskal’s guarantee. Take any group of towns already joined to one another, and let e be the cheapest cable leaving that group — the cable greedy is about to grab. Suppose some minimum tree left the group without it. Add e to that tree: you now have exactly one loop, and a loop that leaves the group has to come back, so it contains a second cable crossing out of the group, priced at least as dear as e. Drop that one instead. What is left is still connected (the loop supplied the detour), still loop-free, and costs no more than the tree you started with. So some minimum tree does contain e. Greedy is not gambling: at every step it takes a cable that some cheapest solution could not have done without.
Prim: Grow Outward From the Power Plant
Prim’s algorithm takes a fundamentally different approach, embodying the intuition of organic growth from a single starting point. Picture an engineer beginning at the central power plant and asking: “What’s the cheapest way to connect one more location to our existing grid?” This local growth strategy builds the network incrementally, always expanding from what’s already been constructed.
The algorithm begins by selecting any location as its starting point, often the power plant in our analogy. From this initial seed, it repeatedly identifies the cheapest connection that would bring a new, unconnected location into the growing network. Unlike Kruskal’s global view, Prim’s algorithm maintains a clear distinction between locations already in the network and those still waiting to be connected. At each step, it finds the minimum-cost bridge between these two groups, gradually expanding the connected region until it encompasses every location.
This local expansion strategy mirrors how many real-world infrastructure projects actually develop. Engineers often start from existing facilities and expand outward, always seeking the most cost-effective way to serve additional areas. Prim’s algorithm formalizes this natural growth process.
The two algorithms find the same tree when all connection costs are different. When several cables cost the same, there can be several minimum spanning trees of equal total cost, and which one you get depends on the algorithm — and, for Prim, on where you started.
Below, both algorithms step through the same six towns — a power plant at A, five towns, and nine surveyed stretches of cable priced 1 to 9. Watch the bill climb under each grid; watch Kruskal refuse the 3-cable because it would close a loop; watch Prim walk past the 5-cable because it cannot yet reach it. They arrive at the same five cables from opposite directions. The last step does the swap from the previous section in motion.
The Cheapest Grid Is the Easiest to Break
A minimum spanning tree connects everyone for the least money. It also has no spare parts. Because a tree has no cycles, every single edge is a bridge: cut any one of the N-1 cables and the grid splits in two. Remove a town in the middle and it splits into as many pieces as that town had cables. There is no second route anywhere, because a second route is exactly what the algorithm was told to avoid.
This is why real power grids carry far more line than a tree would need.
One Node Down: Sometimes Nothing, Sometimes Everything
Not every failure is equal. Some failures are more damaging than others: removing some nodes is catastrophic, while removing others is barely noticed.
Many measures of damage are possible. We will use a purely topological one — how much of the network is still holding together:
\text{Connectivity} = \frac{\text{Size of largest connected component after removal}}{N}
where N is the number of nodes in the original network. Note what the numerator counts: not survivors, but survivors still reachable from one another. A node that lives through the attack but ends up cut off from everyone contributes nothing.
Try it yourself in Twelve towns, twenty cables. It hands you twelve unconnected towns and a budget of twenty cables: click two towns to lay a cable between them — click the same two again to take it back — and spend the budget however you like. Then press Random failure or Targeted attack, and it removes towns one at a time, drawing the connectivity after every removal and printing R underneath. Rebuild puts your wiring back so you can run the other attack on exactly the same network. Wire the same twenty cables two ways, spread evenly and then piled onto two or three towns, and compare the four numbers. The random curves will barely move between the two wirings; the targeted ones will not be close. That contrast is the rest of this module.
The Whole Story in One Curve, and One Number
Removing one node tells you one thing. Keep going — remove a second, a third, all the way down — and record the connectivity after every removal. The result is the robustness profile: connectivity plotted against the fraction of nodes removed.
To compare whole networks with a single number, we take the area under that curve — the R-index:
R = \frac{1}{N} \sum_{k=1}^{N-1} y_k
where y_k is the connectivity measured after k nodes have been removed, and N is the size of the original network. The higher the R-index, the longer the network kept working as it was dismantled.
It is worth knowing the scale before you compute one. The best a network can possibly do is lose exactly one node’s worth of connectivity per removal, which traces a straight line from 1 down to 0; averaging that line gives R \approx 0.5. A network that shatters on the first removal gives R \approx 0. So R = 0.35 is not “35% robust” — it is seven-tenths of the way to the best any network could do.
One profile on its own is only a shape. It turns into an argument the moment you draw two of them. Below are two grids built for exactly the same money — thirty towns, sixty cables, four cables a town on both sides — wired as differently as that budget allows. Let the dice pick which towns fail. Then let somebody pick. Then take the dial and decide for yourself how much of the damage is deliberate.
Two grids, one bill, and the answer to “which one would you rather own” reverses inside the first tenth of that dial. That is the robust-yet-fragile paradox, and the rest of this module is the account of why.
Random Failure or Targeted Attack?
The shape of the profile depends entirely on the order in which nodes are removed — which is what the dial above was turning — and there are two orders worth distinguishing.
Random failure removes nodes with no regard for what they do. This is earthquakes, storms, and equipment wearing out: in a power grid, a generator fails because a bearing seized; on the Internet, a server crashes because a disk died. Nothing chose it.
Targeted attack removes nodes chosen for maximum damage. An adversary who can see the network structure will go after the hubs — the nodes with the most connections — the way you would ground the busiest airports to paralyse air travel. A network can survive random failure beautifully and still fall apart under a targeted attack, and the rest of this module is about why.
Fixed Order or Recomputed Order?
There is a subtlety hiding in “attack the hubs first” that is easy to miss and matters a great deal in practice: when do you decide the order?
- Fixed (simultaneous) attack. Rank all nodes by degree once, on the original network, then delete them in that order.
- Adaptive (sequential) attack. Delete the current highest-degree node, then recompute every degree on what remains, then delete the new highest-degree node, and so on.
These differ because removing a hub changes its neighbors’ degrees. A node that looked unimportant initially can become the most connected node left once the hubs around it are gone; a fixed ranking never notices. Adaptive attacks are consistently more destructive than fixed ones for the same number of removals, so an adaptive strategy gives the more honest estimate of worst-case fragility.
The same choice applies to any attack criterion, not just degree — you can attack by betweenness (Module 6) and recompute it after every removal. That is more damaging still, and far more expensive to compute, which is the usual trade-off: better targeting costs the attacker more information and more computation.
Attack Is Percolation Run Backwards
To understand these curves mathematically, we borrow a piece of physics. Percolation theory was invented to describe how a liquid seeps through a porous rock, and it asks: as more and more of the material is opened up at random, when does a path suddenly appear all the way through?
That is our question with the sign flipped:
- Percolation asks “starting from isolation, how much must we connect before one giant component appears?” — connectivity increasing from p = 0 to p = 1.
- Robustness asks “starting from a working network, how much must we remove before the giant component disappears?” — connectivity decreasing from p = 1 to p = 0.
These are the same process traversed in opposite directions along the same parameter, so every result about one is a result about the other. A giant component here means a single connected component that holds a finite fraction of all the nodes — the difference between a grid and a scatter of neighbourhood islands.
Nothing, Nothing, Then Everything at Once
Percolation is easiest to see on a square grid, so picture one for a moment: a large sheet of squares, each of which independently becomes a puddle with probability p. Neighbouring puddles merge. At small p you get isolated ponds. Raise p a little and you get slightly bigger ponds. Nothing, nothing, nothing — and then, over a very narrow range of p, the ponds join up and one puddle spans the entire sheet. That sudden change is a phase transition, and the value of p where it happens is the critical probability p_c.
Two things about that sentence are worth pinning down.
First, which squares filled first does not matter, only how many. Fill them in any order you like and the picture at a given p is statistically the same, because each square was chosen with no regard for its surroundings. This is exactly why random failure is easy to analyse and targeted attack is not: an attacker chooses which, and then order is the whole story.
Second, p_c belongs to the object you are studying. For this particular square grid it sits at p_c \approx 0.593; a triangular grid has a different one, and a network with hubs has a different one again. The two sections below work out the equivalent threshold for networks, and the answer will not look anything like 0.593 — do not carry that number across.
One Number Decides: The Molloy-Reed Criterion
For networks, the question “is there a giant component?” has a startlingly compact answer. Let \langle k \rangle be the average degree of the network and \langle k^2 \rangle the average of the squared degrees, and form their ratio
\kappa = \frac{\langle k^2 \rangle}{\langle k \rangle}.
The Molloy-Reed criterion (Molloy & Reed 1995) says that a randomly wired network has a giant component exactly when
\kappa > 2 .
Writing \langle k^2 \rangle = \text{Var}(k) + \langle k \rangle^2 turns the ratio into
\kappa = \langle k \rangle + \frac{\text{Var}(k)}{\langle k \rangle},
which is why \kappa is read as a measure of degree heterogeneity: it is the average degree, plus a term that grows with how unequal the degrees are.
Where does a threshold of exactly 2 come from? Follow a cable out of a town and arrive somewhere. The average degree of the town you land on is not \langle k \rangle but \kappa, because a town with many cables is many times more likely to be at the far end of the one you followed. One of its cables is the one you arrived on, so on average it offers \kappa - 1 new ways onward. If \kappa - 1 < 1 the exploration shrinks at every step and dies; if \kappa - 1 > 1 it grows at every step and swallows a finite fraction of the network. The threshold is \kappa - 1 = 1. The appendix does this argument properly.
The same idea gives the critical fraction f_c: the fraction of nodes that must be removed at random before the giant component dies. Removing a fraction f leaves each onward cable in place with probability 1-f, so the branching factor falls to (1-f)(\kappa - 1), and the network dies when that reaches 1:
f_c = 1 - \frac{1}{\kappa - 1}.
A worked case. Take a randomly wired network in which towns have on average 4 cables, with the degrees scattered the way random wiring scatters them (a Poisson distribution, whose variance equals its mean, so \text{Var}(k) = 4 too). Then \kappa = 4 + 4/4 = 5, and
f_c = 1 - \frac{1}{5 - 1} = 0.75 .
Three-quarters of the towns have to go before the grid stops being a grid. Denser wiring pushes f_c up — for Poisson degrees the formula collapses to f_c = 1 - 1/\langle k \rangle — but it never reaches 1: a homogeneous network always falls apart at some definite fraction.
Hubs Inflate the One Number That Matters
Now hold the budget fixed and change only how the cables are distributed. Here are three ways to wire 100 towns with 200 cables. All three have the same average degree, \langle k \rangle = 4; they differ only in the spread.
| Wiring of 100 towns, 200 cables | degrees | \kappa | f_c (random failure) |
|---|---|---|---|
| every town identical | all 4 | 4 | 0.67 |
| random wiring (Poisson) | mean 4, variance 4 | 5 | 0.75 |
| ten hubs | 90 towns with 2, 10 hubs with 22 | 13 | 0.92 |
Read the last row off the definition: \langle k^2 \rangle = (90 \times 2^2 + 10 \times 22^2)/100 = 52, so \kappa = 52/4 = 13 and f_c = 1 - 1/12 \approx 0.92. Same money, same number of cables, and the hub-heavy grid survives random failure far longer — you have to knock out 92 towns out of 100 instead of 67. (These thresholds are statements about large randomly wired networks; on exactly 100 towns read them as the trend, not as a guarantee.)
This is not a quirk of the numbers chosen. \kappa grows with the variance of the degrees, and real networks — airline routes, the Internet, who-cites-whom — have enormous degree variance: a handful of nodes with hundreds of connections while the typical node has two or three. Module 4 measures that spread properly. For networks with that much spread, \kappa can be so large that f_c sits within a whisker of 1: essentially every node has to fail before the network stops working. Random breakdown, in such a network, is almost harmless.
The appendix turns “enormous degree variance” into a formula and works out f_c exactly.
Robust Yet Fragile: The Hubs Are the Achilles’ Heel
The hub-heavy grid in the table above shrugs off random failure. Now let an adversary choose.
Delete the ten hubs. That is 10 towns out of 100 — one node in ten. Those ten hubs account for 10 \times 22 = 220 of the 400 cable-ends in the network. Even in the worst case for the attacker, where all ten hubs happen to be cabled to one another (at most \binom{10}{2} = 45 cables), deleting them still takes at least 220 - 45 = 175 of the 200 cables with them. Ninety towns are left holding no more than 25 cables between them. The grid is dust.
Compare the same attack on the row above it, where every town has exactly 4 cables. Deleting any 10 towns removes at most 40 of the 200 cables. Nothing dramatic happens; you have to keep going.
That is the robust-yet-fragile paradox, and it is the same structural fact read twice. The hubs make \langle k^2 \rangle huge, which is what protects the network against a blind attacker who is unlikely to hit one — and they concentrate the connectivity into a handful of nodes, which is what dooms it against an attacker who can see. Robustness is not a property of a network; it is a property of a network and a threat.
The numbers get more extreme, not less, as networks get bigger and more hub-heavy. The appendix works out the attack threshold for the heavy-tailed degree distributions that Module 4 will measure on real data (Cohen, Erez, ben-Avraham & Havlin 2001). For one standard case worked there in full, the answer is f_c \approx 0.056: delete the best-connected one node in eighteen and the rest is rubble.
This is why the operators of real infrastructure spend their protection budget so unevenly — extra transformers and armed fences at the major substations, hot-standby routers at the large Internet exchange points, spare landing slots at the big hub airports — while a rural distribution line gets none of it. It is also why the same reasoning turns up in epidemiology: if you can only vaccinate a few people, vaccinate the hubs. Module 4 shows you how to find them without ever seeing the whole network.
What This Buys You: Redundancy Costs Money, Hubs Cost Risk
Borůvka’s tree is one end of a spectrum: minimum cost, zero slack. What the rest of this module adds is a way to price the other end.
- Redundancy is the thing you are actually buying. Every cable beyond the N-1 in the spanning tree exists to give some pair of towns a second route. Adding cables raises \langle k \rangle, which raises \kappa, which raises f_c — you can now say how much robustness a given cable bought.
- Concentrating those cables is efficient and dangerous. Hub-heavy wiring buys the highest f_c per cable against random failure and the lowest threshold against a deliberate attacker. Which one you want depends on what you expect to face.
- If you must have hubs, protect them explicitly. The paradox says the vulnerability is localized in a small number of identifiable nodes. That is bad news for an unprepared operator and good news for a prepared one: the list of things to defend is short.
What You Can Now Do
- Build the cheapest network that connects everything, by hand, with Kruskal’s or Prim’s algorithm — and say why greedy is enough.
- Measure how much of a network survives an attack, draw its robustness profile, and reduce that profile to a single R-index.
- Compute \kappa from a degree sequence and predict the critical fraction f_c before running a single simulation.
- Say precisely why a hub-heavy network is simultaneously the most robust and the most fragile network on the table.
Next, in this order. First the pen-and-paper design exercise: nine stations, a table of cable costs, and an attacker who deletes one of them — you build the cheapest grid, break it, find the station the attacker will pick, and buy the resilience back one cable at a time. Do it with your own hands before you touch code; the notebook computes in a line what the worksheet asks you to discover, and discovering it is the point. Then run the attacks yourself on a real network and watch the same thing happen at a scale no worksheet can reach.
References
Borůvka, O. (1926). O jistém problému minimálním [About a certain minimal problem]. Práce Moravské Přírodovědecké Společnosti, 3, 37-58. [Original work on minimum spanning trees]
Molloy, M., & Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2-3), 161-180. [The \kappa > 2 criterion]
Albert, R., Jeong, H., & Barabási, A. L. (2000). Error and attack tolerance of complex networks. Nature, 406(6794), 378-382. [The robust-yet-fragile paradox, measured]
Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2000). Resilience of the Internet to random breakdowns. Physical Review Letters, 85(21), 4626-4629. [f_c for random failure]
Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2001). Breakdown of the Internet under intentional attack. Physical Review Letters, 86(16), 3682-3685. [f_c for targeted attack; the equation solved in the appendix]
Callaway, D. S., Newman, M. E., Strogatz, S. H., & Watts, D. J. (2000). Network robustness and fragility: Percolation on random graphs. Physical Review Letters, 85(25), 5468-5471. [Percolation treatment of both cases]
Schneider, C. M., Moreira, A. A., Andrade, J. S., Havlin, S., & Herrmann, H. J. (2011). Mitigation of malicious attacks on networks. PNAS, 108(10), 3838-3841. [The R-index]
Cohen, R., & Havlin, S. (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press.
Newman, M. E. J. (2018). Networks (2nd ed.). Oxford University Press. [Chapter 11 covers percolation and robustness]