Consistency thresholds for the planted bisection model

DOI10.1214/16-EJP4185zbMath1336.05117arXiv1407.1591OpenAlexW2093663313MaRDI QIDQ287720

Elchanan Mossel, Allan Sly, Joe Neeman

Publication date: 23 May 2016

Published in: Electronic Journal of Probability, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1591

zbMATH Keywords

consistencyphase transitionrandom graphthresholdcommunity detectionstochastic block modelplanted partition modelrandom networkgraph clusteringminimum bisection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (45)

Iterative algorithm for discrete structure recovery ⋮ Uniform estimation in stochastic block models is slow ⋮ Optimal Bipartite Network Clustering ⋮ Community detection with a subsampled semidefinite program ⋮ Frequentist validity of Bayesian limits ⋮ Model assisted variable clustering: minimax-optimal recovery and algorithms ⋮ Optimal rates for community estimation in the weighted stochastic block model ⋮ Rate optimal Chernoff bound and application to community detection in the stochastic block models ⋮ PageRank Nibble on the sparse directed stochastic block model ⋮ Unnamed Item ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ Mutual information for the sparse stochastic block model ⋮ Asymptotic uncertainty quantification for communities in sparse planted bi-section models ⋮ Unnamed Item ⋮ Spectral norm bounds for block Markov chain random matrices ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Recovering Structured Probability Matrices ⋮ Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding ⋮ Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Maximum likelihood estimation of sparse networks with missing observations ⋮ On semidefinite relaxations for the block model ⋮ Contiguity and non-reconstruction results for planted partition models: the dense case ⋮ Random Laplacian matrices and convex relaxations ⋮ Submatrix localization via message passing ⋮ Clustering in block Markov chains ⋮ Distribution-Free, Size Adaptive Submatrix Detection with Acceleration ⋮ Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time ⋮ Convex relaxation methods for community detection ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ Community detection in degree-corrected block models ⋮ On the estimation of latent distances using graph distances ⋮ Unnamed Item ⋮ Rate-optimal graphon estimation ⋮ Community detection with dependent connectivity ⋮ Exact recovery in the hypergraph stochastic block model: a spectral algorithm ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ A spectral method for community detection in moderately sparse degree-corrected stochastic block models ⋮ Unnamed Item ⋮ Non-convex exact community recovery in stochastic block model ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ Global and individualized community detection in inhomogeneous multilayer networks ⋮ Detecting Overlapping Communities in Networks Using Spectral Methods

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Consistency thresholds for the planted bisection model