Unravelling small world networks

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:158

Article; Proceedings Paper

Higham, DJ

关键词: adjacency matrix;    bandwidth;    bioinformatics;    Cuthill-McKee;    envelope;    genome datasets;    laplacian;    maximum likelihood;    minimum degree;    proteome networks;    random graph;    reordering;    small world phenomenon;    sparse matrix;    two-sum;   

DOI  :  10.1016/S0377-0427(03)00471-0

来源: Elsevier

【 摘 要 】

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. (C) 2003 Elsevier B.V. All rights reserved.

【 授权许可】

Free