Commute times for a directed graph using an asymmetric Laplacian

被引：48

作者：

Boley, Daniel ^{[1
]}

Ranjan, Gyan ^{[1
]}

Zhang, Zhi-Li ^{[1
]}

机构：

[1] Univ Minnesota, Minneapolis, MN 55455 USA

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2011年 / 435卷 / 02期

基金：

美国国家科学基金会;

关键词：

Directed graphs; Graph Laplacians; Commute times; Wireless networks; EIGENVALUES; MATRICES;

D O I：

10.1016/j.laa.2011.01.030

中图分类号：

O29 [应用数学];

学科分类号：

070104 [应用数学];

摘要：

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. (C) 2011 Elsevier Inc. All rights reserved.

引用

页码：224 / 242

页数：19