TU Graz: Course: 707.000 Web Science and Web Technology: Lecture 2: Small World Problem

Markus StrohmaierEdShare 2008

Abstract

This paper examines the "Small World Problem," a foundational concept in social network analysis and web science. Drawing from the second lecture of the "Web Science and Web Technology" course at TU Graz, we explore how any two individuals in a global population are often connected by surprisingly short chains of acquaintances. We discuss landmark empirical studies, such as Milgram's 1969 experiment, and theoretical frameworks like Granovetter’s "Strength of Weak Ties." Furthermore, we look at modern computational examples like the Bacon Number and the structural properties of scale-free networks, providing a comprehensive overview of how social interconnectedness shapes information flow and network resilience.

Introduction: The Small World Phenomenon

The "Small World" phenomenon is a pervasive social intuition—the feeling that the world is smaller than its billions of inhabitants suggest. Scientifically, this addresses a core question of social interconnectedness: what is the probability that any two people, chosen at random, are linked through a short chain of mutual acquaintances? This lecture moves beyond the cliché of "six degrees of separation" to investigate the mechanics of network formation, the role of specific link types, and the mathematical models that describe these complex systems.

Empirical Foundations: The Milgram Experiment

The most famous empirical test of the small world hypothesis was conducted by Jeffrey Travers and Stanley Milgram in 1969. In this study, "starters" in Nebraska and Boston were tasked with sending a folder to a specific "target"—a stockbroker in Boston. The catch was that participants could only pass the folder to a personal acquaintance whom they believed might be closer to the target.

Milgram’s results provided the first quantitative evidence for the "six degrees" theory. Among the chains that successfully reached the target, the average number of intermediaries was between 5.2 and 6.1. Interestingly, the study revealed "chain convergence": as the folders neared the target, they often passed through the same few "super-connectors." For instance, 25% of all completed chains reached the target through a single specific neighbor of the target.

Modern Social Networks

Today, social software like LinkedIn, XING, and Facebook provides a digital laboratory for observing these connections in real-time. These platforms explicitly map the "path" between users, demonstrating the practical reality of the small world problem in professional and personal contexts.

A screenshot from the XING platform illustrating a multi-step connection path between two users, visualizing the small world concept in a modern social network.

The Strength of Weak Ties

A critical insight in network theory is Mark Granovetter’s "The Strength of Weak Ties" (1973). Granovetter argued that while our "strong ties" (close friends and family) are emotionally significant, they often belong to the same insular social circles we do. Consequently, information within these cliques is often redundant.

In contrast, "weak ties" (acquaintances) often act as "bridges" to different social clusters. Because they connect otherwise disconnected groups, weak ties are disproportionately important for the diffusion of new information, such as job opportunities or novel ideas. This "paradox of weak ties" suggests that a network's global connectivity depends more on its casual acquaintances than its tight-knit friendships.

Computational Examples: Bacon and Erdös Numbers

The small world property is not limited to general social interactions but appears in specialized professional networks as well. Two prominent examples include:

  • The Bacon Number: Using the IMDb database, researchers calculate the distance between any actor and Kevin Bacon based on shared movie appearances. Data shows that the vast majority of the over 500,000 actors in the database have a Bacon number of 3 or less.
  • The Erdös Number: Similarly, mathematicians track their "distance" from the prolific Paul Erdös based on co-authorship of academic papers, based on approximately 1,500 publications.
The "Kevin Bacon Game" board game, which popularized the concept of calculating degrees of separation within the film industry.

Network Dynamics and Resilience

Why do these short paths exist? One explanation is "Preferential Attachment," a model popularized by Barabási and Albert. In many growing networks, new nodes are more likely to connect to existing "hubs"—nodes that already have many connections. This "rich-get-richer" dynamic leads to a scale-free architecture characterized by a few highly connected hubs and many sparsely connected nodes.

This structure has profound implications for network resilience. Small-world networks are remarkably robust against random failures; if a random individual leaves the network, the overall connectivity usually remains intact. However, they are highly vulnerable to targeted attacks on hubs. Removing just a few key "connectors" can cause the entire global network to fragment into isolated islands.

Furthermore, social networks often exhibit "Assortative Mixing" or homophily, where individuals tend to associate with others who share similar characteristics. This contrasts with many technological networks, like the Web, which often show "Disassortative Mixing," where low-degree nodes are more likely to link to high-degree hubs.

Limitations and Conclusion

While the small world theory is compelling, it faces several academic critiques. Milgram’s original study suffered from high attrition; only 29% (64 of 296) of chains were completed. It remains unclear if the failed chains represent non-existent paths or simply a lack of participant motivation. Additionally, status bias may play a role, as targets are often high-status individuals who are naturally easier to reach.

Despite these caveats, the study of the small world problem serves as a gateway to more rigorous network science, involving the analysis of degree distributions and clustering coefficients. Understanding these patterns is essential for navigating the interconnected landscape of modern web science and technology.

Summary updated

Abstract

We will discuss several examples and research efforts related to the small world problem and set the ground for our discussion of network theory and social network analysis.
\n
\nReadings: An Experimental Study of the Small World Problem, J. Travers and S. Milgram Sociometry 32 425-443 (1969) [Protected Access] 
\nOptional: The Strength of Weak Ties, M.S. Granovetter The American Journal of Sociology 78 1360--1380 (1973) [Protected Access]
\nOptional: Worldwide Buzz: Planetary-Scale Views on an Instant-Messaging Network, J. Leskovec and E. Horvitz MSR-TR-2006-186. Microsoft Research, June 2007. [Web Link, the most recent and comprehensive study on the subject!]
\n
\nOriginally from: http://kmi.tugraz.at/staff/markus/courses/SS2008/707.000_web-science/
\n
\n
BibTeX
@inproceedings{strohmaier2008tu,
  author = {Markus Strohmaier},
  title = {{TU Graz: Course: 707.000 Web Science and Web Technology: Lecture 2: Small World Problem}},
  booktitle = {EdShare},
  year = {2008},
}
Figure