TY - JOUR
T1 - Digraph Laplacian and the Degree of Asymmetry
AU - Li, Yanhua
AU - Zhang, Zhi Li
N1 - Publisher Copyright:
© Taylor and Francis Group, LLC.
PY - 2012/1/1
Y1 - 2012/1/1
N2 - In this paper we extend and generalize the standard spectral graph theory (or random-walk theory) on undirected graphs to digraphs. In particular, we introduce and define a normalized digraph Laplacian (Diplacian for short) Γ for digraphs, and prove that (1) its Moore–Penrose pseudoinverse is the discrete Green’s function of the Diplacian 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 a new formula for computing hitting and commute times in terms of the Moore–Penrose pseudoinverse of the Diplacian, or equivalently, the singular values and vectors of the Diplacian. Furthermore, we show that the Cheeger constant defined in[Chung 05] is intrinsically a quantity associated with undirected graphs. This motivates us to introduce a metric, the largest singular value of the skewed Laplacian ∇ = (Γ − Γ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 in[Chung 05] 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 spectral graph theory (or random-walk theory) on undirected graphs to digraphs. In particular, we introduce and define a normalized digraph Laplacian (Diplacian for short) Γ for digraphs, and prove that (1) its Moore–Penrose pseudoinverse is the discrete Green’s function of the Diplacian 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 a new formula for computing hitting and commute times in terms of the Moore–Penrose pseudoinverse of the Diplacian, or equivalently, the singular values and vectors of the Diplacian. Furthermore, we show that the Cheeger constant defined in[Chung 05] is intrinsically a quantity associated with undirected graphs. This motivates us to introduce a metric, the largest singular value of the skewed Laplacian ∇ = (Γ − Γ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 in[Chung 05] 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=84924168806&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84924168806&partnerID=8YFLogxK
U2 - 10.1080/15427951.2012.708890
DO - 10.1080/15427951.2012.708890
M3 - Article
AN - SCOPUS:84924168806
SN - 1542-7951
VL - 8
SP - 381
EP - 401
JO - Internet Mathematics
JF - Internet Mathematics
IS - 4
ER -