Digraph Laplacian and the Degree of Asymmetry

Yanhua Li, Zhi Li Zhang

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

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 Γ.

Original languageEnglish (US)
Pages (from-to)381-401
Number of pages21
JournalInternet Mathematics
Volume8
Issue number4
DOIs
StatePublished - Jan 1 2012

Bibliographical note

Funding Information:
This work was supported in part by National Science Foundation grants CNS-0905037 and CNS-1017647, the DTRA grant HDTRA1-09-1-0050, and a University of Minnesota DTI grant. A preliminary version of the results in this paper appeared in [Li and Zhang 10b].

Fingerprint Dive into the research topics of 'Digraph Laplacian and the Degree of Asymmetry'. Together they form a unique fingerprint.

Cite this