TY - GEN

T1 - Random walks on digraphs, the generalized digraph laplacian and the degree of asymmetry

AU - Li, Yanhua

AU - Zhang, Zhi Li

PY - 2010/12/1

Y1 - 2010/12/1

N2 - In this paper we extend and generalize the standard random walk theory (or spectral graph theory) on undirected graphs to digraphs. In particular, we introduce and define a (normalized) digraph Laplacian matrix, and prove that 1) its Moore-Penrose pseudo-inverse is the (discrete) Green's function of the digraph Laplacian matrix (as an operator on digraphs), and 2) it is the normalized fundamental matrix of the Markov chain governing random walks on digraphs. Using these results, we derive new formula for computing hitting and commute times in terms of the Moore-Penrose pseudo-inverse of the digraph Laplacian, or equivalently, the singular values and vectors of the digraph Laplacian. Furthermore, we show that the Cheeger constant defined in [6] is intrinsically a quantity associated with undirected graphs. This motivates us to introduce a metric - the largest singular value of Δ := (ℒ̃ - ℒ̃T)/2 - to quantify and measure the degree of asymmetry in a digraph. Using this measure, we establish several new results, such as a tighter bound (than that of Fill's in [9] and Chung's in [6]) on the Markov chain mixing rate, and a bound on the second smallest singular value of ℒ̃.

AB - In this paper we extend and generalize the standard random walk theory (or spectral graph theory) on undirected graphs to digraphs. In particular, we introduce and define a (normalized) digraph Laplacian matrix, and prove that 1) its Moore-Penrose pseudo-inverse is the (discrete) Green's function of the digraph Laplacian matrix (as an operator on digraphs), and 2) it is the normalized fundamental matrix of the Markov chain governing random walks on digraphs. Using these results, we derive new formula for computing hitting and commute times in terms of the Moore-Penrose pseudo-inverse of the digraph Laplacian, or equivalently, the singular values and vectors of the digraph Laplacian. Furthermore, we show that the Cheeger constant defined in [6] is intrinsically a quantity associated with undirected graphs. This motivates us to introduce a metric - the largest singular value of Δ := (ℒ̃ - ℒ̃T)/2 - to quantify and measure the degree of asymmetry in a digraph. Using this measure, we establish several new results, such as a tighter bound (than that of Fill's in [9] and Chung's in [6]) on the Markov chain mixing rate, and a bound on the second smallest singular value of ℒ̃.

UR - http://www.scopus.com/inward/record.url?scp=78650891188&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650891188&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18009-5_8

DO - 10.1007/978-3-642-18009-5_8

M3 - Conference contribution

AN - SCOPUS:78650891188

SN - 3642180086

SN - 9783642180088

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 74

EP - 85

BT - Algorithms and Models for the Web Graph - 7th International Workshop, WAW 2010, Proceedings

T2 - 7th International Workshop on Algorithms and Models for the Web Graph, WAW 2010

Y2 - 13 December 2010 through 14 December 2010

ER -