A matrix perturbation view of the small world phenomenon

Higham, Desmond J. (2003) A matrix perturbation view of the small world phenomenon. SIAM Journal on Matrix Analysis and Applications, 25 (2). pp. 429-444. ISSN 0895-4798 (https://doi.org/10.1137/S0895479802406142)

[thumbnail of strathprints000167]
Preview
 Text. Filename: strathprints000167.pdf
Accepted Author Manuscript
Download (316kB)| Preview

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].

ORCID iDs

Higham, Desmond J. ORCID logoORCID: https://orcid.org/0000-0002-6635-3461;
  • Item type:Article
    ID code:167
    Dates:
    Date
    Event
    2003
    Published
    Notes:Also published in: SIAM Review (2007), 49 (1), pp91-108
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Ms Sarah Scott
    Date deposited:22 Feb 2006
    Last modified:11 Nov 2024 08:23
    URI:https://strathprints.strath.ac.uk/id/eprint/167
CORE (COnnecting REpositories)