Abstract
Language | English |
---|---|
Pages | 61-74 |
Number of pages | 13 |
Journal | Journal of Computational and Applied Mathematics |
Volume | 158 |
Issue number | 1 |
DOIs | |
Publication status | Published - Sep 2003 |
Fingerprint
Keywords
- adjacency matrix
- bandwidth
- bioinformatics
- Cuthill-McKee
- proteome networks
- small world phenomenon
- sparse matrix
Cite this
}
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 journal › Article
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 -