Networks everywhere

A tree in Ohio

On the afternoon of Thursday 14 August 2003, an electric utility in northern Ohio had a bad day. A generating unit shut down around lunchtime. At about 2:14 p.m. the computer system that was supposed to alert the control room stalled, and nobody noticed. Then, between 3:05 and 3:42 p.m., three high-voltage lines tripped one after another when they touched trees that had been allowed to grow too close. (The official investigation was careful on this point: the lines were not overloaded, and they had not sagged beyond their ratings. The trees had simply been left alone.) Those failures were local, one company’s problem in one corner of one state.

At 4:05 p.m. another line tripped, and the problem stopped being local. Over the next few minutes the failures ran across the whole region. By 4:13 p.m., more than 500 generating units at 265 power plants had shut down, and about 50 million people in eight US states and the Canadian province of Ontario had no electricity. Some had power back within hours. Parts of the United States waited up to four days, and parts of Ontario had rolling blackouts for more than a week.

No single machine in that story was remarkable. What failed was the way the machines were connected. A power grid is a network: stations are the dots and transmission lines are the links. Connection is the whole point of a grid, because neighbors can share power and so each one needs fewer spare plants of its own. But the same links let trouble travel. When one line trips, the electricity it carried must flow somewhere else, and the lines that take the extra load may overload and trip in their turn. Engineers call this a cascading failure. The system as a whole did something (went dark) that none of its parts had chosen to do.

This course is about that kind of fact. The earlier courses in this series asked how complex systems behave; this one asks where the connections are and what they do. Try it on a toy grid.

Networks also fail in a stranger way when they depend on each other. A few weeks after the Ohio blackout, on 28 September 2003, Italy lost power. In 2010 a team led by Sergey Buldyrev published a model, motivated by that event, in which power stations need communication nodes to be controlled and the communication nodes need power. In their model, a small failure in one network can topple both, and interdependent networks turn out to be more fragile than either one alone. That is a theoretical result, a warning about a design, not a measurement of what happened in Italy.

Dots and lines

The first person to see that a map could be reduced to dots and lines was the Swiss mathematician Leonhard Euler. The city of Königsberg (today Kaliningrad, in Russia) stood on a river with two islands and seven bridges, and the townspeople asked whether one could walk a route that crossed every bridge exactly once. Euler presented his answer to the St. Petersburg Academy on 26 August 1735 (it was published in 1741). He noticed that the distances and shapes did not matter at all. Only which land is joined to which. Treat each piece of land as a dot and each bridge as a line, and a walk that uses every line once can exist only if no more than two of the dots have an odd number of lines. In Königsberg all four have an odd number (five, three, three and three), so the answer is no. Euler had invented the idea of a network, although the word graph for such a diagram was only introduced by the mathematician James Joseph Sylvester in 1878.

That act of abstraction is the whole power of network science. Once you forget what the dots and lines are and keep only who is connected to whom, very different systems can be compared. Some examples that scientists have mapped:

• A nervous system. In 1986 John White, Sydney Brenner and colleagues published the complete wiring diagram of the roundworm Caenorhabditis elegans: 302 neurons joined by about 5,000 chemical synapses, 600 gap junctions, and 2,000 junctions with muscle. It was the first nervous system of any animal to be mapped completely.
• A cell. In 2000 a team of biologists and physicists compared the chemical-reaction networks of 43 organisms from all three domains of life. In 2001 the same group mapped 1,870 proteins in yeast, joined by 2,240 interactions, in which one protein binds another.
• The Web. The nodes are pages and the links are hyperlinks. In early 1999 the Web held about 800 million pages, and a 1999 study estimated that two randomly chosen pages were on average about 19 clicks apart.
• Money. Banks lend to one another. When Lehman Brothers filed for bankruptcy on 15 September 2008, the losses traveled along those links. Later studies (Andrew Haldane and Robert May in 2011; Daron Acemoglu and colleagues in 2015) found that dense links can help a banking system absorb a small shock and hurt it when the shock is large: connection is a safety net up to a point, and a conveyor belt for panic after it.
• The universe. Galaxies lie in clusters, sheets, and long filaments around huge voids, a pattern astronomers call the cosmic web. In 2016 a team that included astronomers and network scientists showed that a network built from galaxy positions has the same properties as one built from a simulated universe.

In each case a choice is hiding. A “link” in a friendship network can mean “is related to,” “talked last week,” or “named as a friend,” and the network changes with the choice. Whenever a number is quoted about a network, ask how the link was defined.

Two questions turn out to organize most of network science. The first: how far apart are things? The rest of this lesson answers it. The second: does a typical node look like the others, or are a few nodes special? That is the subject of Lesson 2.

Six steps

In 1929 the Hungarian writer Frigyes Karinthy published a short story, “Chains” (Láncszemek), in which a group at a party plays a game: choose anyone among the earth’s 1.5 billion people, and see whether you can reach them through a chain of personal acquaintances. In the story, he says, five links would always be enough. The English translation of that passage is in a 2006 collection of classic papers on networks.

Thirty-eight years later the psychologist Stanley Milgram tested the idea. In the study he reported in 1969 with Jeffrey Travers, 296 volunteers, some in Boston and some in Nebraska, were asked to get a folder to a particular man who lived in Sharon, Massachusetts and worked in Boston. They knew only his name and a little about him. Each person was to send the folder to someone they knew on a first-name basis who seemed more likely to know the target. Of the 296 chains, 64 (22 percent) reached him. The completed chains had on average 5.2 intermediaries between the starter and the target, which makes about six links and is where “six degrees of separation” comes from. (Milgram never used the phrase. It became famous through the title of John Guare’s 1990 play. In Chinese the idea is called 六度分隔 liù dù fēngé.)

Milgram’s evidence was thin, and it was fair for later researchers to say so. Seventy-eight percent of the chains never reached the target. The psychologist Judith Kleinfeld, who went back to his archives, reported that in his first, unpublished pilot only 3 of 60 folders arrived. In 2003 Peter Dodds, Roby Muhamad and Duncan Watts repeated the experiment by e-mail: more than 60,000 people took part, trying to reach 18 targets in 13 countries. Of the 24,163 chains that were started, 384 (1.6 percent) were completed. The completed ones averaged about four steps, but that figure is misleading, because short chains are the ones most likely to finish. Correcting for the chains that stalled, the team estimated a typical distance of five to seven steps. Most chains stopped because people lost interest, not because the network had no path.

The largest direct measurement did not need volunteers. In 2011 a team at Facebook and the University of Milan measured the shortest paths among about 721 million active users, joined by about 69 billion friendship links. The average distance was 4.74, or 3.74 people in between. In 2016 the same measurement for 1.59 billion users gave 4.57. A 2008 study of about 180 million Microsoft Messenger accounts, with a link meaning “talked that month,” found an average of 6.6. So “about six” is the right ballpark, and the exact number depends on what a link means and who is counted.

Why paths are short

Why should the world be small? A rough argument goes like this. Suppose you know 150 people. Each of them knows 150 people, so you can reach 150 × 150, about 22,000, in two steps; in three steps, over 3 million; in four, over 500 million. The number of people within reach multiplies at every step, and multiplication gets large very quickly. The size of the world is hardly a limit: with k acquaintances each, the number of steps needed to reach a population of N people is roughly ln N ÷ ln k, where “ln” is the natural logarithm. For N = 8 billion and k = 150, that is about 4.5 steps. Because the logarithm grows so slowly, doubling the world’s population adds only a fraction of a step.

The argument is too generous, because your friends’ friends overlap with your own: many of the people you know also know each other. In the Facebook data, the formula applied to the average of 190 friends gives about 3.9 steps, but the measured distance was 4.74. The next activity lets you add overlap yourself. And how many people do we really know? Surveys using an indirect counting method (McCormick, Salganik and Zheng, 2010) put the average American at about 600 people and the median at about 470, using a fairly loose test of “knowing”. Dunbar’s famous number of about 150 is a different quantity, an estimate of the size of a close social group, and its exact value is disputed. The claim sometimes heard that we all know about a thousand people on a first-name basis is on the high side.

There is a second reason, and it is more surprising. Real networks are not only short but also clustered: your friends tend to know one another. A ring in which everyone knows only their near neighbors is very clustered but very large: the people on the far side are many steps away. In 1998 Duncan Watts and Steven Strogatz showed that replacing just a few of the local links by random long-range ones collapses the distances while hardly touching the clustering. They called the result a small-world network, and they found it in three real systems: the wiring of C. elegans, the electric grid of the western United States, and the collaboration network of film actors. In the film-actor network, for example, the typical distance was 3.65 steps, close to what a random network of the same size would give (2.99), while the clustering was about 3,000 times higher.

Two playful maps show the same idea. The mathematician Paul Erdős (1913–1996) wrote about 1,500 papers with more than 500 coauthors. Your Erdős number is 1 if you wrote a paper with him, 2 if you wrote one with one of his coauthors, and so on. And in 1994 three students at Albright College in Pennsylvania, Craig Fass, Brian Turtle, and Mike Ginelli, invented a game in which you link any actor to the actor Kevin Bacon through shared films. The average actor in the database is only about three links from him. These games work for the same reason as everything else in this lesson: a very large network, a few well-placed ties, and the multiplication of reach at each step.

A world drawn by chance

The mathematicians Paul Erdős and Alfréd Rényi gave the first theory of how a network might look when links are placed purely at random. In papers in 1959 and 1960 they imagined a set of dots with links placed between randomly chosen pairs. An equivalent picture, set out by Edgar Gilbert in the same year, is to go through every pair of dots and throw a die: if it comes up six, draw a link, otherwise not. Who ends up linked to whom is a matter of chance, but the overall picture is predictable. Almost every dot ends up with about the same number of links, near the average. A dot with many more links than the average, or with none at all, is very rare. The mathematical name for the spread is the Poisson distribution.

That has a consequence if the model is meant as a picture of society. In a society drawn by chance, no one would be much more popular than anyone else, and no one would be much more isolated: the person on your left and the person on your right would have about as many friends as you do. And random networks are also small worlds: distances in them grow like the logarithm of the size, just as in the argument above. So the small-world property alone is not what makes real networks special. What does? Real societies obviously contain people with thousands or millions of followers, and nothing like them in a random network. Lesson 2 asks what a map of a real network looks like, and what it says about how it grew.