Small World Graphs Revisited

Main Menu           Previous Topic                                                           Next Topic

Finding Short Paths Between Agents

We return, for a moment, to Stanley Milgram's famous chain letter experiment. While we may be surprised just to learn that there exist short paths linking random people, Milgram's experiment actually shows a stronger result. Namely, not only do short paths exist, but agents are able to find these short paths without knowing the entire structure of the graph.

In "The Small World Phenomenon: An Algorithmic Perspective," Jon Kleinberg takes up the question of why random pairs of strangers can find short chains of aquaintances linking each other. Kleinberg shows that, given only the local information of their own connections, agents in the Watts small world graph are unable to find such short chains using any local algorithm. Rather, Kleinberg asserts, it is necessary that the network have some structure both in its short range contacts and in its long range contacts.

Kleinberg creates a model in which agents on a lattice know their nearby contacts and one distant contact, but the probability of choosing a distant contact at a certain distance decreases with the square of that distance. He shows that with this added structure, agents are capable of finding short paths to random agents.

The implication of Kleinberg's study is that the real social world may exibit more structure than our model implies. In order for short paths to exist, a graph only needs completely random long range connections. However, the ability of people to find these short paths may indicate that long range contacts follow some structural law of their own.

                   Previous Slide                                                           Next Slide