### Abstract

Original language | English |
---|---|

Pages (from-to) | 429-444 |

Number of pages | 15 |

Journal | SIAM Journal on Matrix Analysis and Applications |

Volume | 25 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2003 |

### Fingerprint

### Keywords

- web search engine
- Markov chain
- matrix perturbation
- mean hitting time
- optional sampling theorem
- partially random graph
- random walk
- teleporting

### Cite this

*SIAM Journal on Matrix Analysis and Applications*,

*25*(2), 429-444. https://doi.org/10.1137/S0895479802406142

}

*SIAM Journal on Matrix Analysis and Applications*, vol. 25, no. 2, pp. 429-444. https://doi.org/10.1137/S0895479802406142

**A matrix perturbation view of the small world phenomenon.** / Higham, Desmond J.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A matrix perturbation view of the small world phenomenon

AU - Higham, Desmond J.

N1 - Also published in: SIAM Review (2007), 49 (1), pp91-108

PY - 2003

Y1 - 2003

N2 - We use techniques from applied matrix analysis to study small world cutoff in a Markov chain. Our model consists of a periodic random walk plus uniform jumps. This has a direct interpretation as a teleporting random walk, of the type used by search engines to locate web pages, on a simple ring network. More loosely, the model may be regarded as an analogue of the original small world network of Watts and Strogatz [Nature, 393 (1998), pp. 440-442]. We measure the small world property by expressing the mean hitting time, averaged over all states, in terms of the expected number of shortcuts per random walk. This average mean hitting time is equivalent to the expected number of steps between a pair of states chosen uniformly at random. The analysis involves nonstandard matrix perturbation theory and the results come with rigorous and sharp asymptotic error estimates. Although developed in a different context, the resulting cutoff diagram agrees closely with that arising from the mean-field network theory of Newman, Moore, and Watts [Phys. Rev. Lett., 84 (2000), pp. 3201-3204].

AB - We use techniques from applied matrix analysis to study small world cutoff in a Markov chain. Our model consists of a periodic random walk plus uniform jumps. This has a direct interpretation as a teleporting random walk, of the type used by search engines to locate web pages, on a simple ring network. More loosely, the model may be regarded as an analogue of the original small world network of Watts and Strogatz [Nature, 393 (1998), pp. 440-442]. We measure the small world property by expressing the mean hitting time, averaged over all states, in terms of the expected number of shortcuts per random walk. This average mean hitting time is equivalent to the expected number of steps between a pair of states chosen uniformly at random. The analysis involves nonstandard matrix perturbation theory and the results come with rigorous and sharp asymptotic error estimates. Although developed in a different context, the resulting cutoff diagram agrees closely with that arising from the mean-field network theory of Newman, Moore, and Watts [Phys. Rev. Lett., 84 (2000), pp. 3201-3204].

KW - google

KW - web search engine

KW - Markov chain

KW - matrix perturbation

KW - mean hitting time

KW - optional sampling theorem

KW - partially random graph

KW - random walk

KW - teleporting

U2 - 10.1137/S0895479802406142

DO - 10.1137/S0895479802406142

M3 - Article

VL - 25

SP - 429

EP - 444

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 2

ER -