It is almost true that any two people in the US are connected by less than six steps from one friend to another. What are models for large graphs with such small diameters ?

Watts and Strogatz observed (in Nature, June 1998) that a few random edges in a graph could quickly reduce its diameter (longest distance between two nodes). We report on an analysis by Newman and Watts (using mathematics of physicists) to estimate the diameter with an N-cycle and M random shortcuts, 1 << M << N.

We also study a related model, which adds N edges around a second (but now random) cycle. The average distance between pairs becomes nearly A log n + B. The eigenvalues of the adjacency matrix are surprisingly close to an arithmetic progression; for each cycle they would be cosines, the sum changes everything.

We will discuss some of the analysis (with Alan Edelman and Henrik Eriksson at MIT) and also some applications. We also report on the surprising eigenvalue distribution for trees (large and growing ) found by Li He and Xiangwei Liu. And a nice work by Jon Kleinberg discusses when the short paths can actually be located efficiently.