On fast computation of directed graph Laplacian pseudo-inverse

Research output: Contribution to journalArticlepeer-review

Abstract

The Laplacian matrix and its pseudo-inverse for a strongly connected directed graph is fundamental in computing many properties of a directed graph. Examples include random-walk centrality and betweenness measures, average hitting and commute times, and other connectivity measures. These measures arise in the analysis of many social and computer networks. In this short paper, we show how a linear system involving the Laplacian may be solved in time linear in the number of edges, times a factor depending on the separability of the graph. This leads directly to the column-by-column computation of the entire Laplacian pseudo-inverse in time quadratic in the number of nodes, i.e., constant time per matrix entry. The approach is based on “off-the-shelf” iterative methods for which global linear convergence is guaranteed, without recourse to any matrix elimination algorithm.

Original languageEnglish (US)
Pages (from-to)128-148
Number of pages21
JournalLinear Algebra and Its Applications
Volume623
DOIs
StatePublished - Aug 15 2021

Bibliographical note

Funding Information:
This research was supported in part by NSF grants 1835530 and 1922512 . The author would like to thank the anonymous reviewer for many helpful comments that greatly improved the manuscript.

Publisher Copyright:
© 2020 Elsevier Inc.

Keywords

  • Directed graphs
  • Graph Laplacian
  • Iterative methods
  • Pseudo-inverse

Fingerprint

Dive into the research topics of 'On fast computation of directed graph Laplacian pseudo-inverse'. Together they form a unique fingerprint.

Cite this