The Small-World Phenomenon.
A social network exhibits the small-world phenomenon if, roughly speaking, any two individuals in the network are likely to be connected through a short sequence of intermediate acquaintances.
This has long been the subject of anecdotal observation and folklore; often we meet a stranger and discover that we have an acquaintance in common.
It has since grown into a signicant area of study in the social sciences, in large part through a series of striking experiments conducted by Stanley Milgram and his co-workers in the 1960's. Recent work has suggested that the phenomenon is pervasive in networks arising in nature and technology, and a fundamental ingredient in the structural evolution of the World Wide Web.
Milgram's basic small-world experiment remains one of the most compelling ways to think about the problem. The goal of the experiment was to nd short chains of acquaintances linking pairs of people in the United States who did not know one another.
In a typical instance of the experiment, a source person in Nebraska would be given a letter to deliver to
a target person in Massachusetts. The source would initially be told basic information about the target, including his address and occupation; the source would then be instructed to send the letter to someone she knew on a rst-name basis in an eort to transmit the letter to the target as ecaciously as possible.
Anyone subsequently receiving the letter would be given the same instructions, and the chain of communication would continue until the target was reached.
Over many trials, the average number of intermediate steps in a successful chain was found to lie between ve and six, a quantity that has since entered popular culture as the "six degrees of separation" principle.
