|
Abstract: 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 ? Outstanding applications would be networks of neurons, or an electric power grid, or even (possibly) the world wide web. 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 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 the spectrum completely. We will discuss diameters and eigenvalues of the adjacency matrix for partly random graphs. 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 be located efficiently by a decentralized algorithm - as on the web. 
|