Spectral reordering of a range-dependent weighted random graph

^** Email: aas96106{at}maths.strath.ac.uk Grindrod (2002. Phys. Rev. E, 66, 0667021–0667027) posedthe problem of reordering a range-dependent random graph andshowed that it is relevant to the analysis of data sets frombioinformatics. Reordering under a random graph hypothesis canbe regarded as an extension of clustering and fits into thegeneral area of data mining. Here, we consider a generalizationof Grindrod's model and show how an existing spectral reorderingalgorithm that has arisen in a number of areas may be interpretedfrom a maximum likelihood range-dependent random graph viewpoint.Looked at this way, the spectral algorithm, which uses eigenvectorinformation from the graph Laplacian, is found to be automaticallytuned to an exponential edge density. The connection is precisefor optimal reorderings, but is weaker when approximate reorderingsare computed via relaxation. We illustrate the performance ofthe spectral algorithm in the weighted random graph contextand give experimental evidence that it can be successful forother edge densities. We conclude by applying the algorithmto a data set from the biological literature that describescortical connectivity in the cat brain.