Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Unravelling small world networks

Higham, D.J. (2003) Unravelling small world networks. Journal of Computational and Applied Mathematics, 158 (1). pp. 61-74. ISSN 0377-0427

[img]
Preview
PDF (strathprints000168.pdf)
Download (3573Kb) | Preview

    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.

    Item type: Article
    ID code: 168
    Keywords: adjacency matrix, bandwidth, bioinformatics, Cuthill-McKee, proteome networks, small world phenomenon, sparse matrix, Mathematics
    Subjects: Science > Mathematics
    Department: Faculty of Science > Mathematics and Statistics
    Related URLs:
      Depositing user: Ms Sarah Scott
      Date Deposited: 22 Feb 2006
      Last modified: 13 Mar 2012 05:49
      URI: http://strathprints.strath.ac.uk/id/eprint/168

      Actions (login required)

      View Item

      Fulltext Downloads: