The idea of six degrees of separation—that is, that every person in the world is no more than six people away from every other person on earth—has fascinated social scientists and laymen alike ever since Hungarian writer Frigyes Karinthy introduced the concept in 1929.
For the greater public, the cultural touchstone of the theory was the 1990 play entitled Six Degrees of Separation by John Guare. Although the drama was not an exploration of the phenomenon by any means, it spawned countless versions of parlor games. For scientists, however, the wellspring of the six degrees phenomenon, also called the small-world problem, was a 1967 study undertaken by social psychologist Stanley Milgram, in which a selected group of volunteers in the Midwestern U.S. were instructed to forward messages to a target person in Boston. Milgram’s results, published in Psychology Today in 1967, were that the messages were delivered by “chains” that comprised anywhere between two and 10 intermediaries, with the mean being five.
In the ensuing years, the problem has become a perennial favorite among researchers of many disciplines, from computer scientists exploring probabilistic algorithms for best use of network resources to epidemiologists exploring the interplay of infectious diseases and network theory.
Most recently, the vast architectural resources of Facebook and Twitter have supplied researchers with something they never possessed before—the capability to look at the small-world problem from both the traditional algorithmic approach, which explores the probabilities of how each person (or network node) in a chain seeks out the next messenger using only the limited local knowledge they possess, and the new topological approach, which can examine the entire structure of a network as it also observes the progression of the algorithmic chains.
“It’s amazing how far we’ve come,” says Duncan Watts, a founding partner at Microsoft Research New York City, who was until recently a senior researcher at Yahoo! Watts is one of the world’s leading authorities on the small-world problem, dating to the publication of “Collective Dynamics of ‘Small-world’ Networks,” co-authored with Steven Strogatz, in Nature in 1998. At that time, Watts says, the largest available network, actors listed in the Internet Movie Database, contained about 225,000 edge nodes (individual actors). A recent study by researchers from Facebook and the University of Milan, however, looked at 721 million Facebook users, who had 69 billion unique friendships among them, and revealed an average of 3.74 intermediaries between a source and target user, suggesting an even smaller world than Milgram’s original study showed.
“In fact, the whole motivation of the thing I did with Strogatz was precisely that you couldn’t do the exercise Facebook just did,” Watts says. “Now the empirical exercise is possible. That’s a remarkable change.”
A Similarity of Results
One must consider the large variety of online communities and compare the small-world experiments performed on them to Milgram’s method—sending a message via terrestrial delivery routes—in order to fully appreciate the similarity of results across the board. While the Facebook experiment yielded approximately four degrees of separation, work by distinguished scientist Eric Horvitz of Microsoft Research and Stanford University assistant professor Jure Leskovec, on connections between users of the Microsoft Instant Messaging network, yielded an average 6.6 degrees of separation between any two users. In their 2009 paper “Social Search in ‘Small-world’ Experiments” examining the algorithmic approach, Watts, Sharad Goel, and Roby Muhamad discovered that roughly half of all chains can be completed in six or seven steps, “thus supporting the ‘six degrees of separation’ assertion,” they wrote, “but on the other hand, estimates of the mean are much longer, suggesting that for at least some of the population, the world is not ‘small’ in the algorithmic sense.”
One ironic factor in examining the small-world problem as online communities grow ever larger is that the experiments’ attrition rates are also vastly greater than in the past.
Discovering the reason why “the world is not ‘small’ in the algorithmic sense” presents a wide swath of fertile ground for those researchers, including Watts and Leskovec, who are still plumbing the many vectors of network navigation.
One ironic, or counterintuitive, factor in examining the small-world problem as online communities grow ever larger is that the experiments’ attrition rates are also vastly greater than in the past. For instance, Watts says only 12% of those who signed up for a joint small-world experiment at Yahoo! and Facebook completed their chains, compared with 75% of those who participated in Milgram’s experiment and the 35% who completed chains in a 20012002 experiment run by Watts.
However, Watts says the data they have should allow them to still answer the questions they care about most, which is exploring the efficiency of intermediary connections selected.
“We know how far you are from the target, Facebook knows how far your friends are from the target, and we know who you picked, so we can establish whether you made the right choice,” Watts says. “So we can get the most science out of it, it’s just a little bummer that the attrition was so bad.”
The logic behind finding the most efficient paths may produce payoffs unforeseen for both theoretical modeling and production networks such as search engine optimization. Finding the best ways to determine those paths, though, will necessitate a leap from the known models of small-world networks to a better understanding of the intermediary steps between any two endpoints of a chain.
Leskovec says, given constants from graph theory, the diameter of any given network will grow logarithmically with its size; that is, the difference between five and six degrees of separation mandates a graph an order of magnitude larger or denser. Jon Kleinberg, Tisch University professor in the department of computer science at Cornell University, whose “The Small-World Phenomenon: An Algorithmic Perspective” is regarded as one of the problem’s seminal modeling documents, says this basic property is precisely what makes the small-world theory so appealing while also presenting the research community the greatest challenge inherent in it.
“It’s something that still feels counterintuitive when you first encounter it,” Kleinberg says. “It makes sense in the end: I know 1,000 people and my friend knows 1,000 people—and you don’t have to multiply 1,000 by itself too many times for it to make sense.”
However, this logarithmic progression also precludes the ability to examine or design intermediate levels of scale, Kleinberg says. “We thought the right definition of distance was going to be ‘Here I am, and how many steps do I have to go to get to you?’ but that turns out not to be. We need some other measure and I think that remains an interesting open question, that people are actively looking at: Is there some kind of smoother scale here? Who are the 10,000 people closest to me? The 100,000?
“What is the right definition of distance when you’re looking at social networks?” asks Jon Kleinberg. “It’s not just how many steps I have to go.”
“We need a much more subtle way to do that and it is going to require some sophisticated mathematical ideas and sophisticated combinational ideas—what is the right definition of distance when you’re looking at social networks? It’s not just how many steps I have to go. That’s an important question in everyday life and when you’re designing some online system.”
Mozart Meets The Terminator
Recent research is beginning to use the short-path principles of social search in the online systems discussed by Kleinberg. In “Degrees of Separation in Social Networks,” presented at the Fourth International Symposium on Combinatorial Search 2011, researchers from Shiraz University, Carnegie Mellon University, and the University of Alberta designed a search algorithm, tested on Twitter, intended for uses beyond social search.
For example, they reported in Voice over Internet Protocol (VoIP) networks, when a user calls another user in the network, he or she is first connected to a VoIP carrier, a main node in the network. The VoIP carrier connects the call to the destination either directly or, more commonly, through another VoIP carrier.
“The length of the path from the caller to the receiver is important since it affects both the quality and price of the call,” the researchers noted. “The algorithms that are developed in this paper can be used to find a short path (fewest carriers) between the initial (sender) and the goal (receiver) nodes in the network.”
These algorithms, such as greedy algorithms enhanced by geographic heuristics, or probabalistic bidirectional methods, have the potential to cut some of the overhead, and cost, of network search sessions such as the sample VoIP session, the authors believe.
Leskovec’s most recent work based on small-world algorithms explores the paths that humans take in connecting concepts that, on the surface, seem rather disparate, such as Wolfgang Amadeus Mozart and the Terminator character from the science-fiction films starring Arnold Schwarzenegger.
“As a human, I sort of know how the knowledge fits together,” Leskovec says. “If I want to go from Mozart to Terminator and I know Mozart was from Austria and Schwarzenegger was from Austria, maybe I can go through the Austrian connection. A computer that is truly decentralized has no clue, it has no conception that getting to Schwarzenegger is good enough.”
Interestingly enough, Leskovec says, computers fared better than humans on average on solving such search chains, but humans also were less likely to get totally lost and were capable of forming backup plans, which the Web-crawling agents could not do. Effectively, he says, the payoff of such research is “understanding how humans do this, what kind of cues are we using, and how to make the cues more efficient or help us recognize them, to help us understand where we are, right now, in this global network.”
Further Reading
Backstrom, L., Boldi, P., Rosa, M., Ugander, J., and Vigna, S.
Four degrees of separation, http://arxiv.org/abs/1111.4570, Jan. 6, 2012.
Bakhshandeh, R., Samadi, M., Azimifar, Z., and Schaeffer, J.
Degrees of separation in social networks, Proceedings of the Fourth International Symposium on Combinatorial Search, Barcelona, Spain, July 1516, 2011.
Goel, S., Muhamad, R., and Watts, D.
Social search in “small-world” experiments, 18th International World Wide Web Conference, Madrid, Spain, April 2024, 2009.
Kleinberg, J.
The small-world phenomenon: an algorithmic perspective, 32nd ACM Symposium on Theory of Computing, Portland, OR, May 2123, 2000.
West, R., and Leskovec, J.
Human wayfinding in information networks, 22nd International World Wide Web Conference, Lyon, France, April 1620, 2012.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment