Strong against accident, weak against attack
On Friday morning, 21 October 2016, a great many people on the US East Coast found that Twitter, Netflix, Reddit, Spotify, GitHub, PayPal and Airbnb would not load. The sites themselves were running. What had been knocked over was a company most of their users had never heard of: Dyn, of Manchester, New Hampshire, which ran part of the Internet’s domain name system, the directory that turns a name like “example.com” into the numeric address a computer needs. Starting at about 7:10 a.m. Eastern, its servers were swamped with junk requests, in three waves over the day. Dyn said that up to 100,000 infected devices had taken part, many of them ordinary connected devices, such as home cameras, that had been taken over by a program called Mirai. (The people who wrote Mirai pleaded guilty in 2017 to related charges, but no public source has charged them with this particular attack, and we do not name anyone for it.)
Dyn was a hub: a node that a very large number of others depend on. When it was hit, many sites went dark at once. This is the central fact about networks with hubs, and it was first set out in a 2000 paper, “Error and attack tolerance of complex networks.” The authors built two kinds of model network, each with 10,000 nodes and 20,000 links. One was random, with every node close to the average; the other was scale-free, with a few hubs. Then they removed nodes in two ways. In the first, nodes failed at random, as when machines break down for ordinary reasons. In the second, an attacker removed the best-connected nodes first.
The results were opposite. When up to 5 percent of the nodes failed at random, the typical distance across the scale-free network did not change at all: the nodes that fail are mostly small ones, and there are so many of them that a hub is rarely hit. In the random network the same removals lengthened the distances steadily. But when the same 5 percent were removed from the top of the list, the typical distance across the scale-free network doubled, and when about 18 percent had been taken from the top the network fell into pieces. The random network needed about 28 percent to shatter, however the nodes were chosen. The authors tested real maps too: for the Internet’s map of 6,209 autonomous systems, random removal of 2.5 percent of the nodes left the typical distance unchanged, and removing the most connected 2.5 percent made it more than triple. The paper called these networks “extremely vulnerable to attacks.” The common phrase for the pair is robust yet fragile, the Achilles’ heel of a scale-free network: it shrugs off accidents and may be brought down by an informed enemy.
Random failures or an attack?
Two networks with the same 200 nodes and 400 links: one scale-free, one random. Remove nodes at random, or hubs first, and compare how well each holds together.
Blue nodes are in the largest connected group, red ones are cut off, and faint circles are removed. At this small size, the scale-free network does not keep more of its nodes connected under random failure than the random network does; what it keeps is short distances. The famous “random failures can’t break it” result describes very large networks with very heavy tails.
A related mathematical result, by a second team in the same year, makes the same point as a statement about size: in an idealized scale-free network with an exponent below 3, no giant cluster ever disappears under random failure, and for the Internet’s estimated exponent of about 2.5 one would need to destroy more than 99 percent of the nodes. That is where the claim that you could remove “95 percent of the nodes” and the rest would still hold together comes from. Read it carefully. It says that a connected core survives in a mathematical model. It does not say that the Internet would still work, because the remaining machines would be starved of traffic and capacity.
Failure can also travel. Lesson 1 showed how a failed station can pass its load to its neighbors and bring them down. A 2002 study by Adilson Motter and Ying-Cheng Lai found that in networks where some nodes carry much more load than others, knocking out a single heavily loaded node can set off a cascade that takes down a large part of the network (in their 5,000-node scale-free example, more than 60 percent of the nodes at one setting of spare capacity). Hubs are the nodes that carry the load. But the 2003 blackout did not begin at a hub. It began with the failure of a local alarm system and some trees in a small part of the grid. Cascades, too, can start almost anywhere, and hubs are what make the damage large.
Another view
The famous Internet result has been challenged. Walter Willinger, David Alderson, and John Doyle argued in 2009 that the early maps of the Internet’s routers, built from a tool called traceroute, produced misleading hubs. Traceroute can mistake an opaque cloud of switches for a single router with many links, and an analysis by Dimitris Achlioptas and colleagues showed that traceroute sampling produces power-law-looking degrees even from networks that do not have them. In the real router network, they argued, the routers with many links tend to sit at the edge, serving many customers, while the core consists of a few fast links between routers with few connections. Removing an edge router with many links harms its customers but does little to the rest. So whether the “attack on the hubs” scenario fits the Internet’s physical network is disputed. It fits better where hubs are real: a big DNS provider, a cloud service, an airport, a supplier of a single critical part. Dyn was that kind of hub, and Dyn’s customers were the ones who felt it.
Why is a hub-dominated network robust against random failures but fragile against attacks?
Why germs love hubs
The second thing hubs change is how things spread. The standard mathematics of epidemics, developed in the early twentieth century, uses two numbers: how easily an infected person passes on the disease, and how quickly people recover. If the first is too small compared with the second, the disease dies out on its own. Above a certain threshold, it takes off and some fraction of the population is infected. The classical theory assumes that everyone mixes with everyone else at random.
In 2001 Romualdo Pastor-Satorras and Alessandro Vespignani asked what happens if people are connected by a scale-free network. In their model of a disease from which people recover but can catch again, in an idealized infinite network with an exponent of 3 or below, the threshold disappears: however weakly contagious the disease, it can persist. The reason is the hubs. A disease soon reaches a hub, because a hub is in touch with so many people, and the hub then passes it on to many more. In a network of finite size the threshold does not vanish entirely but it can be very low, and it gets lower as the largest hub gets bigger. A formula by Mark Newman (2002) gives the threshold for a disease that people catch only once, expressed as the chance T that a sick person passes it to a given contact, as ⟨k⟩ divided by (⟨k²⟩ minus ⟨k⟩), where ⟨k⟩ is the average number of links and ⟨k²⟩ the average of the square. In a random network, ⟨k²⟩ is not much larger than ⟨k⟩ squared. In a network with hubs it is much larger, so the threshold is much lower. Try it.
An epidemic on two networks
The same 1,000 people and 2,000 links, arranged two ways. Raise the contagiousness and watch when each network starts to have epidemics.
Each point averages 300 simulated outbreaks that start with one random person. An outbreak counts as an epidemic if it reaches more than 5 percent of the people. These are model networks, not maps of real contacts.
Real contacts are lumpy. A 1996 Swedish survey of 2,810 people found that the number of sexual partners people reported in the previous year had a long tail consistent with a power law (an exponent of about 2.4), and the authors drew the implication for diseases that spread that way. Evidence on how contagious diseases spread also points to hubs of a different kind: superspreaders. A 2005 study of outbreaks, including SARS in Singapore in 2003, found that most infected people passed the disease to almost no one, while a few passed it to many. For COVID-19, a 2020 analysis estimated that about 10 percent of cases were responsible for about 80 percent of transmission. The older “20/80 rule,” that 20 percent of cases cause 80 percent of transmission, comes from studies of sexually transmitted and vector-borne diseases; for diseases that pass directly between people, the 2005 authors found that no single rule holds. What the evidence supports is the general point: when a few people or places account for a large share of transmission, finding them matters more than treating everyone alike.
Your friends have more friends than you
This leads to a mathematical fact that surprises almost everyone. On average, your friends have more friends than you do. The sociologist Scott Feld described it in 1991 and called it the friendship paradox. The reason is not that you are unlucky. When you ask “how many friends do my friends have?”, a person with 100 friends gets counted 100 times, once on each friend’s list, while a person with 2 friends is counted twice. Popular people are over-represented in everyone’s friend lists. In symbols, the average number of friends among your friends is ⟨k²⟩ divided by ⟨k⟩, which is always at least as large as ⟨k⟩ and is much larger when there are hubs.
Is it true of you?
A network of 300 people with a few hubs. Pick someone at random, then check everyone.
The effect holds in any network where the number of friends varies; it is strongest when there are hubs.
The fact can be put to use. In the autumn of 2009, during the H1N1 flu pandemic, Nicholas Christakis and James Fowler followed 744 Harvard students: 319 chosen at random, plus 425 friends named by them. The flu reached the named friends about 14 days earlier on average (13.9 days, with a confidence interval of 9.9 to 16.6) than it reached the randomly chosen group, because the friends, being better connected, were more exposed. Friends could serve as early-warning sensors. A later study found that friends’ groups on Twitter detected the rise of hashtags about a week earlier than a random group, although that was about information, not disease.
The same idea suggests a way to protect a population. If hubs are the key, immunize the hubs. But who they are is rarely known, and a map of everyone’s contacts does not exist. In 2003 Reuven Cohen, Shlomo Havlin and Daniel ben-Avraham proposed a trick that needs no map: pick a random person, and then immunize one of that person’s acquaintances. By the friendship paradox the acquaintance is likely to be better connected than a random person. In their models of scale-free networks, this greatly lowered the proportion of the population that had to be immunized. It remains a theoretical strategy, and real vaccination programs depend on logistics, supply and consent as much as on the structure of the network.
Another view
The “no threshold” result is easily overstated. It is a theorem about infinitely large networks with a precisely scale-free distribution. In a finite network the largest hub is limited, so the threshold is small but not zero, and the more the distribution is cut off at its tail (people cannot have infinitely many contacts), the more it comes back. Proofs by Marián Boguñá and colleagues showed that some other features, such as a tendency of hubs to link to hubs, do not bring the threshold back. And the result is for one family of models: for diseases that people catch only once, the threshold vanishes only when the exponent is 3 or below. (For diseases that can be caught again, a 2009 proof by Shirshendu Chatterjee and Rick Durrett found a zero threshold even for exponents above 3, but only in the limit of an infinitely large network, which no real network is.) Real epidemics are shaped by many things the model leaves out, including how long people are infectious, where they go, and what they do once they know. The network picture shows why heterogeneity matters. It does not replace the epidemiologists’ own models.
How scale-free is the world?
All of this rests on one claim: that many real networks are scale-free. It deserves a hard look, and science has given it one. Fitting a power law is delicate. A straight-looking stretch on log-log axes can come from other distributions, such as the log-normal, which produces a similar bend. In 2009 Aaron Clauset, Cosma Shalizi and Mark Newman published a statistical method for testing power laws and applied it to 24 data sets that had been reported as power laws. Seventeen were consistent with a power law. Seven were firmly ruled out, including the Web’s links and the metabolic network, while others, such as protein interactions, were consistent with it. They also found that telling a power law from a log-normal is “extremely difficult.” An earlier study (Amaral and colleagues, 2000) had found that real networks fall into at least three classes: some are scale-free, but others, such as the electric grid of southern California, have an exponential distribution, and the film-actor network is a power law cut off by an exponential tail.
The largest test came in 2019. Anna Broido and Aaron Clauset collected 928 network data sets from many fields (social, biological, technological, transportation, and information networks) and applied a graded test. Only 4 percent of the networks met their strictest criteria, and only about 10 percent met the next, “strong” test. Nearly half (49 percent) were not scale-free by even the weakest test. The log-normal fitted the data better than the power law in 48 percent of the comparisons, against 12 percent where the power law won. Social networks were “at best weakly scale-free”; none passed the strong test. A handful of technological and biological networks came closest.
Another view
Both sides have a case. Critics of the strict test (Petter Holme, Ivan Voitalov and colleagues, and others) pointed out that real networks are finite and noisy, that “scale-free” was always meant as a large-size limit, and that other estimators find scale-free networks to be “definitely not as rare” as the strict test implies. One reanalysis found that about 64 percent of the networks that had enough data to be tested were classified as power-law, and another, using finite-size scaling on about 200 networks, found that many protein, computer, hyperlink, and information networks fit while social and transport networks deviate. The scientist behind the original model objected publicly, in a blog post, on conceptual and technical grounds. What no one disputes is that real degree distributions are usually heavy-tailed: far broader than a random network’s, with hubs that matter. What is disputed is whether the right description is an exact power law, how often it fits, and which simple growth rule produces it.
How should you hold these results together? Think of the scale-free picture as a useful first approximation, which is how many scientific models begin. The central, robust ideas are that real networks have far larger hubs than chance would give, that growth with a bias toward the already-connected is one way to get them, that hubs make a network robust to accidents and fragile to attack, and that they speed up spreading. The more exact claims, a pure power law with an exponent between 2 and 3, a universal mechanism, are hypotheses that depend on the network and on how carefully it was measured. That is what a healthy science looks like: a claim made in 1999 was tested in 2009 and 2019, and what survived is clearer than what came in.
What does the evidence say about the claim that real networks are scale-free?
Closer to home
If you have ever felt that your friends are more popular than you, the friendship paradox says you are in the majority: for most people in a network with hubs, their friends really do have more friends than they do. It is no verdict on you. It is also why the news and the jokes that reach you tend to come from the people with the biggest circles. Social media magnifies this, since it shows you the most-followed accounts of the people you follow. And if you have ever been the one connecting two circles, the friend who knows everyone at the restaurant and everyone at the temple, you were a hub for a day, and the research says that such people matter both for good news and for bad.
What to keep
- Hub-dominated networks are robust against random failure (most nodes are small) and fragile against attack (a few hubs hold everything together). A hub such as the Dyn name servers in 2016 is a single point of failure for everyone who depends on it.
- Hubs lower the epidemic threshold, and a few superspreaders can drive most of the spread. In idealized infinite networks the threshold vanishes; in real finite ones it is small but positive.
- Your friends have more friends than you do, because popular people appear on many lists. This can be used: friends are early-warning sensors, and immunizing a random person’s acquaintance beats immunizing at random.
- The claim that real networks are scale-free has been tested hard. Heavy tails and hubs are common; pure power laws fit a minority; the size of that minority is still argued over.
Think it over
Your notes are saved in this browser.
Sources and further reading
- Brian Krebs, “DDoS on Dyn impacts Twitter, Spotify, Reddit” (KrebsOnSecurity, 21 October 2016); Dyn’s statement of 26 October 2016 as reported by The Hacker News and others; “2016 Dyn cyberattack” (Wikipedia) for the three waves. Public records do not establish who carried out the attack.
- Réka Albert, Hawoong Jeong, and Albert-László Barabási, “Error and attack tolerance of complex networks,” Nature 406 (2000); Reuven Cohen, Keren Erez, Daniel ben-Avraham, and Shlomo Havlin, “Resilience of the Internet to random breakdowns,” Physical Review Letters 85 (2000), and “Breakdown of the Internet under intentional attack,” Physical Review Letters 86 (2001).
- Adilson Motter and Ying-Cheng Lai, “Cascade-based attacks on complex networks,” Physical Review E 66 (2002); US–Canada Power System Outage Task Force, Final Report on the August 14, 2003 Blackout (2004).
- Romualdo Pastor-Satorras and Alessandro Vespignani, “Epidemic spreading in scale-free networks,” Physical Review Letters 86 (2001); Mark Newman, “Spread of epidemic disease on networks,” Physical Review E 66 (2002); Marián Boguñá, Romualdo Pastor-Satorras, and Alessandro Vespignani, Physical Review Letters 90 (2003); Claudio Castellano and Romualdo Pastor-Satorras, Physical Review Letters 105 (2010); Shirshendu Chatterjee and Rick Durrett, “Contact processes on random graphs with power law degree distributions have critical value 0,” Annals of Probability 37 (2009).
- Fredrik Liljeros and others, “The web of human sexual contacts,” Nature 411 (2001).
- James Lloyd-Smith, Sebastian Schreiber, P. Ekkehard Kopp, and Wayne Getz, “Superspreading and the effect of individual variation on disease emergence,” Nature 438 (2005); Akira Endo and others, “Estimating the overdispersion in COVID-19 transmission using outbreak sizes outside China,” Wellcome Open Research 5 (2020).
- Scott Feld, “Why your friends have more friends than you do,” American Journal of Sociology 96 (1991); Nicholas Christakis and James Fowler, “Social network sensors for early detection of contagious outbreaks,” PLoS ONE 5 (2010); Manuel Garcia-Herranz and others, PLoS ONE 9 (2014); Reuven Cohen, Shlomo Havlin, and Daniel ben-Avraham, “Efficient immunization strategies for computer networks and populations,” Physical Review Letters 91 (2003).
- Aaron Clauset, Cosma Shalizi, and Mark Newman, “Power-law distributions in empirical data,” SIAM Review 51 (2009); Luís Amaral, Antonio Scala, Marc Barthélemy, and H. Eugene Stanley, “Classes of small-world networks,” Proceedings of the National Academy of Sciences 97 (2000).
- Anna Broido and Aaron Clauset, “Scale-free networks are rare,” Nature Communications 10 (2019); Petter Holme, “Rare and everywhere: perspectives on scale-free networks,” Nature Communications 10 (2019); Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, and Dmitri Krioukov, “Scale-free networks well done,” Physical Review Research 1 (2019); Ivan Artico and others, Proceedings of the Royal Society A 476 (2020); Manuel Serafino and others, Proceedings of the National Academy of Sciences 118 (2021).
- Walter Willinger, David Alderson, and John Doyle, “Mathematics and the Internet: a source of enormous confusion and great potential,” Notices of the American Mathematical Society 56 (2009); Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore, “On the bias of traceroute sampling,” Journal of the ACM 56 (2009).