Almost optimal local graph clustering using evolving sets

DOI10.1145/2856030MaRDI QIDQ3177772zbMATH OpenOpenAlexFDO

Authors Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2856030

zbMATH Keywords

Cheeger's inequalitylocal graph clusteringrandom walkssparsest cut

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) Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• Finding sparse cuts locally using evolving sets
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Finding small sparse cuts by random walk

Cited in

(12)

• Mean field analysis of personalized PageRank with implications for local graph clustering
• Approximate and exact solutions of intertwining equations through random spanning forests
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
• Finding small sparse cuts by random walk
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• On the probe complexity of local computation algorithms
• Statistical guarantees for local graph clustering
• Finding sparse cuts locally using evolving sets
• Flow-based algorithms for local graph clustering
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance

This page was built for publication: Almost optimal local graph clustering using evolving sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177772)