Laplacians and the Cheeger inequality for directed graphs
Laplacians and the Cheeger inequality for directed graphs
复制标题
DOI：
10.1007/s00026-005-0237-z
复制
发表时间：
2005-04-01
影响因子：
0.5
通讯作者：
Chung, Fan
中科院分区：
文献类型：
--
作者：
Chung, Fan
我们考虑有向图的拉普拉斯算子，并检验它们的特征值。引入了有向图中循环的概念及其与瑞利商的联系。然后我们定义了Cheeger常数并建立了有向图的Cheeger不等式。这些关系可以用来处理在研究不可逆马尔可夫链时经常出现的各种问题，包括收敛速度的限定和比较定理的推导。
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.