Laplacians and the Cheeger Inequality for Directed Graphs |
| |
Authors: | Fan Chung |
| |
Institution: | (1) University of California, San Diego, La Jolla, CA 92093-0112, USA |
| |
Abstract: | 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.Received September 8, 2004 |
| |
Keywords: | 05C20 05C50 15A42 60J05 |
本文献已被 SpringerLink 等数据库收录! |
|