Spectral reordering of a range-dependent weighted random graph

D.J. Higham

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

Reordering under a random graph hypothesis can be regarded as an extension of clustering and fits into the general area of data mining. Here, we consider a generalization of Grindrod's model and show how an existing spectral reordering algorithm that has arisen in a number of areas may be interpreted from a maximum likelihood range-dependent random graph viewpoint. Looked at this way, the spectral algorithm, which uses eigenvector information from the graph Laplacian, is found to be automatically tuned to an exponential edge density. The connection is precise for optimal reorderings, but is weaker when approximate reorderings are computed via relaxation. We illustrate the performance of the spectral algorithm in the weighted random graph context and give experimental evidence that it can be successful for other edge densities. We conclude by applying the algorithm to a data set from the biological literature that describes cortical connectivity in the cat brain.
LanguageEnglish
Pages443-457
Number of pages14
JournalIMA Journal of Numerical Analysis
Volume25
DOIs
Publication statusPublished - 2005

Fingerprint

Reordering
Weighted Graph
Random Graphs
Dependent
Range of data
Graph Laplacian
Eigenvalues and eigenfunctions
Eigenvector
Maximum likelihood
Maximum Likelihood
Data mining
Brain
Data Mining
Connectivity
Clustering
Model

Keywords

  • bioinformatics
  • cortical connectivity
  • clustering
  • functional magnetic resonance imaging of the brain
  • genome data sets
  • Laplacian
  • maximum likelihood
  • small world networks
  • sparse matrix
  • two-sum

Cite this

@article{204a85da6c30415ab7b5f2d8e8e54b3e,
title = "Spectral reordering of a range-dependent weighted random graph",
abstract = "Reordering under a random graph hypothesis can be regarded as an extension of clustering and fits into the general area of data mining. Here, we consider a generalization of Grindrod's model and show how an existing spectral reordering algorithm that has arisen in a number of areas may be interpreted from a maximum likelihood range-dependent random graph viewpoint. Looked at this way, the spectral algorithm, which uses eigenvector information from the graph Laplacian, is found to be automatically tuned to an exponential edge density. The connection is precise for optimal reorderings, but is weaker when approximate reorderings are computed via relaxation. We illustrate the performance of the spectral algorithm in the weighted random graph context and give experimental evidence that it can be successful for other edge densities. We conclude by applying the algorithm to a data set from the biological literature that describes cortical connectivity in the cat brain.",
keywords = "bioinformatics, cortical connectivity, clustering, functional magnetic resonance imaging of the brain, genome data sets, Laplacian, maximum likelihood, small world networks, sparse matrix, two-sum",
author = "D.J. Higham",
year = "2005",
doi = "10.1093/imanum/dri003",
language = "English",
volume = "25",
pages = "443--457",
journal = "IMA Journal of Numerical Analysis",
issn = "0272-4979",

}

Spectral reordering of a range-dependent weighted random graph. / Higham, D.J.

In: IMA Journal of Numerical Analysis, Vol. 25, 2005, p. 443-457.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Spectral reordering of a range-dependent weighted random graph

AU - Higham, D.J.

PY - 2005

Y1 - 2005

N2 - Reordering under a random graph hypothesis can be regarded as an extension of clustering and fits into the general area of data mining. Here, we consider a generalization of Grindrod's model and show how an existing spectral reordering algorithm that has arisen in a number of areas may be interpreted from a maximum likelihood range-dependent random graph viewpoint. Looked at this way, the spectral algorithm, which uses eigenvector information from the graph Laplacian, is found to be automatically tuned to an exponential edge density. The connection is precise for optimal reorderings, but is weaker when approximate reorderings are computed via relaxation. We illustrate the performance of the spectral algorithm in the weighted random graph context and give experimental evidence that it can be successful for other edge densities. We conclude by applying the algorithm to a data set from the biological literature that describes cortical connectivity in the cat brain.

AB - Reordering under a random graph hypothesis can be regarded as an extension of clustering and fits into the general area of data mining. Here, we consider a generalization of Grindrod's model and show how an existing spectral reordering algorithm that has arisen in a number of areas may be interpreted from a maximum likelihood range-dependent random graph viewpoint. Looked at this way, the spectral algorithm, which uses eigenvector information from the graph Laplacian, is found to be automatically tuned to an exponential edge density. The connection is precise for optimal reorderings, but is weaker when approximate reorderings are computed via relaxation. We illustrate the performance of the spectral algorithm in the weighted random graph context and give experimental evidence that it can be successful for other edge densities. We conclude by applying the algorithm to a data set from the biological literature that describes cortical connectivity in the cat brain.

KW - bioinformatics

KW - cortical connectivity

KW - clustering

KW - functional magnetic resonance imaging of the brain

KW - genome data sets

KW - Laplacian

KW - maximum likelihood

KW - small world networks

KW - sparse matrix

KW - two-sum

UR - http://www.maths.strath.ac.uk/~aas96106/rep14_2003.ps

U2 - 10.1093/imanum/dri003

DO - 10.1093/imanum/dri003

M3 - Article

VL - 25

SP - 443

EP - 457

JO - IMA Journal of Numerical Analysis

T2 - IMA Journal of Numerical Analysis

JF - IMA Journal of Numerical Analysis

SN - 0272-4979

ER -