A matrix perturbation view of the small world phenomenon

Desmond J. Higham

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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].
LanguageEnglish
Pages91-108
Number of pages17
JournalSIAM Review
Volume49
Issue number1
DOIs
Publication statusPublished - Mar 2007

Fingerprint

Matrix Perturbation
Small World
Random walk
Hitting Time
Small-world networks
Circuit theory
Search engines
Markov processes
Nonstandard Analysis
Ring Network
Websites
Matrix Analysis
Small-world Network
Matrix Theory
Asymptotic Estimates
Search Engine
Mean Field
Perturbation Theory
Error Estimates
Markov chain

Keywords

  • Google
  • Markov chain
  • matrix perturbation
  • mean hitting time
  • optional sampling theorem
  • partially random graph
  • random walk
  • Sherman-Morrison formula
  • teleporting
  • web search engine

Cite this

Higham, Desmond J. / A matrix perturbation view of the small world phenomenon. In: SIAM Review. 2007 ; Vol. 49, No. 1. pp. 91-108.
@article{04ab4564cfb444ae8fb3a49499acdd31,
title = "A matrix perturbation view of the small world phenomenon",
abstract = "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].",
keywords = "Google, Markov chain, matrix perturbation, mean hitting time, optional sampling theorem, partially random graph, random walk, Sherman-Morrison formula, teleporting, web search engine",
author = "Higham, {Desmond J.}",
note = "Also published in: SIAM Journal on Matrix Analysis and Applications (2003), 25 (2), pp429-444 (This is a variant record)",
year = "2007",
month = "3",
doi = "10.1137/060664987",
language = "English",
volume = "49",
pages = "91--108",
journal = "SIAM Review",
issn = "0036-1445",
number = "1",

}

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

In: SIAM Review, Vol. 49, No. 1, 03.2007, p. 91-108.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A matrix perturbation view of the small world phenomenon

AU - Higham, Desmond J.

N1 - Also published in: SIAM Journal on Matrix Analysis and Applications (2003), 25 (2), pp429-444 (This is a variant record)

PY - 2007/3

Y1 - 2007/3

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 - Markov chain

KW - matrix perturbation

KW - mean hitting time

KW - optional sampling theorem

KW - partially random graph

KW - random walk

KW - Sherman-Morrison formula

KW - teleporting

KW - web search engine

UR - http://strathprints.strath.ac.uk/167/

UR - http://dx.doi.org/10.1137/060664987

U2 - 10.1137/060664987

DO - 10.1137/060664987

M3 - Article

VL - 49

SP - 91

EP - 108

JO - SIAM Review

T2 - SIAM Review

JF - SIAM Review

SN - 0036-1445

IS - 1

ER -