Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Spectral reordering of a range-dependent weighted random graph

Higham, D.J. (2005) Spectral reordering of a range-dependent weighted random graph. IMA Journal of Numerical Analysis, 25. pp. 443-457. ISSN 0272-4979

[img]
Preview
PDF (strathprints000159.pdf)
strathprints000159.pdf

Download (425kB) | Preview

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.

Item type: Article
ID code: 159
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, Mathematics, Computational Mathematics, Applied Mathematics, Mathematics(all)
Subjects: Science > Mathematics
Department: Faculty of Science > Mathematics and Statistics
Depositing user: Ms Sarah Scott
Date Deposited: 10 Feb 2006
Last modified: 18 Jun 2015 09:06
Related URLs:
URI: http://strathprints.strath.ac.uk/id/eprint/159

Actions (login required)

View Item View Item