  The diagonal entries of pseudoinverse of the Laplacian matrix of a graph
appear in many important practical applications, since they contain much
information of the graph and many relevant quantities can be expressed in terms
of them, such as Kirchhoff index and current flow centrality. However, a
na\"{\i}ve approach for computing the diagonal of a matrix inverse has cubic
computational complexity in terms of the matrix dimension, which is not
acceptable for large graphs with millions of nodes. Thus, rigorous solutions to
the diagonal of the Laplacian matrices for general graphs, even for particluar
graphs are much less. In this paper, we propose a theoretically guaranteed
estimation algorithm, which approximates all diagonal entries of the
pseudoinverse of a graph Laplacian in nearly linear time with respect to the
number of edges in the graph. We execute extensive experiments on real-life
networks, which indicate that our algorithm is both efficient and accurate.
Also, we determine exact expressions for the diagonal elements of pseudoinverse
of the Laplacian matrices for Koch networks and uniform recursive trees, and
compare them with those obtained by our approximation algorithm. Finally, we
use our algorithm to evaluate the Kirchhoff index of three deterministic model
networks, for which the Kirchhoff index can be rigorously determined. These
results further show the effectiveness and efficiency of our algorithm.
