Laplacians and the Cheeger inequality for directed graphs

被引：306

作者：

Chung, Fan ^{[1
]}

机构：

[1] Univ Calif San Diego, La Jolla, CA 92093 USA

来源：

ANNALS OF COMBINATORICS | 2005年 / 9卷 / 01期

基金：

美国国家科学基金会;

关键词：

eigenvalues; Laplacian; circulation; the Cheeger inequality; random walks; Markov chains; comparison theorems;

D O I：

10.1007/s00026-005-0237-z

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.

引用

页码：1 / 19

页数：19

共 11 条

[1]

Aldous D., REVERSIBLE MARKOV CH

[2]

ALON N, 1986, COMBINATORICA, V6, P86

[3] Generating uniform random vectors [J].

Asci, C .

JOURNAL OF THEORETICAL PROBABILITY, 2001, 14 (02) :333-356

[4]

BASSIRI F, 1997, THESIS HARVARD U

[5]

Bojrner A., 1992, J. Algebr. Comb., V1, P305

[6]

Chung F, 1997, C BOARD MATH SCI AM

[7]

Diaconis P., 1991, Ann. Appl. Probab., P36

[8]

Diaconis P., 1993, Ann. Appl. Probab., V3, P696, DOI [10.1214/aoap/1177005359, DOI 10.1214/AOAP/1177005359]

[9]

Fill J. A., 1991, Annals of Applied Probability, V1, P62, DOI 10.1214/aoap/1177005981

[10]

HILDEBRAND M, RATES CONVERGENCE NO

← 1 2 →