Almost optimal local graph clustering using evolving sets

DOI10.1145/2856030zbMATH Open1426.05158OpenAlexW2346393863MaRDI QIDQ3177772FDOQ3177772

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

random walkssparsest cutCheeger's inequalitylocal graph clustering

Mathematics Subject Classification ID

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

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)

• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Finding small sparse cuts by random walk
• scientific article; zbMATH DE number 7415091 (Why is no real title available?)
• Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
• On the probe complexity of local computation algorithms
• Mean field analysis of personalized PageRank with implications for local graph clustering
• Approximate and exact solutions of intertwining equations through random spanning forests
• Finding sparse cuts locally using evolving sets
• 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
• Flow-based algorithms for local graph clustering
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile

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)