CS590N Statistical Relational Learning
Spring 2007: Example Reponse Paper

Collective Dynamics of Small World Networks
D. Watts and S. Strogatz
By: Jen Neville

This paper identifies a limiting assumption in current work analyzing the networks of dynamic systems. More specifically, past approaches have restricted their attention to either regular lattice structures or random graphs. The authors conjecture that real-world graph structures lie on a spectrum with lattice graphs at one end (representing order) and random graphs at the other end (representing disorder). To begin exploring the dynamics of graphs throughout the spectrum, the authors propose a simple model of graph generation and two measurements of graph properties -- characteristic path length (L) and clustering coefficient (C). Experiments on simulated data show that relatively small departures from order can have a drastic affect on global graph properties (i.e., L) with little impact on local properties (i.e., C) and that influence can spread quickly in graphs with even a small amount of randomness. Analysis of three real-world graphs shows that they do indeed share characteristics of both random graphs (i.e., short L) and lattice graphs (i.e., high C). This indicates that studying graphs throughout the entire spectrum could lead to improved understanding of the behavior of dynamic network systems.

The authors framed the problem well through the use of a spectrum and a simple method of graph generation that can span the spectrum. A similar approach may be useful for exploring the dynamics of graphical model inference. During inference, if the graph can be structured to be acyclic then we can do exact inference. But if it has cycles, we have to resort to approximate inferences techniques. Although these techniques have been shown to converge in practice, we don't really understand the situations in which we can safely use approximate inference techniques. As far as I know, no one has begun to explore the affects of graph properties on the performance of approximate inference techniques (either convergence or overall accuracy). One of the key insights of this paper is that two different graph metrics may have completely different phase transitions with respect to graph structure. This may also be true of inference graphs (e.g., cycle length may change more quickly than mixing time but mixing time may have the key property that determines convergence time).

The authors failed to give a crisp definition of the "small-world phenomenon". The best definition was in the caption of Table 1 where they say that "L~>L_random but C>>C_random", which I could take to mean that L is closer to L_random and C is closer to C_regular. However, the real-world graphs are compared only to one end of the spectrum (random graphs). It's hard to get an sense of the significance of the results without the measurements from the other end of the spectrum. For example, the actor graph has a C that is 3000 times random, the power grid has a C that is 16 times random, and the neural network has a C that is 5 times random. There is a huge difference between these values but are the differences significant? It's impossible to tell without estimates of C for comparable regular lattices.