Generalized Laplacians and First Transit Times for Directed Graphs

Abstract

In this paper, we extend previous results on average commute-times for undirected graphs to fully-connected directed graphs, corresponding to irreducible Markov chains. We introduce an unsymmetrized generalized Laplacian matrix and show how its pseudo-inverse directly yields the one-way first-transit times and round-trip commute times with formulas almost matching those for the undirected graph case. We show that the results are equivalent to similar formulas in terms of the Fundamental Matrix for recurrent irreducible Markov chains. We show that the unsymmetrized generalized Laplacian and its pseudo-inverse are positive semi-definite, leading to a natural embedding of the graph in Euclidean space which preserves the round-trip commute times.