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

consistency phase transition random graph threshold community detection stochastic block model planted partition model random network graph clustering minimum 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

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