From Muhammad Ali to Grandma Rose

When Duncan Watts was pursuing his Ph.D., his adviser was Steven Strogatz, who has written scientific papers with Rennie Mirollo, who was a teaching assistant for Steve Maurer, whose mother used to live down the hall from my Grandma Rose in a high-rise in Hackensack, New Jersey. Small world, right?  Such coincidences crop up a lot. They feel so familiar that there's even a popular legend to explain them. According to cocktail-party lore, every pair of people on the planet--a randomly chosen Inuit and a Parisian, a Solomon Islander and a dude from Nebraska--are connected by a chain of at most 6 acquaintances. I personally, to drop only a few names, am 2 steps from Prince Charles and Stephen Hawking, 3 steps from Marilyn Monroe and King Carl XVI Gustaf of Sweden, 4 steps from King Juan Carlos of Spain, and close friends with the brother of a childhood buddy of the crown prince of Holland. The Discover art department has grislier connections: The picture editor is 3 steps from John Hinckley, Ted Bundy, and Adolf Hitler. The assistant picture editor is 2 steps from Charles Manson and Bugsy Siegel. The associate art director is 2 steps from Gary Gilmore and 3 from Jeffrey Dahmer (through 1 of his victims). The associate production editor knows a friend of the grandson of the man who assassinated Rasputin. And chances are you too have similar connections.  Without coincidences like these, literature as we know it, from Oedipus Rex to Great Expectations, could hardly exist. Two recent examples have lent their names to, or maybe borrowed their names from, the phenomenon: Six Degrees of Separation, a play and film by John Guare (who's pals with my best friend's father), and Small World, a farce about academics who all seem to know each other's colleagues, by the British novelist David Lodge (no connection that I know of).  Strogatz and Watts have also written about the phenomenon, but their paper is a work of math, not fiction. The "small worlds" they study are networks that consist of lots of little cliques, but in which a few members of each clique have connections to other, more distant parts of the network. These longer connections make it easy to find short paths through the network from any one point to any other. "The small-world effect is not just a curiosity about social networks," says Strogatz, an applied mathematician at Cornell. "It occurs in many different kinds of networks throughout nature and technology. We give examples of that in our paper, and we also try to give a mathematical way of understanding why it might be so common." The small-world effect could have a lot to do with how diseases like aids spread, for example: the idea that everyone is at most 6 degrees apart takes on a sinister significance when we look for shared sexual partners instead of shared acquaintances. It could also explain how rumors spread, says Watts, who is now a post-doctoral fellow at the Santa Fe Institute. It could explain how a blackout could propagate across an entire power grid, how year 2000 bugs could bring down vast computer systems, and perhaps even why neurons in the brain are connected the way they are.  The popular conception of the small-world phenomenon may have arisen from a 1967 experiment by Harvard sociologist Stanley Milgram, who asked people in Kansas and Nebraska to get letters to strangers living in Boston by sending the letters to friends who they thought might have a chance of knowing the Boston targets, or of knowing people who did. Milgram found that half the letters took 5 intermediaries or fewer to reach their targets. "That was the experiment that I think led to the idea of 6 degrees of separation," says Strogatz. But for 30 years, until he and Watts turned their attention to the problem, it remained mostly social-science territory.  "Why is the small-world phenomenon surprising?" asks Strogatz. "Why shouldn't it be obvious that we're only 6 degrees of separation apart, or some other small number?" Mathematically minded people, he explains, often approach the question with a simple calculation: suppose I have 100 friends, each of whom also has 100 friends. A hundred times 100 makes 10,000 friends of my friends. If each of those 10,000 people has 100 friends, there will be 1 million people 3 degrees away from me. Five steps away, there are 10 billion. "So a lot of people would say it's not surprising that the degree of separation is small," concludes Strogatz, "because within 5 steps you've done the whole planet."  But there's a big assumption in that calculation. It presumes that each 100 friends are 100 new people. If everyone chose their friends at random from the entire world, the assumption would be valid, but we clearly don't. "The world that we live in is not at all random," as Watts points out. "We are very much constrained by our socioeconomic status, our geographical location, our background, our education and our profession, our interests and hobbies. All these things make our circle of acquaintances highly nonrandom."  In the real world many of one's friends know each other. For example, I cheated in describing my 6 degrees of separation from Strogatz--Mirollo, Maurer, Mrs. Maurer, Grandma--since in fact I know all these people directly: I met them all (except Grandma and Mrs. Maurer) at a summer math program 20 years ago. If friends all know friends, the same 100 people could be counted over and over again. And it's easy to imagine a very exclusive clique of 100 people in Greenwich, Connecticut, say, who know only one another and wouldn't dream of associating with anyone outside their circle. Conceivably, no chain of acquaintances connects you or me with any member of that clique. "So how do you even begin to think about these sorts of networks?" asks Watts.  Watts and Strogatz started by looking at the kinds of networks mathematicians already know quite a bit about: highly structured networks--such as the graph-paper lattice of atoms that make up a crystal of salt--and completely random networks. "Cubic lattices are great to study," says Watts, "because any part of the lattice looks the same as any other part. It's relatively easy to do analysis on things like that." It's also easy to do analysis on networks that are completely random "because even though you can't figure things out exactly for random networks, you can do things approximately or statistically"--as we just did when estimating how many fifth-degree friends a member of a random world will have.  Networks that are neither completely random nor as regular as graph paper are much harder to understand mathematically. And many real-world networks, perhaps even most, seem to fall in the middle. So Watts and Strogatz built model networks that fell in the middle, too. They began with a beautifully structured network called a ring graph. Although it's not quite as symmetrical as a lattice, it would still warm a control freak's heart.  "Think of a lot of people standing in a circle holding hands," says Watts. "Say there are a million people and you know 100 of them. You know 50 people on your left and 50 people on your right, and they are the only ones you can communicate with. What if you want to get a message to person number 500,000 on the other side of the circle--how do you do that? Well, you shout the message to your farthest friend, number 50 to your left side, and say, ëPass it on.' The best they can do is shout to their fiftieth friend to the left, and so on. So you have to go from 0 to 500,000 in steps of 50. That's 10,000 steps. From you to the farthest person in the world, in this particular world, is 10,000." The distance between you and number 250,000, a quarter of the way around the circle, will be 5,000. Between you and number 125,000, an eighth of the way, it will be 2,500; between you and number 300,000, a bit more than a quarter of the way around the circle, it will be 6,000. On average, there are 5,000 steps between pairs of people in this world. And 5,000 degrees of separation, as Watts points out, is an awful lot.  Now imagine the same million people standing in the same circle. Each still has 100 friends. But instead of knowing only the 50 people to the left and the 50 to the right, everyone chooses friends at random from the million people available. "Because you can pick from a million, and there are only a few people standing near you, chances are you will almost always pick someone who is not physically close to you," says Watts. Now when he and Strogatz calculate the average degree of separation between 2 people, it comes out to about 4, which is easy to believe--start multiplying 100 by itself and in 3 steps you've hit a million. ("Why do we say 4 on average and not 3?" asks Watts. "Because by the third step, it's quite likely that people will be picking friends who have already been selected, so some people will have been reached twice and others not at all. If you go out another degree, to 4, you probably really have reached just about everyone.")  The other thing you'll notice about this random network, says Watts, is that almost none of your friends know one another. The first, orderly circle, in contrast, is what mathematicians call highly clustered. It's full of cliques. "The guy next to you knows almost everyone that you know," says Watts. "You have an almost complete overlap of friendship. And even your farthest friend knows half of your friends. Each person is not adding much to the pool of acquaintances, whereas in the random world it's very clear that each new person is opening new doors."  But what happens between the orderly world and the random one? To find out, Watts and Strogatz started with an orderly model and carefully messed it up, making worlds that were progressively more random. "On the computer you build the first world, the ring, and then you just start picking up connections between people at random and moving them, as if they were made of bungee cords," says Watts. So instead of knowing the 50 people to your right and the 50 to your left, you might know the 50 to your right and 49 of the 50 to your left. But number 17 to your left is a stranger; instead you're close friends with number 307,411.  These new connections quickly bring the world closer together. In a big world, says Watts, "if you make one of these random connections, the chances are that you will connect to somebody who is many, many, many degrees of separation away from you. When you do that, a lot happens. Before that connection was made, you were maybe 1,000 degrees of separation apart; now you're 1 degree apart. So that's a big difference for the 2 of you. But it's not just the 2 of you involved, it's also your friends. All your 100 friends are now 2 degrees of separation away from that person, and they are only 3 degrees of separation away from all of that person's friends. So suddenly, whereas they were all more than 1,000 degrees of separation apart, now they're only 3 degrees. And your friends of friends and their friends of friends are only 5 degrees of separation apart. So huge chunks of the world are being brought closer together by virtue of a single connection."  It takes only a tiny number of rewirings--less than 1 percent of the total connections--to bring the average degree of separation down from 5,000 to just over 4, close to the average degree of separation of a random world. With a few random encounters, the big, wide world becomes virtually as small as a random world.  Oddly, though, rewiring a few connections has almost no effect on the network's level of clustering. Almost all your friends still know one another, as they did before, and since they don't know anyone on the other side of the circle, they might not even know about your new connection. For example, childhood friends of Strogatz, who was born in Torrington, Connecticut, probably have no idea that they're only 2 degrees apart from residents of Toowoomba, a little country town in southeast Queensland, Australia, where Watts grew up. They'd never guess that they're only 3 steps from the former secretary general of the Vietnamese Communist Party, Do Muoi, or the Cambodian leader Prince Norodom Ranariddh, through Watts's sister, an Australian diplomat.  Looking at their computer models, Watts and Strogatz came up with what Strogatz calls a fuzzy definition of a small world: a network with about the same average degree of separation as a random network of the same size but with much more clustering. They tried building models with other sorts of networks as a starting point, not just rings: "We tried different dimensions, different structures," says Watts, "but we always found that a little bit of randomness goes a long way in terms of the global properties of the system. Very soon, no matter what you start with, it starts to look like a small world."  But how common are these small worlds in nature? Strogatz and Watts began looking around for networks in which every connection was known, allowing them to determine the shortest possible path between any 2 points. Such networks were hard to find, but they turned up 3: the neural network of Caenorhabditis elegans, a nematode worm; the power grid of the western United States, a map of power stations connected to one another by high-voltage transmission lines; and the Hollywood graph, a database of everyone who has ever acted in a feature film. "That includes silent movies, movies made in India--everything," says Strogatz, "so that's an enormous graph, with currently about 300,000 actors in it--although it gets bigger every day. You say that 2 actors are connected if they've ever been in a movie together." People use this very database--available on the Web at http:// www.cs.virginia.edu/~bct7m/ bacon.html - to play a game called Six Degrees of Kevin Bacon, tracing connections between the footloose thespian and other Hollywood luminaries. Charlie Chaplin, for example, is only 3 steps from Kevin Bacon--he was in The Countess from Hong Kong with Marlon Brando; Brando was in Apocalypse Now with Laurence Fishburne; and Fishburne was in Quicksilver with Kevin Bacon.  Although Watts and Strogatz chose those three examples because they were the only networks they could find in which all the connections were known--"It's not like this was some crafty choice," says Strogatz--all turned out to be small worlds. Bingo, all three times. So the researchers suspect that the natural world is teeming with small worlds. But, of course, they don't know for sure. "Is this as widespread a phenomenon as we guess it is?" asks Strogatz. "I would look forward in the future to work by, say, neurologists mapping out brain networks or other nervous systems. The people who study ecology could study food webs--which organisms are eating each other. In economics it would be interesting to trace out networks of markets and consumers and buyers and sellers. I'm sure there are people who are thinking about network theory in economics and in finance--it could be at the level of whole nations interacting, or even just individual people."  Bill Ditto, a physicist who runs the Applied Chaos Lab at Georgia Tech, calls Strogatz and Watts's work a breakthrough. Ditto works with biologists, doctors, and computer scientists trying to understand how connectivity in the brain contributes to both computation and pathologies like epileptic seizures. Because it's costly for the brain to make lots of extra connections between neurons and to grow connections across long distances, you might expect most connections between brain cells to be local. And indeed, many are. But there are also long, sparse connections reaching into distant regions of the brain, and nobody quite understands their purpose, says Ditto. He suspects they may be there partly to help control epileptic seizures, in which wild, crippling electrical storms spread across the brain.  Forest fires, says Ditto, make a good analogy for epileptic seizures. Firefighters sometimes set small, controlled fires to burn away the fuel in the path of a forest fire. With nothing left to burn, the rogue fire stops in its tracks. In epilepsy, one of those mysterious long-range connections could send a signal ahead of a seizure, starting a wave of activity in a not-yet-affected part of the brain. Since brain cells have to rest before they can fire again, the wave would act as a firebreak, containing the seizure. "This is all really preliminary and speculative," says Ditto, "but we think that it's very profound."  Ditto and his colleagues also plan to exploit the small-world effect in a new project--building a computer out of a hybrid of silicon and living neurons. They hope that adding a few long-range connections will make their new computer behave more like a living brain.  Interest in the small-world problem has been spreading like wildfire (or contagion, or rumors about the bond market, or a new fad in footwear). Since his and Strogatz's paper was published, remarks Watts modestly, "I think I've been contacted by someone from just about every field outside of English literature. I've had letters from mathematicians, physicists, biochemists, neurophysiologists, epidemiologists, economists, sociologists; from people in marketing, information systems, civil engineering, and from a business enterprise that uses the concept of the small world for networking purposes on the Internet." And chances are, you know someone who knows someone who knows someone who knows someone who knows someone who knows those people.