Although we covered the Watts-Strogatz model in class today, there are several concepts in the original paper that were not discussed, and I thought these concepts would make for an interesting blog post. The basic Watts-Strogatz model consists of a graph with both clusters of nodes (this arises from all nodes have links to every other node within distance r; nearby nodes will thus form clusters) as well as a short distance between far away nodes (this arises from the random links each nodes have).

 There are formal definitions to quantify these 2 qualities for graphs, and they are known in the literature as L, the characteristic path length, and C, the clustering coefficient. Given a graph G, which consists of N nodes and K links, we can define L and C: 

Where dij is simply the distance between 2 nodes i and j. This is thus simply the average of the shortest distance between 2 nodes in the graph. This is thus our familiar number 6 in the 6 degree of seperations experiment, if you assume that everyone used the shortest path possible to get to that stock broker in Boston.

 C is slightly more complicated: we first define Ci, the clustering coeffiecent for a node i as follows:

Where Gi is the subgraph of neighbors of node i, and ki is the number of neighbors of node i. Note that the denominator is ki(ki-1)/2, because that is the case where every one of the neighbors of i are connected to every other neighbor of i, i.e. the case where Gi is a complete graph. Intuitively, this gives us a measure of how tightly connected the neighbors of i are, since we’re taking the number of edges in the subgraph divided by the case where Gi is a complete graph. Note also that Ci thus goes between 0 and 1.

 C is then defined as

Which is simple the average of the sum of the clustering coefficient for the nodes in the graph.

Small world graphs are then defined in the Watts Strogatz model as graphs with a low value of L but high values of C.

One point which I felt was not strongly enough emphasized in the lecture is that the Watts Strogatz model builds these small world graphs by taking different parameters for a probability p for random rewiring from a regular graph (a regular graph being a graph with a lattice structure, e.g. the rectangular grid). This is important because regular graphs have a high value of C and a high value of L, whereas random graphs have a low value of C but a low value of L. The Watts-Strogatz model thus takes the best of both worlds as it were from both random and regular graphs.

Also demonstrated in the original paper by Watts and Strogatz are that these small world graphs can be found in a large variety of places - they built models for the IMDB database, the power grid of the Western United States, and the neural network of a worm, and showed that they all demonstrated the small world properties of having a low value of L but a high value of C.

There have also of course been criticisms of the model - one obvious one is that this analysis breaks down in the presence of unconnected graphs: Assume for example, that the film industries of Malaysia and the United States are 2 separate graphs that are very well connected internally but have no bridging links. Since C and L would diverge, we cannot apply this analysis onto the graph of both Malaysia and the United States. Another is that the original model ignores weights: Although Brad Pitt has acted in movies with both Angelina Jolie and Geena Davis, there is no way in the original model to show that Brad Pitt has much stronger links with Angelina Jolie than with Geena Davis. Several other people have come up with modifications to the theory; in particular, V.Latora and M. Marchiori have defined concepts of efficiency, on both a Global and Local scale that take the place of L and C, are able to deal with these problem areas of unconnectedness and weights, and have shown that all examples of small world graphs demonstrated by Watts and Strogatz have both high values of Global and Local efficiency. The full details of these concepts of efficiency, as well as another concept of cost that they introduced, I will leave to interested readers to read up on their own.

 References:

1. Duncan Watts, Steve Strogatz (1998), “Collective Dynamics of Small-World networks”, Nature 393(6684): 409-10

2.V. Latora, M. Marchiori (2003) ”Economic Small-World Behavior in Weighted Networks”,The European Physical Journal B vol. 32, Elsevier, 2003.