A proof of the block model threshold conjecture
From MaRDI portal
Publication:1715062
DOI10.1007/s00493-016-3238-8zbMath1424.05272arXiv1311.4115OpenAlexW2962801026WikidataQ123278351 ScholiaQ123278351MaRDI QIDQ1715062
Allan Sly, Elchanan Mossel, Joe Neeman
Publication date: 1 February 2019
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.4115
Related Items
Testing community structure for hypergraphs, Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM), On the Complexity of Random Satisfiability Problems with Planted Solutions, Iterative algorithm for discrete structure recovery, Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model, Powerful multiple testing of paired null hypotheses using a latent graph model, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Iterative Collaborative Filtering for Sparse Matrix Estimation, Information-theoretic thresholds from the cavity method, Unnamed Item, MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass, Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks, Application of the information-percolation method to reconstruction problems on graphs, Optimal rates for community estimation in the weighted stochastic block model, Joint Community Detection and Rotational Synchronization via Semidefinite Programming, Find Your Place: Simple Distributed Algorithms for Community Detection, Outliers in spectrum of sparse Wigner matrices, Finding one community in a sparse graph, Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems, Community detection in the sparse hypergraph stochastic block model, Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs, Combinatorial statistics and the sciences, Unnamed Item, Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models, Entrywise eigenvector analysis of random matrices with low expected rank, Mutual information for the sparse stochastic block model, A compressed sensing based least squares approach to semi-supervised local cluster extraction, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Learning sparse graphons and the generalized Kesten-Stigum threshold, Community Detection in Censored Hypergraph, Unnamed Item, Step-by-step community detection in volume-regular graphs, Notes on computational-to-statistical gaps: predictions using statistical physics, Bethe states of random factor graphs, The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Optimal couplings between sparse block models, Disentangling group and link persistence in dynamic stochastic block models, Charting the replica symmetric phase, On semidefinite relaxations for the block model, Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs, Charting the replica symmetric phase, Random Laplacian matrices and convex relaxations, Statistical inference on random dot product graphs: a survey, Estimating the number of communities by spectral methods, Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects, Convex relaxation methods for community detection, Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing, Detecting a planted community in an inhomogeneous random graph, Community detection in sparse networks via Grothendieck's inequality, The structure of Gaussian minimal bubbles, Exact recovery in the hypergraph stochastic block model: a spectral algorithm, Exact recovery in the Ising blockmodel, On the computational tractability of statistical estimation on amenable graphs, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels, Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models, Phase Transition of the Reconstructability of a General Model with Different In-Community and Out-Community Mutations on an Infinite Tree, Unnamed Item, Unnamed Item, Unnamed Item, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Global and individualized community detection in inhomogeneous multilayer networks, Eigenvalues of the non-backtracking operator detached from the bulk, Graph Powering and Spectral Robustness, Compressive Sensing for Cut Improvement and Local Clustering
