Small world phenomenon
|
|
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 psychologist Stanley Milgram which found that two random US citizens were connected by an average 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. Remarkably little research has been done in this area since the publication of the original paper.
| Contents |
Milgram's experiment
The idea is due to Stanley Milgram. It was first published in the popular magazine Psychology Today as "The Small World Problem" in 1967. A "technical report" was published in 1969 which filled in some of the details missing from the original paper.
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 Wichita, Kansas who were asked to forward the letter to the wife of a divinity student living at a specified location in Cambridge, 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 fifty people responded to the challenge, only three letters eventually reached their destination. Milgram's celebrated 1967 paper refers to the fact that one of the letters in this initial experiment reached the recipient in just four days, but neglects to mention the fact 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 a large number of 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 6 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".
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, and a similar exercise has been carried out for the actor Kevin Bacon - the latter effort informing the game "Six Degrees of Kevin Bacon".
Influence
The social sciences
The Tipping Point by Malcolm Gladwell, based on articles originally published in The New Yorker, elaborates the "funneling" concept. In it 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).
Mathematics and other disciplines
In a paper published in the June 4 1998 edition of Nature, Duncan J. Watts and Steven H. Strogatz, then mathematicians at Cornell University, caused a stir by announcing that small world networks are common in a variety of different realms ranging from C. elegans neurons to power grids.
Watts and Strogatz show that the addition of a handful of random links can turn a disconnected network into a highly connected one. This has both positive and negative implications: it is a virtue if, by the addition of a few judicious routers, it makes a vast communication network (such as the Internet) no more than six hops wide; in contrast, it is a vice if it places that same well-connected individual a mere six people away from a deadly disease such as SARS.
The research was 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, in conjunction with his supervisor, 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. [1] (http://www.findarticles.com/cf_0/m1511/12_19/59587202/p6/article.jhtml)
The scale-free network model
After the discovery of Watts and Strogatz, Albert-László Barabási from the Physics Department at the University of Notre Dame was able to find a simpler model for the emergence of the small world phenomenon. While Watts' model was able to explain the high clustering coefficient and the short average path length of a small world, it lacked an explanation for another property found in real-world networks such as the Internet: these networks are scale-free. In simple terms, this means that they contain relatively few highly interconnected super nodes or hubs: the vast majority of nodes are weakly connected, and the connectedness ratio of the nodes remains the same whatever size the network has attained. If a network is scale-free, it is also a small world.
Barabási's scale-free model is strikingly simple, elegant, and intuitive. To produce an artificial scale-free network possessing the small world properties, two basic rules must be followed:
- Growth: the network is seeded with a small number of initial nodes. In every timestep, a new node is added. This new node is connected to m existing nodes.
- Preferential Attachment: the probability of a newly added node connecting to an existing node n depends on the degree of n (number of connections from n to other nodes). The more connections n has, the more likely new nodes will connect to n.
The same mechanisms are at work, for example, in the World Wide Web. The web is in a constant state of growth. New pages are added every second. If a user creates a new webpage, he or she will most likely include links to other well-known pages (hubs).
It appears that the scale-free network model may be the foundation for a law of nature which governs the formation of natural small world networks. Several engineering disciplines have already started to exploit this fact in order to improve existing mechanisms relating to such networks.
Related topics
- Erdős number
- Bacon number
- Duncan J. Watts
- Random network
- Small-world networks
- Social networks
- Scale-free networks
Reference
- Stanley Milgram, "The Small World Problem", Psychology Today, May 1967. pp 60 - 67.
- J. Travers and S. Milgram, "An experimental study of the small world problem", Sociometry 32, 425 (1969).
- D. Watts, S. Strogatz, "Collective dynamics of small-world networks", Nature 393 (1998).
- Jon Kleinberg, "The Small-World Phenomenon: An Algorithmic Perspective", Cornell Computer Science Technical Report 99-1776 (1999)
- Malcolm Gladwell, The Tipping Point, 2000.
- Albert, R., and Barabási, A.-L., "Statistical mechanics of complex networks", Reviews of Modern Physics 7J (January 2002), 47-97.
- Duncan J. Watts, Six Degrees: The Science Of A Connected Age, 2003.
- M. E. J. Newman, "The structure and function of complex networks", SIAM Review, 45:167-256 (2003).
- Mark Buchanan, "Know thy neighbour", New Scientist 181 (2430) (2004): 32
External links
Is it possible that anyone in the world could reach anyone else through a chain of just six friends? There are two projects now testing this hypothesis:
- Small World Project - Columbia University (http://smallworld.columbia.edu/)
- The Electronic Small World Project (http://smallworld.sociology.ohio-state.edu/html/homepage.html)
About small world networks:
- Small-world Networks (http://www.ams.org/new-in-math/small-world.html)
Gladwell's original New Yorker article:
- Six Degrees of Lois Weisberg (http://www.gladwell.com/1999/1999_01_11_a_weisberg.htm)
Could It Be a Big World After All?
- What the Milgram Papers in the Yale Archives Reveal About the Original Small World Study (http://www.columbia.edu/itc/sociology/watts/w3233/client_edit/big_world.html)
Collective dynamics of small-world networks:
- Explaining the "Small World" Phenomenon (http://www.unc.edu/depts/cmse/math/smallworld.html)
Theory tested for specific groups:
- The Oracle of Bacon at Virginia (http://www.cs.virginia.edu/oracle/)
- The Oracle of Baseball (http://www.baseball-reference.com/oracle/)
- The Erdős Number Project (http://www.oakland.edu/enp/)