  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.
