1998 From: Cornell University News Service
Networks Become 'Small' Very QuicklyITHACA, N.Y.  The game "Six Degrees of Kevin Bacon," in which actors can be connected to one another through their appearances in films with actor Kevin Bacon, works because Hollywood movies are a "small world," in mathematical terms. It's a world where actors are grouped into clusters  the casts of each film  and there are many interconnections between the clusters. But two Cornell University mathematicians have now shown that small worlds are probably common in many networks found in nature and are easy to create in systems as diverse as networks of people, power grids and the neurons in the human brain. All it takes is a few extra random connections. "It's not just the world of people that's small," says Steven H. Strogatz, professor of theoretical and applied mechanics. "There's a unifying mechanism in nature that makes things small." The mathematical analysis by graduate student Duncan J. Watts and Strogatz is reported in the June 4, 1998, issue of Nature.. Their findings can be both useful and scary. The useful part is that adding just a few connections to something like a cellular phone system or perhaps even the Internet might greatly speed up communication. The scary part is that speeding up connections might cause overloads, and just a few extra connections between people might greatly speed the spread of disease. The researchers point out that mathematicians have focused their attention on two extreme types of networks: "random," where every node is haphazardly connected to a few others ; and "regular," where each node is connected only to its immediate neighbors. "Hands across America," the 1986 demonstration for the homeless in which 7 million people stood handinhand across the country, would be a classic example of a regular network; it would take a long time to pass a message from the East Coast to the West Coast. In a random network all those people would be sitting together in Yankee Stadium and each one would have a telephone connected to about a dozen others scattered around the field. Watts and Strogatz dealt only with "sparse" networks, in which each node has only a few connections compared to the total number of nodes in the system. In a "dense" network, everyone in the stadium would be connected to everyone else, and "of course messages would get around quickly," Strogatz says. In the real world, most networks lie somewhere in between regular and random. Socially, most people belong to a small group of closely interconnected friends and acquaintances, and some of those are connected to people in other groups near and far. The Kevin Bacon game grows out of the idea of "six degrees of separation," the calculation that everyone in the world is connected to everyone else through an average of six steps. Watts and Strogatz graphed the changes in connectivity that occur as more and more connections are added to a regular network, until it becomes totally random. What they found, somewhat to their surprise, was that after just a few extra connections were made, it didn't much matter how many more were added. Just a few "shortcuts" brought everything closer together. They call these partly connected systems "smallworld networks." "The traditional approximations of networks, which assume either that everything is completely ordered or completely random, cannot in general predict the kinds of properties that we see in smallworld networks," Watts has written. "The harder we look at the world around us, the more we see networks. We happen to think that most, or at least many, of these networks will turn out to have the sorts of properties that we talk about in our paper." The researchers tested the idea by graphing three realworld networks, chosen because data on them was readily available: a list of film actors drawn from the Internet Movie Database, the western U.S. power grid and the network of neurons in the nematode worm C. elegans, the only creature whose neural network has been completely mapped. They found that all three were smallworld networks, in which you could get from any point to any other very quickly. They also applied the analysis to a model for the spread of an infectious disease through a population and found that disease would spread almost as quickly through a "small world" as through a world in which everyone was connected at random. "The alarming and less obvious point is how few short cuts are needed to make the world small," they wrote. The paper in Nature is titled "Collective dynamics of smallworld networks." Duncan Watts is now a postdoctoral fellow at Columbia University. For those who would like to examine the connections between actors further, Strogatz suggests consulting "The Oracle of Bacon at Virginia," a web site created by Brett Tjaden at http://www.cs.virginia.edu/~bct7m/bacon.html. "It can be shown that about 90 percent of all actors in the entire history of films have a Bacon number (the number of steps from that actor to Bacon) of four or less," Strogatz says.
