Finding sparse cuts locally using evolving sets

DOI10.1145/1536414.1536449MaRDI QIDQ5172717zbMATH OpenOpenAlexFDO

Authors Reid Andersen, Yuval Peres

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

evolving setsgraph partitioninglocal algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• Almost optimal local graph clustering using evolving sets
• Finding small sparse cuts by random walk
• Using PageRank to Locally Partition a Graph
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Flow-based algorithms for local graph clustering

Cited in

(22)

• Beyond good partition shapes: an analysis of diffusive graph partitioning
• Local algorithms for sparse spanning graphs
• Can we locally compute sparse connected subgraphs?
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• The Small Community Phenomenon in Networks: Models, Algorithms and Applications
• Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
• Constructing near spanning trees with few local inspections
• Finding small sparse cuts by random walk
• Almost optimal local graph clustering using evolving sets
• Sparse Cut Projections in Graph Streams
• Communities, Random Walks, and Social Sybil Defense
• scientific article; zbMATH DE number 7626762 (Why is no real title available?)
• Quantum walk sampling by growing seed sets
• On solving linear systems in sublinear time
• Simulating random walks on graphs in the streaming model
• Local flow partitioning for faster edge connectivity
• Learning by unsupervised nonlinear diffusion
• Flow-based algorithms for local graph clustering
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
• Local community detection by random walk on hypergraphs
• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• Reconstructing Markov processes from independent and anonymous experiments

This page was built for publication: Finding sparse cuts locally using evolving sets

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