Graph Theory in Practice: Part II
Rewiring the Lattice
It's not really surprising that the lattice model and the Erdos-Rényi model fail to reproduce some features of networks such as the human friendship graph or the World Wide Web. After all, these real-world networks are neither entirely regular nor entirely random. People generally know their neighbors, but their circle of acquaintances is not confined to those who live next door, as the lattice model would imply. Conversely, links between pages on the Web are not created at random, as the Erdos-Rényi process requires.
Watts and Strogatz deal with these failures by a strategy that seems perfectly obvious once someone else has thought of it: They interpolate between the two models. They begin with a regular lattice, such as a ring, and then "rewire" some of the edges to introduce a measure of randomness. Each edge in the original lattice is examined in turn, and is either left in place or else is redirected to another randomly chosen destination. The decision to rewire an edge is governed by a probability p, which can be adjusted over the range from 0 to 1. If p is equal to 0, then nothing happens; the lattice is unchanged. If p is equal to 1, the lattice is transformed into a random graph much like a product of the Erdos-Rényi procedure. The interesting range lies between these extremes.
In their analysis of the rewired graphs, Watts and Strogatz examined not the diameter—the shortest path between the most distant vertices—but the minimum path length L averaged over all pairs of vertices. They observed an abrupt transition in L as the rewiring probability increased. L is at its maximum in the regular lattice, but it falls steeply when just a few of the edges are rewired.
As a measure of clustering in their hybrid graphs, Watts and Strogatz defined a coefficient C. To calculate C, list all the neighbors of a vertex, count the edges that link those neighbors, and divide by the maximum number of edges that could possibly be drawn among the neighbors; then repeat these operations for all the vertices, and take the average. In contrast to the path length L, the clustering coefficient remains high until the rewiring probability is rather large. Hence over a wide range of p values, the graph is dominated by local connections between nearby nodes, but the few shortcuts provide efficient long-distance connections.
Watts and Strogatz tested their model against the Hollywood graph, which has L=3.65 and C=0.79. They created a rewiring model with the same number of vertices and edges and the same average degree. The model has an L value of 3.9 and a C coefficient in the range from 0.61 to 0.84, in good agreement with the actors' graph. The Erdos-Rényi model cannot do nearly as well: The path length of L=2.99 is reasonably close, but the cliquishness score, at C=0.00027, is too small by three orders of magnitude.
Watts and Strogatz suggest several more applications of their model to natural or technological graphs, including a part of the U.S. electric power grid and the nervous system of the nematode worm Caenorhabditis elegans. Again, model and observation are consistent, although the agreement is not as impressive as it is with the Hollywood graph. More recently, Lada A. Adamic of the Xerox Palo Alto Research Center has shown that the Web also fits the small-world model.
As it happens, Watts and Strogatz were not the first to explore the effect of short-circuiting a ring graph. In the 1980s, Fan R. K. Chung (now at the University of California, San Diego), in collaborations with Michael R. Garey of AT&T Laboratories and Béla Bolob?s of the University of Memphis, studied various ways of adding edges to cyclic graphs. They found cases where the diameter is proportional to log n.