ABSTRACT


Many complex networks in nature exhibit two properties that are seemingly at odds. They are clusteredneighbors of neighbors are very likely to be neighborsand they are small worldsany two nodes can typically be connected by a relatively short path. Watts and Strogatz [Nature, Vol. 393, 1998] referred to this as the small world phenomenon and proposed a network model, in the form of a partially random graph, that was shown through simulation to capture the two properties. The model incorporates a parameter that interpolates between fully local and fully global regimes. As the parameter is varied the small world property is roused before the clustering property is lost. I will show that the small world phenomenon observed by Watts and Strogatz for randomized networks also arises in the context of Markov chains. The Markov chain model interpolates between local and global periodic, onedimensional, random walks. The small world property may be measured by expressing the average mean hitting time in terms of the average number of shortcuts per random walk. The calculation uses ideas from numerical analysis and provides rigorous asymptotic error estimates. The resulting cutoff diagram agrees closely with that arising from the meanfield network theory of Newman, Moore and Watts [Phys. Rev. Lett., Vol. 84, 2000]. Return to Applied Math Colloquium home page 