Unravelling small world networks

D.J. Higham

Research output: Contribution to journalArticle

21 Citations (Scopus)
28 Downloads (Pure)

Abstract

New classes of random graphs have recently been shown to exhibit the small world phenomenon - they are clustered like regular lattices and yet have small average pathlengths like traditional random graphs. Small world behaviour has been observed in a number of real life networks, and hence these random graphs represent a useful modelling tool. In particular, Grindrod [Phys. Rev. E 66 (2002) 066702-1] has proposed a class of range dependent random graphs for modelling proteome networks in bioinformatics. A property of these graphs is that, when suitably ordered, most edges in the graph are short-range, in the sense that they connect near-neighbours, and relatively few are long-range. Grindrod also looked at an inverse problem - given a graph that is known to be an instance of a range dependent random graph, but with vertices in arbitrary order, can we reorder the vertices so that the short-range/long-range connectivity structure is apparent? When the graph is viewed in terms of its adjacency matrix, this becomes a problem in sparse matrix theory: find a symmetric row/column reordering that places most nonzeros close to the diagonal. Algorithms of this general nature have been proposed for other purposes, most notably for reordering to reduce fill-in and for clustering large data sets. Here, we investigate their use in the small world reordering problem. Our numerical results suggest that a spectral reordering algorithm is extremely promising, and we give some theoretical justification for this observation via the maximum likelihood principle.
Original languageEnglish
Pages (from-to)61-74
Number of pages13
JournalJournal of Computational and Applied Mathematics
Volume158
Issue number1
DOIs
Publication statusPublished - Sep 2003

Keywords

  • adjacency matrix
  • bandwidth
  • bioinformatics
  • Cuthill-McKee
  • proteome networks
  • small world phenomenon
  • sparse matrix

Fingerprint Dive into the research topics of 'Unravelling small world networks'. Together they form a unique fingerprint.

Cite this