Case Study 1: The Microsoft Small World Study

Chapter 20 — Six Degrees: How Small-World Networks Open Big Doors

Overview

Stanley Milgram's 1960s chain-letter experiments were ingenious and suggestive — but they were also small, incomplete, and plagued by methodological concerns. For decades, the "six degrees of separation" finding rested on data from a few hundred completed chains out of thousands of attempts, in a single country, in an era before the internet existed.

In 2008, researchers at Microsoft Research closed that gap decisively.

Jure Leskovec (then at Carnegie Mellon, later at Stanford) and Eric Horvitz (at Microsoft Research) published "Planetary-Scale Views on a Large Instant-Messaging Network" — an analysis of 240 million users and 30 billion messages exchanged over the Microsoft Messenger instant messaging service. The dataset was the largest social network ever analyzed at that time. The finding was: average separation across the network was 6.6 hops — remarkably close to Milgram's estimate, achieved through an entirely different method at incomparably greater scale.

This case study examines the study in detail: its methodology, its headline findings, the important nuances in the data, what it tells us about the "six degrees mythology" versus the six degrees reality, and what it implies for understanding luck and opportunity in human networks.

Background: Why the Study Was Possible

The Microsoft Messenger study was possible because Microsoft, in 2006, had one of the world's largest communication platforms. Microsoft Messenger (also known as Windows Live Messenger) was the dominant instant messaging client in much of the world, with hundreds of millions of active users across dozens of countries.

Like all digital communication platforms, it generated logs. Every message sent created a record: sender, recipient, timestamp. These records, properly anonymized and aggregated, constituted a complete map of the communication network — every edge (communication relationship) between every node (user).

This is qualitatively different from Milgram's experiment, which required participants to actively route messages and report their actions. Leskovec and Horvitz had the complete network structure available computationally. They didn't need to ask people to navigate chains — they could calculate every possible chain directly.

The ethical dimensions of using this data are worth noting. Leskovec and Horvitz worked with Microsoft's data governance team and operated under specific constraints on user privacy. They analyzed aggregate network properties rather than individual communication content, and they worked with anonymized user identifiers. The use of proprietary communication data for research raises important questions about consent and privacy that remain contested in the research ethics literature.

The Methodology

The Dataset

The researchers analyzed: - 240 million distinct user accounts that were active on Messenger during the month of June 2006 - 30 billion conversations logged during that period - 180 billion messages total in the system's history

For the network analysis, they constructed a graph where: - Each active user was a node - Two users were connected by an edge if they had exchanged at least one message during the observation period

This produced a massive, real-world social network graph that could be analyzed computationally.

Computing Path Lengths

In a network of 240 million nodes, computing the exact shortest path between every pair of users would require an impractical amount of computation. Leskovec and Horvitz used a combination of exact algorithms (for well-sampled subgraphs) and statistical sampling methods (selecting random pairs of nodes and computing shortest paths for the sample) to estimate the distribution of path lengths across the full network.

This sampling approach introduces some approximation error, but the researchers validated their methods on smaller subgraphs where exact computation was feasible and found the approximations to be reliable.

Accounting for Disconnected Components

A critical analytical step was accounting for the fact that not all users were connected to each other. Any large communication network will have multiple connected components — groups of users who are reachable from each other but not from users in other components. Analyzing path lengths only makes sense within a connected component.

The researchers found that approximately 99.9% of all users who could be reached were within the largest connected component — a massive "giant component" spanning almost the entire active network. But the existence of users outside this component mattered: roughly 48% of all theoretically possible user pairs had no path between them at all (because many users existed in isolated components or had no connections).

The reported average path length of 6.6 hops applies to pairs within the connected portion of the network — not to all possible pairs globally.

The Core Findings

Average Path Length: 6.6 Hops

Within the largest connected component, the average shortest path between two users was 6.6 hops — or about 6.6 degrees of separation.

The distribution was tight: approximately 78% of connected user pairs were within 7 hops of each other, and more than 90% were within 8 hops. The tail of the distribution extended to longer distances, but these were relatively rare.

This finding closely parallels Milgram's estimate of 5.5 to 6 degrees, achieved decades earlier with a fraction of the data. The convergence of the two estimates — using such different methodologies — substantially increases confidence that "six degrees" is a robust feature of large human communication networks, not a methodological artifact of Milgram's specific design.

The Path Length Distribution Was Not Uniform

A finding that often gets lost in the "six degrees" narrative is that the distribution of path lengths, while centered around 6–7, was not uniform. There was substantial variation:

• Some pairs were reachable in 2–3 hops (close network neighbors)
• Most pairs were in the 5–8 hop range
• A small but non-trivial fraction required 9, 10, or more hops
• Geographic and cultural factors substantially affected path length

Geographic and Cultural Distance Affects Path Length

Leskovec and Horvitz found that pairs within the same country had shorter average path lengths than cross-national pairs. Cross-continental pairs had longer average path lengths than within-continent pairs. This makes intuitive sense: social networks have geographic clustering, and cross-cluster bridges are more sparse across larger geographic and cultural divides.

The practical implication: "six degrees" is a better approximation for within-country or within-culture connections than for globally diverse pairs. Someone trying to reach a hiring manager in their own city is working with a shorter average chain than someone trying to reach a contact in a different country and industry.

The Role of Hubs

The researchers also examined the distribution of node degrees (number of connections per user). The distribution was highly skewed — following approximately a power law, consistent with Barabási and Albert's preferential attachment model. A small number of users had thousands of connections; most had a handful.

When Leskovec and Horvitz analyzed which nodes appeared most frequently in shortest-path chains, they found a predictable result: highly connected users (hubs) appeared disproportionately in the paths between disconnected pairs. Just as Milgram's chains converged on the Boston clothing merchant, shortest paths in the Messenger network converged on hub users.

This confirms the mathematical relationship between hub structure and small-world path length: hubs are the structural source of the short paths. Remove the hubs and the network's average path length would increase dramatically.

What This Tells Us About "Six Degrees" as Mythology vs. Reality

The phrase "six degrees of separation" has become so well-known that it has taken on mythological status — a simple, clean fact about the social world. The Microsoft study (and the careful analysis of Milgram's original work) reveals a more nuanced reality:

What Is True

• Large human communication networks have short average path lengths — in the range of 6–7 hops for connected pairs.
• This property emerges from the combination of local clustering and long-range bridges that Watts and Strogatz identified mathematically.
• The finding is robust across different methodologies and data sources.
• Hubs disproportionately mediate shortest paths.

What Is Oversimplified

• "Six degrees" applies only to pairs within the connected portion of the network. Roughly half of all user pairs in the Messenger network had no path between them.
• The average path length of 6.6 is a distribution, not a guarantee. Some pairs are much farther apart; cross-cultural and cross-geographic paths tend to be longer.
• Topological path length (the path that exists in the network) is not the same as navigational path length (the path you can find without a complete network map). The Microsoft study computed topological paths; real-world chain traversal (like Milgram's experiment, or Priya's LinkedIn navigation) is navigational.
• The short paths that exist are not equally accessible to everyone. Hub access is itself distributed unequally — connected to the structural luck dynamics of Chapter 18.

The Navigability Problem: A Separate Question

The Microsoft study answers the topological question: how short are the paths that exist? But it leaves open the navigational question: can people find those paths without a complete map?

This is where Milgram's experiment provides a different kind of evidence. Milgram wasn't just showing that short paths exist — he was showing that people can navigate toward a target using only local information (who they know and a description of the target). The fact that chains were completed at all demonstrates human navigational capability.

Jon Kleinberg's theoretical work (discussed in the chapter) formalized the conditions under which decentralized navigation can efficiently find short paths. The Messenger study shows the topological structure is right; Kleinberg's theory specifies the conditions under which that structure is navigable; Milgram's experiments provide empirical evidence that it sometimes is.

The practical takeaway for Priya: the path exists (Microsoft/Kleinberg tell us). The question is whether she can find and traverse it efficiently. LinkedIn's connection visualization makes this much easier than in Milgram's era — the topological path is visible, which dramatically reduces the navigational challenge.

Implications for Luck and Opportunity

The Microsoft study has several specific implications for understanding how luck operates through networks:

First: The paths are there even when you can't see them. One of the most common experiences of job-seeking is the feeling of isolation — of throwing applications into a void. The Messenger study's finding suggests that this feeling is topologically wrong. You are almost certainly within 6–7 hops of virtually every professional in your country, and probably within 3–4 hops of almost everyone in your industry. The paths exist. The luck is in finding them.

Second: Hubs are the key. The disproportionate role of hubs in shortest paths suggests that knowing even one well-connected person in a target industry can dramatically reduce your effective distance from the people in that industry. Building one genuine relationship with a hub is worth more, in network terms, than building twenty relationships with regular nodes.

Third: Geographic clustering matters. The study's finding that within-country paths are shorter than cross-country paths is relevant to job-seekers who are targeting employers in geographically concentrated industries. Being geographically close to industry clusters (Silicon Valley for tech, New York for finance and media) provides a structural luck advantage — shorter network paths to the people who make decisions.

Fourth: Disconnected components are a real risk. The finding that ~48% of user pairs were unconnected is a reminder that small-world dynamics don't apply universally. People whose networks are entirely within a single isolated community — whether geographic, cultural, or socioeconomic — may be genuinely more distant from key opportunity nodes than the six-degree average suggests. This is another form of structural luck: not being in the connected component that contains the opportunities you want.

Methodological Notes and Limitations

Sampling validity: The Messenger dataset was large, but it represented users of a specific platform (biased toward Windows users; concentrated in certain countries; more common among certain age groups) rather than the global population. The path length findings may not generalize perfectly to all human networks.

Activity thresholds: The analysis defined edges as pairs who had exchanged at least one message. The inclusion of single-message exchanges may inflate connectivity compared to a network defined by genuine ongoing relationships.

Temporal snapshot: The data represents a single month (June 2006). Network structure changes over time as relationships form and dissolve. The path lengths may differ in a network analyzed in a different period.

Privacy and consent: The use of proprietary communication data for research without explicit user consent is a methodological and ethical issue that the research community continues to debate.

None of these limitations overturn the headline finding — which is convergent with multiple other analyses — but they appropriately qualify the precision and generalizability of the specific numbers.

Key Figures

• 240 million users analyzed
• 30 billion conversations logged
• 6.6 hops average separation within connected component
• 78% of connected pairs within 7 hops
• 48% of all possible user pairs with no path between them

Discussion Questions

1. The study found that ~48% of user pairs had no path between them. What does this imply for the "six degrees" narrative? Who is most likely to be in disconnected components, and what does this tell us about the relationship between network connectivity and structural luck?

2. The study used proprietary corporate data without explicit participant consent. How should the research ethics of this choice be evaluated? What principles would you apply to decide when corporate data can legitimately be used for social research?

3. Geographic clustering produces longer average path lengths across cultural and national lines. What are the practical implications for someone in a smaller country or a geographically isolated region trying to access global professional networks?

4. If you could identify a hub in your own network — someone with vastly more connections than average across multiple clusters — what would your strategy be for building a genuine relationship with them? What can you offer? What would you ask for, and how would you ask it?

5. The Microsoft Messenger network existed in 2006. How do you think the average path length would differ if a similar analysis were conducted today on a combined graph of WhatsApp, Instagram, LinkedIn, and Twitter/X connections? What specific features of modern social media would increase or decrease average path length?