Small World Networks, Markov Chains and Numerical Analysis

Des Higham

Department of Mathematics University of Strathclyde, Scotland, UK
Visiting the Fields Institute, Toronto

March 11, 4:15pm


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,

Return to Applied Math Colloquium home page