Historical context of the small-world problem
Mathematician Manfred Kochen and political scientist Ithiel de Sola Pool wrote a mathematical manuscript, "Contacts and Influences", while working at the University of Paris in the early 1950s, during a time when Milgram visited and collaborated in their research. Their unpublished manuscript circulated among academics for over 20 years before publication in 1978. It formally articulated the mechanics of social networks, and explored the mathematical consequences of these (including the degree of connectedness). The manuscript left many significant questions about networks unresolved, and one of these was the number of degrees of separation in actual social networks.
Milgram took up the challenge on his return from Paris, leading to the experiments reported in "The Small World Problem" in the May 1967 (charter) issue of the popular magazine Psychology Today, with a more rigorous version of the paper appearing in Sociometry two years later. The Psychology Today article generated enormous publicity for the experiments, which are well known today, long after much of the formative work has been forgotten.
Milgram's experiment was conceived in an era when a number of independent threads were converging on the idea that the world is becoming increasingly interconnected. Michael Gurevich had conducted seminal work in his empirical study of the structure of social networks in his MIT doctoral dissertation under Pool. Mathematician Manfred Kochen, an Austrian who had been involved in statist urban design, extrapolated these empirical results in a mathematical manuscript, Contacts and Influences, concluding that, in an American-sized population without social structure, "it is practically certain that any two individuals can contact one another by means of at least two intermediaries. In a [socially] structured population it is less likely but still seems probable. And perhaps for the whole world's population, probably only one more bridging individual should be needed." They subsequently constructed Monte Carlo simulations based on Gurevich's data, which recognized that both weak and strong acquaintance links are needed to model social structure. The simulations, running on the slower computers of 1973, were limited, but still were able to predict that a more realistic three degrees of separation existed across the U.S. population, a value that foreshadowed the findings of Milgram.
Milgram revisited Gurevich's experiments in acquaintanceship networks when he conducted a highly publicized set of experiments beginning in 1967 at Harvard University. One of Milgram's most famous works is a study of obedience and authority, which is widely known as the Milgram Experiment. Milgram's earlier association with Pool and Kochen was the likely source of his interest in the increasing interconnectedness among human beings. Gurevich's interviews served as a basis for his small world experiments.
Milgram sought to develop an experiment that could answer the small world problem. This was the same phenomenon articulated by the writer Frigyes Karinthy in the 1920s while documenting a widely circulated belief in Budapest that individuals were separated by six degrees of social contact. This observation, in turn, was loosely based on the seminal demographic work of the Statists who were so influential in the design of Eastern European cities during that period. Mathematician Benoit Mandelbrot, born in Poland and having traveled extensively in Eastern Europe, was aware of the Statist rules of thumb, and was also a colleague of Pool, Kochen and Milgram at the University of Paris during the early 1950s (Kochen brought Mandelbrot to work at the Institute for Advanced Study and later IBM in the U.S.). This circle of researchers was fascinated by the interconnectedness and "social capital" of social networks.
Milgram's study results showed that people in the United States seemed to be connected by approximately three friendship links, on average, without speculating on global linkages; he never actually used the phrase "six degrees of separation". Since the Psychology Today article gave the experiments wide publicity, Milgram, Kochen, and Karinthy all had been incorrectly attributed as the origin of the notion of "six degrees"; the most likely popularizer of the phrase "six degrees of separation" is John Guare, who attributed the value "six" to Marconi.
Information packets were initially sent to "randomly" selected individuals in Omaha or Wichita. They included letters, which detailed the study's purpose, and basic information about a target contact person in Boston. It additionally contained a roster on which they could write their own name, as well as business reply cards that were pre-addressed to Harvard.
Upon receiving the invitation to participate, the recipient was asked whether he or she personally knew the contact person described in the letter. If so, the person was to forward the letter directly to that person. For the purposes of this study, knowing someone "personally" was defined as knowing them on a first-name basis.
In the more likely case that the person did not personally know the target, then the person was to think of a friend or relative who was more likely to know the target. They were then directed to sign their name on the roster and forward the packet to that person. A postcard was also mailed to the researchers at Harvard so that they could track the chain's progression toward the target.
When and if the package eventually reached the contact person in Boston, the researchers could examine the roster to count the number of times it had been forwarded from person to person. Additionally, for packages that never reached the destination, the incoming postcards helped identify the break point in the chain.
Judith Kleinfeld argues that Milgram's study suffers from selection and non-response bias due to the way participants were recruited and high non-completion rates. First, the "starters" were not chosen at random, as they were recruited through an advertisement that specifically sought people who considered themselves well-connected. Another problem has to do with the attrition rate. If one assumes a constant portion of non-response for each person in the chain, longer chains will be under-represented because it is more likely that they will encounter an unwilling participant. Hence, Milgram's experiment should underestimate the true average path length. Several methods have been suggested to correct these estimates; one uses a variant of survival analysis in order to account for the length information of interrupted chains, and thus reduce the bias in the estimation of average degrees of separation.
One of the key features of Milgram's methodology is that participants are asked to choose the person they know who is most likely to know the target individual. But in many cases, the participant may be unsure which of their friends is the most likely to know the target. Thus, since the participants of the Milgram experiment do not have a topological map of the social network, they might actually be sending the package further away from the target rather than sending it along the shortest path. This is very likely to increase route length, overestimating the average number of ties needed to connect two random people. An omniscient path-planner, having access to the complete social graph of the country, would be able to choose a shortest path that is, in general, shorter than the path produced by the greedy algorithm that makes local decisions only.
A description of heterogeneous social networks still remains an open question. Though much research was not done for a number of years, in 1998 Duncan Watts and Steven Strogatz published a breakthrough paper in the journal Nature. Mark Buchanan said, "Their paper touched off a storm of further work across many fields of science" (Nexus, p60, 2002). See Watts' book on the topic: Six Degrees: The Science of a Connected Age.
Some communities, such as the Sentinelese, are completely isolated, disrupting the otherwise global chains. Once these people are discovered, they remain more "distant" from the vast majority of the world, as they have few economic, familial, or social contacts with the world at large; before they are discovered, they are not within any degree of separation from the rest of the population. However, these populations are invariably tiny, rendering them of low statistical significance.In addition to these methodological criticisms, conceptual issues are debated. One regards the social relevance of indirect contact chains of different degrees of separation. Much formal and empirical work focuses on diffusion processes, but the literature on the small-world problem also often illustrates the relevance of the research using an example (similar to Milgram's experiment) of a targeted search in which a starting person tries to obtain some kind of resource (e.g., information) from a target person, using a number of intermediaries to reach that target person. However, there is little empirical research showing that indirect channels with a length of about six degrees of separation are actually used for such directed search, or that such search processes are more efficient compared to other means (e.g., finding information in a directory).
The social sciences
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).
Mathematicians and actors
Current research on the small-world problem
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.
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.