Introduction

Main Menu           Previous Topic                                                           Next Topic

Isolating the Small World Problem

We now isolate exactly what it is that constitutes the Small World Problem. Rather than just considering people living on Earth, we move to a more abstract realm by considering any set of "agents" in a graph which share symmetric "connections." (In Milgram's experiment, the agents represent people and the connections represent social connections.)

Why exactly should we be surprised to discover short paths of connections between random agents in a graph? Watts presents four properties of a graph that together lead us to expect not to find such short path lengths:

1. The graph has a large population (N >> 1).
   
2. The graph is sparse: Each agent is only connected to a small number of other agents.
   
3. The network is decentralized: There is no central agent having connections to most other agents (further, the maximum number of connections an agent can have is small compared to N).
   
4. The network is highly clustered: Agents that are connected share many mutual connections.

The world's population seems to fulfill all four of these conditions. There are billions of people on the planet. People generally cannot know more than a few thousand aquaintances, and there is no central person everybody knows. Finally, friendship circles are highly overlapping -- that is, connected people have similar sets of aquaintances.

With all four of these conditions, we intuitively expect that randomly selected agents share no aquaintances in common and that there is no short path between them. How then can we explain the fact that Milgram seemingly discovered short paths between random people? This is the essence of the Small World Problem.

                   Previous Slide                                                           Next Slide