Creating a Small World Graph

Main Menu           Previous Topic                                                           Next Topic

A Refined Definition of Small World

With our new measures, we are prepared to refine what we mean by a small world graph. As we saw, a caveman graph has a high characteristic path length and a high clustering coefficient, while a random graph has a low characteristic path length and a low clustering coefficient. Though these are only two extreme examples, we might begin to suspect that as path length increases, so does clustering, and vice-versa.

But what about the real world? As we've said, in our social networks, we tend to know the same people that our friends do. Thus, we expect the clustering coefficient to be high. At the same time, if it is true that short chains exist between random people, then the characteristic path length is low. This is what we really mean by a small world graph.

A small world graph is a graph exhibiting a high clustering coefficient, but low characteristic path length.

As of today, the data on the real social world is rather incomplete, so it is difficult to draw definite conclusions from it. However, there are other real world networks that satisfy this new definition of small world graphs. Watts examines three different real world networks: The United States power grid, the neural network of the nematode, C. elegans, and the collaboration grid of film actors. He discovers that each of these graphs is a small world network, perhaps suggesting that small world graphs are more common that one might suspect. That each of these very different graphs satisfies the small world graph requirement is both surprising and fascinating -- for a full discussion please refer back to the original paper.

We continue by asking what it is about the underlying structure that makes a graph small world. Furthermore, by what process can we create a small world graph? Begining on the next slide, we demonstrate Watts's model for creating graphs that interpolate between the extremes of a random graph and a caveman graph. We will see that this method in fact results in small world graphs.

                   Previous Slide                                                           Next Slide