Dynamics of Small-World Networks

The small-world phenomenon (aka "Six Degrees of Separation") is familiar to all us through folklore and annecdote -- everyone on earth is linked to everyone else through a giant social network via only a short chain of mutual acquaintances. Here I show that the small-world phenomenon -- defined as the coexistence of a short global length scale and high local clustering -- is actually a property of a general class of partly-ordered, partly-random graphs. These "small-world" networks can be used to characterize the structure of three real networks that arise in applications as diverse as movie actors, power grids and neural networks. Finally, the structural parameters that describe small-world networks also turn out to affect the dynamics of a variety of distributed dynamical systems. Here I discuss the spread of an infectious disease and global computation in cellular automata.