Volume 39, pp. 353-378, 2012.

Locally supported eigenvectors of matrices associated with connected and unweighted power-law graphs

Van Emden Henson and Geoffrey Sanders

Abstract

We identify a class of graph substructures that yields locally supported eigenvectors of matrices associated with unweighted and undirected graphs, such as the various types of graph Laplacians and adjacency matrices. We discuss how the detection of these substructures gives rise to an efficient calculation of the locally supported eigenvectors and how to exploit the sparsity of such eigenvectors to coarsen the graph into a (possibly) much smaller graph for calculations involving multiple eigenvectors. This preprocessing step introduces no spectral error and, for some graphs, may amount to considerable computational savings when computing any desired eigenpair. As an example, we discuss how these vectors are useful for estimating the commute time between any two vertices and bounding the error associated with approximations for some pairs of vertices.

Full Text (PDF) [851 KB], BibTeX

Key words

graph Laplacian, adjacency matrix, eigenvectors, eigenvalues, sparse matrices

AMS subject classifications

05C50, 05C82, 65F15, 65F50, 94C15

Links to the cited ETNA articles

< Back