The expected commute times for a strongly connected directed graph are related to an asymmetric Laplacian matrix as a direct extension to similar well known formulas for undirected graphs. We show the close relationships between the asymmetric Laplacian and the so-called Fundamental matrix. We give bounds for the commute times in terms of the stationary probabilities for a random walk over the graph together with the asymmetric Laplacian and show how this can be approximated by a symmetrized Laplacian derived from a related weighted undirected graph.
Bibliographical noteFunding Information:
Supported in part by NSF grants 0534286, 0626808, 0916750, DTRA grant HDTRA1-09-1-0050, and a Univ. of Minn. DTC DTI gr∗Corresponding author.ant. E-mail addresses: firstname.lastname@example.org (D. Boley), email@example.com (G. Ranjan), firstname.lastname@example.org (Z.-L. Zhang).
- Commute times
- Directed graphs
- Graph Laplacians
- Wireless networks