A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
From MaRDI portal
Publication:2839169
DOI10.1137/080744888zbMath1286.68244arXiv0809.3232OpenAlexW2135512436WikidataQ56386819 ScholiaQ56386819MaRDI QIDQ2839169
Shang-Hua Teng, Daniel A. Spielman
Publication date: 4 July 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0809.3232
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81)
Related Items
A Statistical Performance Analysis of Graph Clustering Algorithms, Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance, Ergodicity Coefficients for Higher-Order Stochastic Processes, Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Vertex Nomination Between Graphs via Spectral Embedding and Quadratic Programming, Unnamed Item, Computing heat kernel PageRank and a local clustering algorithm, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Red light green light method for solving large Markov chains, PageRank Nibble on the sparse directed stochastic block model, Random walks and diffusion on networks, Iterated multilevel simulated annealing for large-scale graph conductance minimization, Multiple random walks on graphs: mixing few to cover many, Sublinear Algorithms for Local Graph-Centrality Estimation, Unnamed Item, Unnamed Item, Geometric bounds on the fastest mixing Markov chain, Network Essence: PageRank Completion and Centrality-Conforming Markov Chains, Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile, Variational perspective on local graph clustering, An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition, Unnamed Item, Local computation algorithms for graphs of non-constant degrees, Mean field analysis of personalized PageRank with implications for local graph clustering, Unnamed Item, A spectral approach to the shortest path problem, Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem, Local Flow Partitioning for Faster Edge Connectivity, Unnamed Item, A variational approach to the consistency of spectral clustering, Characterizing limits and opportunities in speeding up Markov chain mixing, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Multiscale Matrix Sampling and Sublinear-Time PageRank Computation, A survey of computational methods in protein-protein interaction networks, Unnamed Item, Compressive Sensing for Cut Improvement and Local Clustering
