期刊
ANNALS OF COMBINATORICS
卷 9, 期 1, 页码 1-19出版社
BIRKHAUSER VERLAG AG
DOI: 10.1007/s00026-005-0237-z
关键词
eigenvalues; Laplacian; circulation; the Cheeger inequality; random walks; Markov chains; comparison theorems
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据