Jump to content

Small world phenomenon

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Pufferfish101 (talk | contribs) at 19:03, 9 October 2006 (Revert to revision 80204025 dated 2006-10-08 13:28:06 by 68.58.0.158 using popups). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The small world phenomenon (also known as the small world effect) is the hypothesis that everyone in the world can be reached through a short chain of social acquaintances. The concept gave rise to the famous phrase six degrees of separation after a 1967 small world experiment by social psychologist Stanley Milgram which suggested that two random US citizens were connected on average by a chain of six acquaintances.

However, after more than thirty years its status as a description of heterogeneous social networks (such as the aforementioned "everyone in the world") still remains an open question. Little research has been done in this area since the publication of the original paper.

Milgram's experiment

Milgram's original research — conducted among the population at large, rather than the specialized, highly collaborative fields of mathematics and acting (see below) — has been challenged on a number of fronts. In his first "small world" experiment, documented in an undated paper entitled "Results of Communication Project," Milgram sent 60 letters to various recruits in Omaha, Nebraska who were asked to forward the letter to a stockbroker living at a specified location in Sharon, Massachusetts. The participants could only pass the letters (by hand) to personal acquaintances who they thought might be able to reach the target — whether directly or via a "friend of a friend". While 50 people responded to the challenge, only three letters eventually reached their destination. Milgram's celebrated 1967 paper [1] refers to the fact that one of the letters in this initial experiment reached the recipient in just four days, but neglects to mention that only 5% of the letters successfully "connected" to their target. In two subsequent experiments, chain completion was so low that the results were never published. On top of this, researchers have shown that a number of subtle factors can have a profound effect on the results of "small world" experiments. Studies that attempted to connect people of differing races or incomes showed significant asymmetries. Indeed a paper which revealed a completion rate of 13% for black targets and 33% for white targets (despite the fact that the participants did not know the race of the recipient) was co-written by Milgram himself.

Despite these complications, a variety of novel discoveries did emerge from Milgram's research. After numerous refinements of the apparatus (the perceived value of the letter or parcel was a key factor in whether people were motivated to pass it on or not), Milgram was able to achieve completion rates of 35%, and later researchers pushed this as high as 97%. If there was some doubt as to whether the "whole world" was a small world, there was very little doubt that there were many small worlds within that whole (from faculty chains at Michigan State University to a close-knit Jewish community in Montreal). For those chains that did reach completion, the number six emerged as the mean number of intermediaries — and thus the expression "six degrees of separation" (perhaps by analogy to "six degrees of freedom") was born. In addition, Milgram identified a "funneling" effect whereby most of the forwarding (i.e. connecting) was being done by a very small number of "stars" with significantly higher-than-average connectivity: even on the 5% "pilot" study, Milgram noted that "two of the three completed chains went through the same people."

One problem with conducting such a study, however, is that it assumes people in the chain are competent at discovering the connection between two people serving as end points.

Mathematicians and actors

Smaller communities, such as mathematicians and actors, have been found to be densely connected by chains of personal or professional associations. Mathematicians have created the Erdős number to describe their distance from Paul Erdős based on shared publications. A similar exercise has been carried out for the actor Kevin Bacon for actors who appeared in movies together — the latter effort informing the game "Six Degrees of Kevin Bacon". Players of the popular Asian game Go describe their distance from the great player Honinbo Shusaku by counting their Shusaku number, which counts degrees of separation through the games the players have had.

Influence

The social sciences

The Tipping Point by Malcolm Gladwell, based on articles originally published in The New Yorker, elaborates the "funneling" concept. Gladwell argues that the six-degrees phenomenon is dependent on a few extraordinary people ("connectors") with large networks of contacts and friends: these hubs then mediate the connections between the vast majority of otherwise weakly-connected individuals.

Recent work in the effects of the small world phenomenon on disease transmission, however, have indicated that due to the strongly-connected nature of social networks as a whole, removing these hubs from a population usually has little effect on the average path length through the graph (Barrett et al., 2005).

Network models

In 1998, Duncan J. Watts and Steven H. Strogatz, both in the Department of Theoretical and Applied Mechanics at Cornell University, published the first network model on the small-world phenomenon. They showed that networks from both the natural and manmade world, such as the neural network of C. elegans and power grids, exhibit the small-world property. Watts and Strogatz showed that, beginning with a regular lattice, the addition of a small number of random links reduces the diameter — the longest direct path between any two vertices in the network — from being very long to being very short. The research was originally inspired by Watts' efforts to understand the synchronization of cricket chirps, which show a high degree of coordination over long ranges as though the insects are being guided by an invisible conductor. The mathematical model which Watts and Strogatz developed to explain this phenomenon has since been applied in a wide range of different areas. In Watts' words:

"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." [2]

Generally, their model demonstrated the truth in Mark Granovetter's observation that it is "the strength of weak ties" that holds together a social network. Although the specific model has since been generalized by Jon Kleinberg, it remains a canonical case study in the field of complex networks. In network theory, the idea presented in the small-world network model has been explored quite extensively. Indeed, several classic results in random graph theory show that even networks with no real topological structure exhibit the small-world phenomenon, which mathematically is expressed as the diameter of the network growing with the logarithm of the number of nodes (rather than proportional to the number of nodes, as in the case for a lattice). This result similarly maps onto networks with a power-law degree distribution, such as scale-free networks.

In Computer Science, the small-world phenomenon (although it is not typically called that) is used in the development of secure peer-to-peer protocols, novel routing algorithms for the Internet and ad-hoc wireless networks, and search algorithms for communication networks of all kinds.

See also

Is it possible that anyone in the world could reach anyone else through a chain of just six friends? There are three projects now testing this hypothesis:

Gladwell's original New Yorker article:

Could It Be a Big World After All?

Collective dynamics of small-world networks:

Theory tested for specific groups:

Retrieved from "https://en.wikipedia.org/w/index.php?title=Small_world_phenomenon&oldid=80461491"