Matrix analysis of a Markov chain small-world model

Recently D. Higham showed that the small-world phenomenon arising in a ring network of N nodes can be modelled by a Markov chain which depends on a parameter E of the form is an element of = K/N-alpha,where K >= 0 and alpha > 1. The parameter can be viewed as a transitional factor interpolating between the completely local and completely global configurations of the network. Higham analyzed the Markov chain model by a combination of matrix perturbation theory and finite difference approximations to an underlying boundary value problem. Using such tools he obtained asymptotic results for the limiting case when N is sufficiently large. Furthermore, for large N, Higham verified the small-world phenomenon on the network in the case when alpha = 3. Motivated by Higham's work, we show that the Markov chain of the small-world model can be investigated more completely by direct matrix-theoretic methods which produces exact results for all N and for all E. Our results therefore allow a fuller examination of the behavior of the small-world phenomenon in the Markov chain model for small to moderate values of N and for all alpha > 1. (c) 2005 Elsevier Inc. All rights reserved.