Higham, D.J. (2003) Unravelling small world networks. Journal of Computational and Applied Mathematics, 158 (1). pp. 6174. ISSN 03770427

PDF (strathprints000168.pdf)
strathprints000168.pdf Download (3MB)  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) 0667021] 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 shortrange, in the sense that they connect nearneighbours, and relatively few are longrange. 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 shortrange/longrange 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 fillin 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, CuthillMcKee, proteome networks, small world phenomenon, sparse matrix, Mathematics, Computational Mathematics, Applied Mathematics 
Subjects:  Science > Mathematics 
Department:  Faculty of Science > Mathematics and Statistics 
Depositing user:  Ms Sarah Scott 
Date Deposited:  22 Feb 2006 
Last modified:  12 Dec 2015 20:34 
URI:  http://strathprints.strath.ac.uk/id/eprint/168 
Actions (login required)
View Item 