Almost Optimal Local Graph Clustering Using Evolving Sets

DOI10.1145/2856030zbMath1426.05158OpenAlexW2346393863MaRDI QIDQ3177772

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

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 walksCheeger's inequalitysparsest cutlocal graph clustering

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

Related Items (5)

Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ Unnamed Item ⋮ Approximate and exact solutions of intertwining equations through random spanning forests ⋮ Mean field analysis of personalized PageRank with implications for local graph clustering ⋮ Unnamed Item

This page was built for publication: Almost Optimal Local Graph Clustering Using Evolving Sets