Average case analysis of the Markov chain small-world model

An extended Markov chain small-world network model is further investigated with an average case approach. An exact formula of the average mean first passage time is developed. This new expression is shown to include relevant existing results as its special cases. Moreover, numerical outcomes seem to confirm, within the framework of the average case analysis, some recent results regarding the effect of asymmetry on the small-world phenomenon.