Commute times for a directed graph using an asymmetric Laplacian |
| |
Authors: | Daniel Boley Gyan Ranjan |
| |
Institution: | Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USA |
| |
Abstract: | 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. |
| |
Keywords: | 05C20 05C50 05C81 94C15 |
本文献已被 ScienceDirect 等数据库收录! |
|