Laplacians and the Cheeger Inequality for Directed Graphs
Annals of CombinatoricsPublished 1 April 2005
Fan Chung
Citations546
SJR quartileQ2
SJR score0.70
SNIP1.11
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
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.
Keywords
Mathematics
Matrix Analysis
22,234 Citations1985Roger A. Horn, Charles R. Johnson
COMBINATORICAEigenvalues and expanders
1,170 Citations1986Noga Alon
It is shown that a regular bipartite graph is an expanderif and only if the second largest eigenvalue of its adjacency matrix is well separated from the first.
The Annals of Applied ProbabilityGeometric Bounds for Eigenvalues of Markov Chains
886 Citations1991Persi Diaconis, Daniel W. Stroock
The Annals of Applied ProbabilityComparison Theorems for Reversible Markov Chains
424 Citations1993Persi Diaconis, Laurent Saloff‐Coste
The Annals of Applied ProbabilityEigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion Process
334 Citations1991James Allen Fill
Journal of Algebraic CombinatoricsChip-Firing Games on Directed Graphs
95 Citations1992Anders Björner, László Lovász
It is shown that for many graphs, in particular for undirected graphs, the problem whether a given position of the chips can be reached from the initial position is polynomial time solvable.