Periodic reordering
Grindrod, P. and Higham, D.J. and Kalna, G. (2010) Periodic reordering. IMA Journal of Numerical Analysis, 30. pp. 195207. ISSN 02724979

PDF (periodic.pdf)
periodic.pdf Download (4MB)  Preview 
Abstract
For many networks in nature, science and technology, it is possible to order the nodes so that most links are shortrange, connecting near neighbours, and relatively few longrange links, or shortcuts, are present. Given a network as a set of observed links (interactions), the task of finding an ordering of the nodes that reveals such a range dependent structure is closely related to some sparse matrix reordering problems arising in scientific computation. The spectral, or Fiedler vector, approach for sparse matrix reordering has successfully been applied to biological data sets, revealing useful structures and subpatterns. In this work we argue that a periodic analogue of the standard reordering task is also highly relevant. Here, rather than encouraging nonzeros only to lie close to the diagonal of a suitably ordered adjacency matrix, we also allow them to inhabit the offdiagonal corners. Indeed, for the classic smallworld model of Watts and Strogatz (Nature, 1998) this type of periodic structure is inherent. We therefore devise and test a new spectral algorithm for periodic reordering. By generalizing the rangedependent random graph class of Grindrod (Phys. Rev. E, 2002) to the periodic case, we can also construct a computable likelihood ratio that suggests whether a given network is inherently linear or periodic. Tests on synthetic data show that the new algorithm can detect periodic structure, even in the presence of noise. Further experiments on real biological data sets then show that some networks are better regarded as periodic than linear. Hence, we find both qualitative (reordered networks plots) and quantitative (likelihood ratios) evidence of periodicity in biological networks.
Item type:  Article 

ID code:  13618 
Keywords:  spectral vector, Fiedler vector, matrix reordering, biological data sets, periodic reordering, periodic structure, Science (General), Mathematics, Computational Mathematics, Applied Mathematics, Mathematics(all) 
Subjects:  Science > Science (General) Science > Mathematics 
Department:  Faculty of Science > Mathematics and Statistics Faculty of Science > Mathematics and Statistics > Mathematics 
Depositing user:  Mrs Irene Spencer 
Date Deposited:  06 Jan 2010 16:34 
Last modified:  28 Apr 2016 22:46 
Related URLs:  
URI:  http://strathprints.strath.ac.uk/id/eprint/13618 