THEMATIC PROGRAMS

Many complex networks in nature exhibit two properties that are seemingly at odds. They are clustered---neighbors of neighbors are very likely to be neighbors---and they are small worlds---any 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, one-dimensional, 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 mean-field network theory of Newman, Moore and Watts [Phys. Rev. Lett., Vol. 84, 2000].

I will finish by mentioning some recent ideas that use partially random graphs to model bioinformatics data.