Creating a Small World Graph

Main Menu           Previous Topic                                                           Next Topic


Generalizing the Procedure

Our procedure has successfully demonstrated that small world graphs can exist and has actually created a set of small world graphs. An important question is how specific the procedure is that creates such graphs. Do small world graphs only exist in a fragile balance, susceptible to slight alterations in structure?

According to Watts, the answer is no. He identifies what he believes to be the critical property of our procedure that allows small world graphs to appear: most connections formed are dependent upon previous connections, thus satisfying a local structure, while a very small number of connections do not respect the structural rule and form randomly.

Watts claims that a small number of such random connections will have a minimal effect on local structure and can even go unnoticed when examining only a small part of a graph. Furthermore, just a small number of such connections is all that is needed to drastically alter the global structure of a graph.

To show that this is the case, Watts creates a new variable, phi, which measures the fraction of edges that are shortcuts. An edge is a shortcut if it spans two agents who would otherwise be separated by a greater number of links. Plotting the path length and clustering coefficient in terms of phi instead of alpha shows that even a tiny increase in phi drastically lowers the path length, while the increase in shortcuts only slowly erodes the clustering coefficient. Thus, a small number of shortcuts introduced into a highly structured graph create a small world graph.

In this light, it is no surprise that small world graphs can be readily identified in the real world. It seems that they may be quite natural after all.

                   Previous Slide                                                           Next Slide