Exact Recovery in the Stochastic Block Model
From MaRDI portal
Publication:2977080
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
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Applications of graph theory to circuits and networks (94C15)
Related Items
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
