Periodic reordering

Peter Grindrod, Desmond J. Higham, Gabriela Kalna

Research output: Contribution to journalArticle

8 Citations (Scopus)
60 Downloads (Pure)

Abstract

For many networks in nature, science and technology, it is possible to order the nodes so that most links are short-range, connecting near neighbours, and relatively few long-range 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 off-diagonal corners. Indeed, for the classic small-world 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 range-dependent 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 ofperiodicity in biological networks.
Original languageEnglish
Pages (from-to)195-207
Number of pages13
JournalIMA Journal of Numerical Analysis
Volume30
Issue number1
DOIs
Publication statusPublished - 1 Jan 2010

Fingerprint

Reordering
Periodic structures
Periodic Structures
Likelihood Ratio
Sparse matrix
Range of data
Graph Classes
Dependent
Small World
Biological Networks
Adjacency Matrix
Synthetic Data
Vertex of a graph
Random Graphs
Nearest Neighbor
Analogue
Experiments
Interaction
Experiment

Keywords

  • spectral vector
  • Fiedler vector
  • matrix reordering
  • biological data sets
  • periodic reordering
  • periodic structure

Cite this

Grindrod, P., Higham, D. J., & Kalna, G. (2010). Periodic reordering. IMA Journal of Numerical Analysis, 30(1), 195-207. https://doi.org/10.1093/imanum/drp047
Grindrod, Peter ; Higham, Desmond J. ; Kalna, Gabriela. / Periodic reordering. In: IMA Journal of Numerical Analysis. 2010 ; Vol. 30, No. 1. pp. 195-207.
@article{1efff7f5c49f4e438b240172434a7a45,
title = "Periodic reordering",
abstract = "For many networks in nature, science and technology, it is possible to order the nodes so that most links are short-range, connecting near neighbours, and relatively few long-range 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 off-diagonal corners. Indeed, for the classic small-world 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 range-dependent 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 ofperiodicity in biological networks.",
keywords = "spectral vector, Fiedler vector, matrix reordering, biological data sets, periodic reordering, periodic structure",
author = "Peter Grindrod and Higham, {Desmond J.} and Gabriela Kalna",
year = "2010",
month = "1",
day = "1",
doi = "10.1093/imanum/drp047",
language = "English",
volume = "30",
pages = "195--207",
journal = "IMA Journal of Numerical Analysis",
issn = "0272-4979",
number = "1",

}

Grindrod, P, Higham, DJ & Kalna, G 2010, 'Periodic reordering', IMA Journal of Numerical Analysis, vol. 30, no. 1, pp. 195-207. https://doi.org/10.1093/imanum/drp047

Periodic reordering. / Grindrod, Peter; Higham, Desmond J.; Kalna, Gabriela.

In: IMA Journal of Numerical Analysis, Vol. 30, No. 1, 01.01.2010, p. 195-207.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Periodic reordering

AU - Grindrod, Peter

AU - Higham, Desmond J.

AU - Kalna, Gabriela

PY - 2010/1/1

Y1 - 2010/1/1

N2 - For many networks in nature, science and technology, it is possible to order the nodes so that most links are short-range, connecting near neighbours, and relatively few long-range 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 off-diagonal corners. Indeed, for the classic small-world 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 range-dependent 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 ofperiodicity in biological networks.

AB - For many networks in nature, science and technology, it is possible to order the nodes so that most links are short-range, connecting near neighbours, and relatively few long-range 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 off-diagonal corners. Indeed, for the classic small-world 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 range-dependent 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 ofperiodicity in biological networks.

KW - spectral vector

KW - Fiedler vector

KW - matrix reordering

KW - biological data sets

KW - periodic reordering

KW - periodic structure

UR - http://www.scopus.com/inward/record.url?scp=76549112326&partnerID=8YFLogxK

U2 - 10.1093/imanum/drp047

DO - 10.1093/imanum/drp047

M3 - Article

VL - 30

SP - 195

EP - 207

JO - IMA Journal of Numerical Analysis

JF - IMA Journal of Numerical Analysis

SN - 0272-4979

IS - 1

ER -

Grindrod P, Higham DJ, Kalna G. Periodic reordering. IMA Journal of Numerical Analysis. 2010 Jan 1;30(1):195-207. https://doi.org/10.1093/imanum/drp047