Introduction

In 1967, the sociologist Stanley Milgram published results of a letter-relaying experiment of his design. The now-famous experiment required a source individual to forward a letter to a destination individual, about whom was disclosed information such as address, name and profession. However, each source individual was forbidden to post the letter directly to the target person. Instead she was required to forward the letter to someone known on a first-name basis, who in turn was allowed to forward it only to such familiar contacts.

The outcome was that a significant fraction of letters reached their destinations. Moreover, they did so in at most six hops, justifying the term “six degrees of separation”. This observation is also often referred to as the “small-world phenomenon”. The problem, formulated in the social sciences, is highly relevant in many other settings, namely routing with limited information in communication networks and browsing behaviour on the World Wide Web.

Viewing the social world as a graph with edges between acquainted persons, if any individual can relay information to any other in a small number of hops as in Milgram's experiment, the corresponding graph must have a small diameter. As we saw in Chapter 4, the E-R graph does have a small diameter (logarithmic in the number of nodes).