Graph Partitioning via Adaptive Spectral Techniques

DOI10.1017/S0963548309990514zbMath1209.05178OpenAlexW2133361319MaRDI QIDQ3557535

Amin Coja-Oghlan

Publication date: 23 April 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548309990514

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (30)

Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator ⋮ Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information ⋮ Information-theoretic thresholds from the cavity method ⋮ A simple spectral algorithm for recovering planted partitions ⋮ Constructing uniquely realizable graphs ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ Finding one community in a sparse graph ⋮ Combinatorial statistics and the sciences ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Spectral redemption in clustering sparse networks ⋮ Learning sparse graphons and the generalized Kesten-Stigum threshold ⋮ A Simple SVD Algorithm for Finding Hidden Partitions ⋮ Asymptotic mutual information for the balanced binary stochastic block model ⋮ Step-by-step community detection in volume-regular graphs ⋮ Sparse general Wigner-type matrices: Local law and eigenvector delocalization ⋮ Reconstruction and estimation in the planted partition model ⋮ Contiguity and non-reconstruction results for planted partition models: the dense case ⋮ Community Detection and Stochastic Block Models ⋮ Recovering nonuniform planted partitions via iterated projection ⋮ On the hardness of designing public signals ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Network representation using graph root distributions ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ Consistent nonparametric estimation for heavy-tailed sparse graphs ⋮ Optimality of spectral clustering in the Gaussian mixture model ⋮ Analysis of spectral clustering algorithms for community detection: the general bipartite setting ⋮ Consistency of spectral clustering in stochastic block models ⋮ Graph Powering and Spectral Robustness

Cites Work

• Unnamed Item
• Quick approximation to matrices and applications
• The eigenvalues of random symmetric matrices
• The Metropolis algorithm for graph bisection
• Heuristics for semirandom graph problems
• Sparse quasi-random graphs
• General Partitioning on Random Graphs
• The solution of some random NP-hard problems in polynomial expected time
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• On clusterings
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Max Cut for Random Graphs with a Planted Partition
• The Largest Eigenvalue of Sparse Random Graphs
• Spectral techniques applied to sparse random graphs

This page was built for publication: Graph Partitioning via Adaptive Spectral Techniques