Unravelling small world networks

D.J. Higham

Research output: Contribution to journalArticle

20 Citations (Scopus)

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.
LanguageEnglish
Pages61-74
Number of pages13
JournalJournal of Computational and Applied Mathematics
Volume158
Issue number1
DOIs
Publication statusPublished - Sep 2003

Fingerprint

Small-world networks
Small-world Network
Random Graphs
Reordering
Small World
Bioinformatics
Inverse problems
Range of data
Maximum likelihood
Graph in graph theory
Proteins
Likelihood Principle
Matrix Theory
Network Modeling
Dependent
Adjacency Matrix
Sparse matrix
Large Data Sets
Justification
Maximum Likelihood

Keywords

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

Cite this

Higham, D.J. / Unravelling small world networks. In: Journal of Computational and Applied Mathematics. 2003 ; Vol. 158, No. 1. pp. 61-74.
@article{531b0568efcf450384042cf3d218e9c0,
title = "Unravelling small world networks",
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.",
keywords = "adjacency matrix, bandwidth, bioinformatics, Cuthill-McKee, proteome networks, small world phenomenon, sparse matrix",
author = "D.J. Higham",
year = "2003",
month = "9",
doi = "10.1016/S0377-0427(03)00471-0",
language = "English",
volume = "158",
pages = "61--74",
journal = "Journal of Computational and Applied Mathematics",
issn = "0377-0427",
number = "1",

}

Unravelling small world networks. / Higham, D.J.

In: Journal of Computational and Applied Mathematics, Vol. 158, No. 1, 09.2003, p. 61-74.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Unravelling small world networks

AU - Higham, D.J.

PY - 2003/9

Y1 - 2003/9

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

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

KW - adjacency matrix

KW - bandwidth

KW - bioinformatics

KW - Cuthill-McKee

KW - proteome networks

KW - small world phenomenon

KW - sparse matrix

U2 - 10.1016/S0377-0427(03)00471-0

DO - 10.1016/S0377-0427(03)00471-0

M3 - Article

VL - 158

SP - 61

EP - 74

JO - Journal of Computational and Applied Mathematics

T2 - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

SN - 0377-0427

IS - 1

ER -