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

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

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)

Cited In (12)

• Approximate and exact solutions of intertwining equations through random spanning forests
• On the probe complexity of local computation algorithms
• Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
• Flow-based algorithms for local graph clustering
• Finding small sparse cuts by random walk
• Title not available (Why is that?)
• Finding sparse cuts locally using evolving sets
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Mean field analysis of personalized PageRank with implications for local graph clustering
• 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

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)