Paper Info
Title
Approximations Of The Generalized Inverse Of The Graph Laplacian Matrix
Abstract
We devise methods for finding approximations of the generalized inverse of the graph Laplacian matrix, which arises in many graph-theoretic applications. Finding this matrix in its entirety involves solving a matrix inversion problem, which is resource-demanding in terms of consumed time and memory and hence impractical whenever the graph is relatively large. Our approximations use only a few eigenpairs of the Laplacian matrix and are parametric with respect to this number, so that the user can compromise between effectiveness and efficiency of the approximate solution. We apply the devised approximations to the problem of computing current-flow betweenness centrality on a graph. However, given the generality of the Laplacian matrix, many other applications can be sought. We experimentally demonstrate that the approximations are effective already with a constant number of eigenpairs. These few eigenpairs can be stored with a linear amount of memory in the number of nodes of the graph, and in the realistic case of sparse networks, they can be efficiently computed using one of the many methods for retrieving a few eigenpairs of sparse matrices that abound in the literature.
Year
DOI
Venue
2012
10.1080/15427951.2012.715115
INTERNET MATHEMATICS
DocType
Volume
Issue
Journal
8
4
ISSN
Citations 
PageRank 
1542-7951
5
0.47
References 
Authors
6
2
Name
Order
Citations
PageRank
Enrico Bozzo1518.79
Massimo Franceschet265839.91