ArticleslgStudy

computer science

Small-world experiment

Small-world experiment is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Small-world experiment rather than just read about it. In short: The small-world experiment comprised several experiments conducted by Stanley Milgram and other researchers examining the average path length for social networks of people in the United States. The research was groundbreaking in that it suggested that human society is a small-world-type network characterized by short path-lengths.

Small-world experiment — main illustration
Small-world experiment — illustration

Key takeaways

  • Small-world experiment belongs to computer science; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Small-world experiment to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Small-world experiment from memory before moving on to harder problems.

Reference excerpt

The small-world experiment comprised several experiments conducted by Stanley Milgram and other researchers examining the average path length for social networks of people in the United States. The research was groundbreaking in that it suggested that human society is a small-world-type network characterized by short path-lengths. The experiments are often associated with the phrase "six degrees of separation", although Milgram did not use this term himself.

Historical context of the small-world problem Guglielmo Marconi's conjectures based on his radio work in the early 20th century, which were articulated in his 1909 Nobel Prize address, may have inspired Hungarian author Frigyes Karinthy to write a challenge to find another person to whom he could not be connected through at most five people. This is perhaps the earliest reference to the concept of six degrees of separation, and the search for an answer to 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.

The experiment Milgram's experiment developed out of a desire to learn more about the probability that two randomly selected people would know each other. This is one way of looking at the small world problem. An alternative view of the problem is to imagine the population as a social network and attempt to find the average path length between any two nodes. Milgram's experiment was designed to measure these path lengths by developing a procedure to count the number of ties between any two people.

Basic procedure

… excerpt ends here. Continue reading the full article.

Illustrations

Small-world experiment: Milgram concluded from his small-world experiments that any two random people in the United States would be linked by a chain of (on average) six steps.
Milgram concluded from his small-world experiments that any two random people in the United States would be linked by a chain of (on average) six steps.
Small-world experiment: One possible path of a message in the "Small World" experiment by Stanley Milgram
One possible path of a message in the "Small World" experiment by Stanley Milgram
Small-world experiment: Comparison of Watts-Strogatz graphs with different randomization probability. A regular ring graph (left), a small-world graph with some edges randomly rewired (center), and a random graph with all edges randomly rewired (right).
Comparison of Watts-Strogatz graphs with different randomization probability. A regular ring graph (left), a small-world graph with some edges randomly rewired (center), and a random graph with all edges randomly rewired (right).

Worked examples

Example 1 — a first encounter with Small-world experiment

Start with the simplest possible case. Write down what Small-world experiment claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Small-world experiment before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Small-world experiment ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Small-world experiment

In research
Small-world experiment appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Small-world experiment in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Small-world experiment is common in secondary-school and first-year university syllabi. It links to neighbouring topics Community building, Psychology experiments, Social network analysis, so understanding it makes those chapters shorter.
In everyday life
Look for Small-world experiment outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Small-world experiment in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Small-world experiment means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Small-world experiment out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Small-world experiment in simple terms?

The small-world experiment comprised several experiments conducted by Stanley Milgram and other researchers examining the average path length for social networks of people in the United States. The research was groundbreaking in that it suggested that human society is a small-world-type network cha…

Why does Small-world experiment matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Small-world experiment?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Small-world experiment.

Tags

  • Community building
  • Psychology experiments
  • Social network analysis

Keep exploring