Gilbert Strang - Partly random graphs and small world networks

It is almost true that any two people in Canada 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 try to analyze this. We also study a related model, which starts with n edges around a cycle (large diameter) and adds n edges around a second (but now random) cycle. The average distance between pairs becomes nearly . 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 with Li He and Xiangwei Liu. In this case we found eigenvalues with very high multiplicity.