Geodesic
Locally supported eigenvectors of matrices associated with connected and unweighted power-law graphs
Electronic transactions on numerical analysis, Tome 39 (2012), pp. 353-378
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.
Classification : 05C50, 05C82, 65F15, 65F50, 94C15
Keywords: graph Laplacian, adjacency matrix, eigenvectors, eigenvalues, sparse matrices 
@article{ETNA_2012__39__a5,
     author = {Henson,  Van Emden and Sanders,  Geoffrey},
     title = {Locally supported eigenvectors of matrices associated with connected and unweighted power-law graphs},
     journal = {Electronic transactions on numerical analysis},
     pages = {353--378},
     year = {2012},
     volume = {39},
     zbl = {1286.05089},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2012__39__a5/}
}
TY  - JOUR
AU  - Henson,  Van Emden
AU  - Sanders,  Geoffrey
TI  - Locally supported eigenvectors of matrices associated with connected and unweighted power-law graphs
JO  - Electronic transactions on numerical analysis
PY  - 2012
SP  - 353
EP  - 378
VL  - 39
UR  - http://geodesic.mathdoc.fr/item/ETNA_2012__39__a5/
LA  - en
ID  - ETNA_2012__39__a5
ER  - 
%0 Journal Article
%A Henson,  Van Emden
%A Sanders,  Geoffrey
%T Locally supported eigenvectors of matrices associated with connected and unweighted power-law graphs
%J Electronic transactions on numerical analysis
%D 2012
%P 353-378
%V 39
%U http://geodesic.mathdoc.fr/item/ETNA_2012__39__a5/
%G en
%F ETNA_2012__39__a5
Henson,  Van Emden; Sanders,  Geoffrey. Locally supported eigenvectors of matrices associated with connected and unweighted power-law graphs. Electronic transactions on numerical analysis, Tome 39 (2012), pp. 353-378. http://geodesic.mathdoc.fr/item/ETNA_2012__39__a5/