|
'd like to hand-deliver a copy of this article to the actor Will Smith. Unfortunately, I've never met him. I don't even have any friends who know him. Maybe, though, I know somebody who knows somebody who knows him. If only I could find the right sequence of people, I could get the article passed on to him.
Such chains of association exist. In fact, experiments conducted in the 1960s suggest that every person is connected to every other through an average of about six first-name-basis acquaintances.
This "six-degrees-of-separation paradigm" says that if you find the right string of friends, relatives, colleagues and lovers, you can move in six steps (or thereabouts) from Donald Sutherland to the Dalai Lama, from Stockard Channing to an Indonesian shepherd, or from Will Smith to yours truly.
A new network model designed by a Cornell University computer science professor makes it easier to find those short routes.
"It's not just that networks have all these short paths, which previous work has already shown," said Jon Kleinberg. "But that it's possible to actually find the short paths, and to find them without a map. You don't have to have a bird's-eye view of the network."
Some networks are more orderly than others. For instance, mailing a copy of this article to Will Smith would be easy. An addressed package would enter a carefully designed system, where it would be collected, sorted, transported and delivered according to specific rules and hierarchies.
Other networks, though, like societal connections, the World Wide Web and neural pathways, aren't designed, they just happen.
"The question is, 'Can a hierarchical structure like the postal system -- which supports rapid navigation -- arise from a randomly evolving network, without being centrally planned?' " Kleinberg said. "And indeed, it turns out to be possible."
Kleinberg's model has implications for both human and computer networking. It can help improve the design of software "agents" that seek out specific information on the Web, and might make it easier to gain the sympathetic ear of a philanthropic tycoon.
Kleinberg's model was inspired by a 1967 experiment by Stanley Milgram, a social psychologist. In that exercise, randomly selected residents of Omaha, Neb., were asked to get letters to particular people in Boston. A participant could pass the letter on only to someone they knew on a first-name basis, who would then pass it on, and on, and so on. The median number of steps from Nebraskan to Bostonian was five or six. (This "small-world method" experiment begat the phrase, "six degrees of separation.")
"No one person along the way knew anything but who their friends were," said Kleinberg. "So you couldn't say that one person was doing anything particularly clever to aim the message at the target. If you ask where the information is that tells you how to get to targets, it doesn't reside within any one person. Somehow it's actually intrinsically in the network."
He built a model that mimicked the structure of social connections to try to find out how a network can contain such information. The model hinged on getting a true-to-life balance of short- and long-range connections.
To understand Kleinberg's model, it's easiest to slightly oversimplify. Pretend there are only three distances at which you know people: people from your town, people from other towns in your province and people from out of province.
Naturally, the most densely meshed chains of acquaintances will be within your town. But what Kleinberg found was that if you "zoom out" to the provincial level, the pattern of connections actually looks a lot like that at the town level. And if you zoom out again to the highest level, a similar-looking pattern emerges again.
So the connections for any one person (or "node" in network-speak) create patterns on one level that resemble patterns at another. If it were possible to make a complete map of the global network of friends, these patterns would be repeated at many times on many levels.
This self-similarity at different "resolutions" explains how a message can make it so quickly through such a haphazard network.
When people choose whom to give the message to, they can make only the best guess according to what they know about their own lines of association. But the repeated patterns mean a good decision on an individual level probably will also make sense in the big picture.
Kleinberg's discovery won't yet help me get a copy of this article into Will Smith's hands. It would, however, help find the path if more data were available. The trouble is, no one keeps a database of my friends, my friends' friends and my friends' friends' friends. And that particular information is not likely to become available.
"If you just go up to random people and say give me a list of all your friends, most people are not likely to do so," said Gabriel Robins, a computer science professor at the University of Virginia. Robins built something called the Oracle of Bacon, a rather stunning demonstration of a variation on Milgram's small-world method: the Six Degrees of Kevin Bacon.
The Oracle uses a database of more than 100,000 films to link actors who have co-starred with each other. It finds the shortest path from any actor to Kevin Bacon. The Web-based Oracle (www.cs.virginia.edu/oracle/) generates a "Bacon Number" for any given movie star.
For example, Will Smith and Stockard Channing both have a Bacon Number of two: Smith was in Independence Day with Gary Hecker who was in Hollow Man with Bacon; Channing was in Twilight with Clint Howard who was in My Dog Skip with Bacon.
Donald Sutherland, who was in JFK with Bacon, has a Bacon Number of one. Very few movie actors from any era or country have a Bacon Number greater than four.
Finding short paths affects more than trivial pursuits. A Virginia police department employs Oracle of Bacon technology to link crooks to one another using criminal records, and the University of Virginia Business School alumni association is experimenting with Oracle-assisted fundraising.
"The trick with a campaign drive is getting donors who are quite rich," Robins said. "But you have to be very careful how you approach them. With someone like Bill Gates, you can say, 'Well, he should donate $10-million to our university simply because he has it.' But it's not that simple, because he gets thousands of requests like that a day.
"What you want to do is get a friend of his to bend his ear during a dinner party somewhere and say, 'I think the University of Virginia is a very good thing, and if you're feeling philanthropic it would be a good place to put $10-million into a building.' But you don't really know his friends and you can't approach them either, because it can be a bit awkward. What you want is one of your alumni who knows a friend who knows Bill Gates. So the question now is,'What is the shortest path between Bill Gates and any one of your
alumni?' "
Finding paths through a single database is relatively simple. But it takes a different method to trace links through multiple databases of movie stars, business associations, academic and literary authors, sports leagues, alumni associations, criminal records, Web links, company directories and so on.
In fact, it starts to look like Kleinberg's model, which means his discovery can be used to trace links across disciplines, classes and geography. With more data coming on-line all the time, and better tools to integrate them, it's reasonable to think that computer scientists will soon be able to link Bill Gates to Will Smith to a University of Virginia alumnus to Kleinberg to Robins to my cousin Josh in Cape Breton.
Then I'll give them all copies of this article.
Articles about Robins