|
|
CMSE Online Front
Page |
The world is tied together by a network of personal relationships, and often we're impressed by how tightly these connections work. A and Z come from different parts of the country, yet they have a mutual friend C. Or perhaps A knows B, B knows C, and C knows Z. When we discover these unexpected relationships, we say, "It's a small world." There's a popular hypothesis called Six Degrees of Separation which says that given any two people in the world, they can be connected through at most six "friends of".
Now two mathematicians at Cornell University have shown that any network will probably be a "small world" of this kind, provided it has just a few random connections joining otherwise widely separated regions. Following is the full text of the June 4 Cornell news release describing this discovery. [News releases are generally not copyrighted, but if you use them be sure to give full credit to the source!]
Kevin Bacon shows the way to a much smaller world than we thought, Cornell mathematicians find
FOR RELEASE: June 4, 1998
Contact: Bill Steele
Office: (607) 255-7164
E-Mail: ws21@cornell.eduITHACA, 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 hand-in-hand 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 "small-world 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 small-world 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 real-world 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 small-world 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 small-world networks." Duncan Watts is now a post-doctoral 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.
-30-
FEEDBACK: We'd be glad to have your comments and suggestions!
Posted June 12, 1998. Features remain online as long as they remain current; they may be updated if new information becomes available.
Copyright © 1998, Center for Mathematics and Science Education. Teachers have permission to duplicate this page for use in teaching their own classes. All other rights reserved. You are welcome to link to this page, but do not copy its contents.
|
http://www.unc.edu/depts/cmse/math/smallworld.html Center for Mathematics and Science
Education PHONE: voice (919) 966-5922; fax (919) 962-0588 |
CMSE Online Front
Page |
