by Greg Satell
* * *
Over the next two centuries, graph theory became a widely studied topic for ordered systems, from chess strategies to the atomic structure of crystals. Mathematicians today continue to use graph theory to study networks of connections. However, in the 1950s, graph theory took on a new life with the study of random networks, thanks to a Hungarian-born mathematician named Paul Erdős (pronounced “Erdish”).
Erdős was almost a purely mathematical being, and one of the few mathematicians in history almost as prolific as Euler: he published no fewer than 1,500 papers before his death at 83 in 1996.8 He often said that he considered mathematicians to be machines who turn coffee into theorems, and his caffeine-fueled working sessions sometimes lasted as long as 20 hours a day. When one of his (usually considerably younger) collaborators succumbed to exhaustion, he would call another on the phone and announce: “My brain is open.”
Incidentally, Erdős’s incredibly prolific work led him to become an exhibit in network theory himself. Even today, more than 20 years after his death, many mathematicians rate themselves based on their “Erdős number.” Those who collaborated directly with the legendary genius earned themselves an Erdős number of one. Those who worked with those collaborators receive an Erdős number of two, and so on.
Erdős was as famous for his outlandish personality as for his genius. A citizen of the world, he lived mostly out of worn suitcases and off the hospitality of friendly mathematicians. He would arrive at their houses, usually unannounced, declare, “My brain is open,” and then stay for a few days, or a few weeks. His unwitting hosts would have to compensate for his inability to do almost any activity a normal person performs in the course of daily life. Erdős couldn’t cook, drive, or even tie his own shoes. Stories of Erdős are legion. One mathematician recalled:
Erdős came to my twins’ bar mitzvah, notebook in hand. He also brought gifts for my children—he loved kids—and behaved himself very well. But my mother-in-law tried to throw him out. She thought he was some guy who wandered off the street, in a rumpled suit, carrying a pad under his arm. It is entirely possible that he proved a theorem or two during the ceremony.9
To understand what Erdős and his Hungarian friend Alfréd Rényi discovered about random networks, imagine throwing a party for a hundred complete strangers. After a short while, the partygoers break off into small groups of two or three, chatting away. And there’s some mingling at your party, too—every five minutes, two people from different groups swap their places.
Amidst the pleasant cocktail conversation, you whisper to one guest that you have a nice bottle of single-malt scotch, and you’ll serve him a few fingers—as long as he tells no one else. But of course, the scotch loosens his tongue a little, and he mentions the prized bottle to one random person he meets in passing. Erdős and Rényi proved three things about this scenario:
First, your excellent scotch will be gone in record time: if each person passes the secret on to only one additional person in a different group, the chain will soon envelop everyone at the party. Those invisible ties, once connected, will allow information to transfer among the previously disparate group, causing its behavior to synchronize.
Second, even if the links were completely random and undirected, the party guests would be connected through remarkably few clusters, because not every grouping would need to be directly connected to each other. Many guests, in fact, would be connected through intermediate groups. Nevertheless, a single chain would connect them all.
Finally, and this is a crucial point, the groups in the room will not connect gradually: they will go from being relatively dispersed to being entirely connected in one step. This phenomenon is known as an instantaneous phase transition, and it explains why cascades take off so suddenly, like when my fiancée suddenly starting going to political demonstrations at the same time everyone else did. However, it takes a little thinking to understand how it works.
First, some math: The Erdős-Rényi theorem holds that if there are 40 groups in the room, generating 780 potential links amongst them all only takes 72 links to guarantee a continuous chain.10 So, if every group in the room makes a connection to another group by exchanging a member every five minutes, then 60 links would have been created after 15 minutes. Yet because the links between groups form randomly, those 60 links will be unevenly distributed, leaving some groups tightly clustered while many others remain completely unconnected. In the next five-minute shift of mixing, however, the 72-link threshold will have been met and the entire party will have formed a continuous chain. A complete phase transition will have taken place in that one step.
A particularly vivid example of this phenomenon is the LOLCats videos that exploded on the web with no apparent origin. Seemingly all at once, they were traveling virally at breakneck speed as millions of people in offices and dorm rooms passed them back and forth. In actuality, there was nothing sudden about the LOLCats meme. It had been incubating for months on an online community called 4Chan, whose members occasionally sent them to friends outside the group. Eventually, the system tipped and LOLCats seemed to explode on the general consciousness all at once.11
A similar process took place on that morning in November 2004, when I woke up to find that the entire country of Ukraine had changed. It had been, of course, brewing for months, but I only really noticed it when people close to me got involved, despite the fact that I was working in a news office every day. Once the people that I knew started going to demonstrations, I joined in just like everyone else.
The Erdős-Rényi theorem also explains how Netflix transformed itself from a niche service into an overnight sensation. While the number of Netflix customers was small, they were connected to many others. As their enthusiasm for the service convinced people they knew to try it, the market for Netflix grew like wildfire. In much the same way, it explains how Silicon Valley overtook Route 128. Because the tech entrepreneurs on the West Coast regularly mixed with former colleagues and those outside Boston didn’t, new technologies were able to spread faster, build scale, and dominate their more traditional rivals.
What we often miss when we look at nascent trends in the early stages is that diverse groups tend to intersperse and connect. These connections don’t form in an organized, 58gradual manner, but exponentially. So while one minute you see a disperse assortment of unaffiliated people, the next minute there is one long, connected chain acting in concert. It is, as I noted earlier about my personal experience in the Orange Revolution, like someone flips a switch. Just like that, the world changes.
In effect, Erdős and Rényi showed how groups of millions of fireflies—or protestors, or consumers—could be connected with extreme efficiency through random links. For Duncan Watts, the phenomenon of phase transition, much like Milgram’s small-world phenomenon, suggested that he was onto something important.
However, it was clear to Watts that, in the real world, things don’t link randomly. If we go out for a few beers with friends, it’s unlikely we met them at random. They’re probably people we met at work or school or who live in our neighborhood. If our relationships were truly random, we would be just as likely to meet people from across the world as from across the street. Experience, intuition, and common sense tell us that’s simply not how relationships function.
As it turned out, about 10 years before Erdős and Rényi proved their theorem about random networks, another mathematician, Anatol Rapoport, studying an altogether different problem, found a similarly efficient network structure that was not random.
Rapoport, a Russian émigré to the United States, had an unusually expansive career.12 Originally he had studied to be a concert pianist, but he switched to mathematics in his twenties and earned his PhD at the age of 30, in 1941, from the University of Chicago. Throughout a prodigious career, he made important contributions to mathematical biology, game theory, and network theory.
In the 1950s, Rapoport was studying how epidemics spread, and he began to realize that, as re
lationships develop, they tend to become more clustered. If you have two friends who don’t know each other, there is a high probability that they will eventually meet through you and form their own relationship. Rapoport called this concept triadic closure.13 The idea intrigued him, and in 1961 he collaborated with William Horvath to study junior high school students in Ann Arbor, Michigan. Rapoport and Horvath asked more than 800 students to list eight friends in order of the strength of the relationship: the best friend is listed first, the next best friend second, and so on.14
The mathematicians then attempted to map out the relationships according to the top two friends on each list. They didn’t get very far. Only a small fraction of the student body was connected this way. However, when they mapped the relationships by using the bottom two names on the students’ lists, showing the weakest relationships rather than the strongest, they found that almost the entire school was connected—much like the scotch-drinking cocktail party guests in the random-networks scenario. What Rapoport and Horvath learned was that information spreads not through best friends but casual acquaintances.15
Mark Granovetter, a sociologist who knew both Milgram’s and Rapoport’s work, decided to research the matter further. In the late 1960s and early 1970s, he studied how people found jobs in communities around Boston. He soon found that successful job searches revolved around a strange combination of acquaintance and chance.
In a book describing his research, Granovetter cited three examples. In the first, a salesman who was earning poor commissions started driving a cab to supplement his income. One day, he ran across an old friend while dropping off a passenger. His friend, surprised to see him driving a taxi, offered him a job as his company’s labor relations manager. In the second example, a man named Edward had recently been discharged from the military. At a local playground, he met an older friend from the neighborhood who was working for an engineering firm and told Edward about an entry-level opening. Edward applied for the job and started a career in engineering. In the third example, Franklin, a stockbroker in Philadelphia, had received an offer from a firm in Boston. Before he accepted the job, he happened to go to Boston on a business trip with another member of his firm. During the trip, Franklin’s friend suggested that they have a casual lunch with Robert, an acquaintance of the friend. When Robert found out that Franklin was considering relocating to Boston, he later contacted him privately and made him a better offer.16
These examples seem unexceptional. Still, when you think about it, choosing a job is a major decision. It’s strange that career paths are so often determined by casual encounters. Granovetter found that more than 80 percent of the people in his study who found a job through a contact did not have a close relationship with the person who lined up the offer. In seeking an explanation, he cited Rapoport and Horvath’s Michigan study.17
The phenomenon reminded Granovetter of something he had learned in a chemistry class about water. Besides the strong bonds between hydrogen and oxygen, there are also weak bonds between the water molecules themselves, which causes the molecules to cluster, forming raindrops. The similarity between the weak bonds of water molecules and human relationships was striking, which inspired Granovetter to brand his idea “the strength of weak ties.”18
In some very important ways, human relationships do resemble molecules floating around in a liquid. While we have a few close relationships, we have many more casual ones, and those relationships form connections to an even larger and more disparate group. Moreover, those who are closest to us tend to come across the same information we do. If you’re searching for a job, or if you want to coordinate activity across a large group, you’ll most likely do it not through close friends, but through the casual acquaintances of second- and third-degree links that connect you to the greater world.
DISCOVERING SMALL-WORLD NETWORKS
* * *
So for more than 200 years before Duncan Watts attacked the problem of coupled oscillation, there had been scattered pockets of insight. Euler showed that arrangements of links and nodes could be a fertile mathematical area. Erdős and Rényi proved that even random arrangements of links can be incredibly efficient. Rapoport highlighted that real-life networks that were neither random nor directed, but biased toward clustering, were just as potent as random networks. Granovetter showed that these clusters could be very effective in transmitting information through second- and third-degree relationships.
Each breakthrough formed a piece of the small-world “six degrees of separation” phenomenon Milgram had exposed in his landmark experiment. However, no one had put them all together. In network terms, the information remained unconnected. It was Watts, under Strogatz’s direction, who would show that information naturally forms a particular kind of network that accounts for the amazing behavior of pacemaker cells, fireflies, snowy tree crickets, and, more important to our story about cascades, protestors in a political revolution, consumers in a marketplace, terrorists on a battlefield, independent units in a large organization, and many other things.
Like many scientists, Watts was a fan of science fiction, and he had another idea for researching networks, based on two Isaac Asimov books he had read as a child. He didn’t know it when he started his research, but hidden in the imagination of that famous author he was about to find the final piece to a puzzle that had baffled scientists for a very long time.19
One book, Caves of Steel, is about a future planet where everybody lives in underground caves. There is very little interaction between the caves, so if you lived in one, you would only know the people in your cave and nobody else. Moreover, in the close confines of the cave, the people you know also know each other. In the other book, The Naked Sun, the situation was at the other end of the communications spectrum. The novel is set on a planet called Solaria, where everybody lives on huge plantations and communicates remotely. Nobody’s acquaintances know one another.
Watts decided to set up a mathematical model that would take into account both extremes and everything in between. He called his first attempt the alpha model, which examined the likelihood that two people would connect as a function of the number of mutual friends they had.
A graphic description of the model can be seen in Figure 2.3. The very top line represents the “caveman” world. As soon as two people have a mutual friend, they immediately meet each other. If they had no mutual friends, that would indicate they were in different caves and would never meet. The bottom line represented the “spaceman” extreme, where mutual friendships don’t increase the likelihood of meeting at all.
FIGURE 2.3 Likelihood of Meeting as a Function of Number of Friends
* * *
What Watts was most interested in, however, was all of the possibilities in between.
The Alpha Model
Although he didn’t immediately realize it, Watts had found a model very similar to Rapoport’s random-biased nets. The more friends you have in common with someone else, the more likely you and that person are to become friends. However, unlike Rapoport, Watts had access to powerful computers, so he could explore the idea further by using the “alpha” metric to run simulations of systems with different attributes.
Armed with this mathematical representation of Rapoport’s random-biased nets concept, Watts set out to see what would happen to the degrees of separation (technically called path lengths) as you increased the alpha metric. What he found amazed him so much that at first, he thought he had done something wrong. As alpha increased, in effect connecting caves or tent cities, path lengths increased (Figure 2.4). In other words, Watts found that it took more steps to connect one person to another. But then, alpha reached a critical value, and suddenly they crashed down to very low path lengths again.20
FIGURE 2.4 Change in Path Length as Alpha Increases
* * *
While this model is highly counterintuitive, it does make sense. Imagine you’re living in a cave world, and an opening in your cave allows you to start meeting people
in another cave. At first, the social distance for the combined communities is larger than when you started, because most people in the caves remain unconnected. Yet as time passes and the new reality of the connected caves sets in, more connections are built, and eventually the connected caves start to behave like one big community. We see an almost instantaneous phase transition where we might expect to see gradual change.
When groups first connect, there is always a period of awkward distance. Much like a dance at summer camp, where the boys and girls start on opposite sides of the room, the first connections are slow to happen. But eventually, two camp counselors start dancing, then a few campers, and then everybody. It’s also precisely what I saw happen in the Orange Revolution in Ukraine. At first, the activity was dispersed around Ukraine. Then one morning, I woke up, and my fiancée was going out in her orange bandana to protest. Before I knew it, it seemed that everyone in Ukraine was attending protests and rallies. The world had changed, almost literally overnight. It was like someone had just flipped a switch.
Put into a real world context, the alpha variable translates roughly into the difference between living on campus in college (high alpha) and living off-campus (low alpha). The problem with the alpha model, however, is that it is very hard to understand what the alpha metric actually represents. It makes sense as a mathematical variable but explains little about the real world. So Watts began to work on a more intuitive version he called the beta model.21
The Beta Model
The beta model (Figure 2.5) works like this: Imagine you’re in a football stadium, standing with a ring of spectators around the circumference. You can communicate pretty easily with those standing close to you, but those across the stadium might as well be out in the parking lot, or even in another city. Although they’re connected to you through the other people in the ring, the connection is so loose that they might as well not be. Now hand out a few mobile phones randomly. Suddenly, the social distance of the ring collapses. You can call someone on the other side of the stadium and that person can get the message to anyone near him or her. The social distance collapses, and all it takes is a little random mixing.