Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile

DOI10.1137/16M1079816zbMath1362.05082MaRDI QIDQ5737813

Tsz Chiu Kwok, Yin Tat Lee, Lap Chi Lau

Publication date: 30 May 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

random walksCheeger's inequalityspectral graph theorygraph expansion

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Random walks and local cuts in graphs
• Eigenvalues and expanders
• Evolving sets, mixing and heat kernel bounds
• Faster mixing via average conductance
• A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
• Finding Small Sparse Cuts by Random Walk
• Subexponential Algorithms for Unique Games and Related Problems
• Expander graphs and their applications
• Finding sparse cuts locally using evolving sets
• Blocking Conductance and Mixing in Random Walks
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Many sparse cuts via higher eigenvalues
• Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm
• Improved Cheeger's inequality
• Optimal numberings and isoperimetric problems on graphs

This page was built for publication: Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile