Exact Recovery in the Stochastic Block Model

DOI10.1109/TIT.2015.2490670zbMath1359.94047arXiv1405.3267OpenAlexW2963264680MaRDI QIDQ2977080

Emmanuel Abbe, Georgina Hall, Afonso S. Bandeira

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Applications of graph theory to circuits and networks (94C15)

Related Items (91)

Joint Alignment from Pairwise Differences with a Noisy Oracle ⋮ Estimating Mixed Memberships With Sharp Eigenvector Deviations ⋮ On Convex Hulls of Epigraphs of QCQPs ⋮ Iterative algorithm for discrete structure recovery ⋮ On the tightness of SDP relaxations of QCQPs ⋮ Bayesian community detection ⋮ 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 ⋮ Optimal Bipartite Network Clustering ⋮ Community detection with a subsampled semidefinite program ⋮ The Ratio-Cut Polytope and K-Means Clustering ⋮ Unnamed Item ⋮ Frequentist validity of Bayesian limits ⋮ Exact recovery of community detection in \(k\)-partite graph models with applications to learning electric potentials in electric networks ⋮ Local law and Tracy-Widom limit for sparse stochastic block models ⋮ Optimal rates for community estimation in the weighted stochastic block model ⋮ Probably certifiably correct \(k\)-means clustering ⋮ Spectral and structural properties of random interdependent networks ⋮ Convexified modularity maximization for degree-corrected stochastic block models ⋮ Joint Community Detection and Rotational Synchronization via Semidefinite Programming ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ \(k\)-median: exact recovery in the extended stochastic ball model ⋮ Efficient joint object matching via linear programming ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ Community detection in the sparse hypergraph stochastic block model ⋮ Fast Network Community Detection With Profile-Pseudo Likelihood Methods ⋮ A unified approach to synchronization problems over subgroups of the orthogonal group ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient, certifiably optimal clustering with applications to latent variable graphical models ⋮ A note on probably certifiably correct algorithms ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ Mutual information for the sparse stochastic block model ⋮ An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization ⋮ A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization ⋮ Asymptotic uncertainty quantification for communities in sparse planted bi-section models ⋮ Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals ⋮ Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks ⋮ Community Detection in Censored Hypergraph ⋮ Spectral norm bounds for block Markov chain random matrices ⋮ A UNIFIED COMMUNITY DETECTION ALGORITHM IN LARGE-SCALE COMPLEX NETWORKS ⋮ Asymptotic mutual information for the balanced binary stochastic block model ⋮ Step-by-step community detection in volume-regular graphs ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Recovering Structured Probability Matrices ⋮ Sparse general Wigner-type matrices: Local law and eigenvector delocalization ⋮ Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery ⋮ Detecting groups in large vector autoregressions ⋮ Unnamed Item ⋮ 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 ⋮ Community Detection and Stochastic Block Models ⋮ Clustering in block Markov chains ⋮ Statistical inference on random dot product graphs: a survey ⋮ Tightness of the maximum likelihood semidefinite relaxation for angular synchronization ⋮ Distribution-Free, Size Adaptive Submatrix Detection with Acceleration ⋮ A goodness-of-fit test for stochastic block models ⋮ Convex relaxation methods for community detection ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Robust high-dimensional factor models with applications to statistical machine learning ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ The geometry of continuous latent space models for network data ⋮ Community detection in degree-corrected block models ⋮ Unnamed Item ⋮ Network Cross-Validation for Determining the Number of Communities in Network Data ⋮ Rank Optimality for the Burer--Monteiro Factorization ⋮ Consistent nonparametric estimation for heavy-tailed sparse graphs ⋮ Learning directed acyclic graph SPNs in sub-quadratic time ⋮ Exact recovery in the hypergraph stochastic block model: a spectral algorithm ⋮ Exact recovery in the Ising blockmodel ⋮ Testing for high-dimensional geometry in random graphs ⋮ Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems ⋮ 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 ⋮ Exact Clustering of Weighted Graphs via Semidefinite Programming ⋮ Spectral clustering revisited: information hidden in the Fiedler vector ⋮ Unnamed Item ⋮ Non-unique games over compact groups and orientation estimation in cryo-EM ⋮ Non-convex exact community recovery in stochastic block model ⋮ Sharp optimal recovery in the two component Gaussian mixture model ⋮ An \({\ell_p}\) theory of PCA and spectral clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Global and individualized community detection in inhomogeneous multilayer networks ⋮ Bootstrap percolation on the stochastic block model ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model ⋮ The planted k-factor problem

This page was built for publication: Exact Recovery in the Stochastic Block Model