Convex relaxation methods for community detection
From MaRDI portal
Publication:2038282
DOI10.1214/19-STS715MaRDI QIDQ2038282
Publication date: 6 July 2021
Published in: Statistical Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.00315
robustnessweak consistencystrong consistencycommunity detectionsemidefinite programdegree correction
Related Items
Joint Community Detection and Rotational Synchronization via Semidefinite Programming, \(k\)-median: exact recovery in the extended stochastic ball model, Community Detection in General Hypergraph Via Graph Embedding, Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates, Efficient, certifiably optimal clustering with applications to latent variable graphical models, Partial recovery bounds for clustering with the relaxed \(K\)-means, Global and individualized community detection in inhomogeneous multilayer networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Consistency thresholds for the planted bisection model
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Guaranteed clustering and biclustering via semidefinite programming
- Reconstruction and estimation in the planted partition model
- Spectral clustering and the high-dimensional stochastic blockmodel
- Community detection in sparse networks via Grothendieck's inequality
- Probably certifiably correct \(k\)-means clustering
- A proof of the block model threshold conjecture
- On semidefinite relaxations for the block model
- Random Laplacian matrices and convex relaxations
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Convexified modularity maximization for degree-corrected stochastic block models
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Spectral redemption in clustering sparse networks
- Phase transitions in semidefinite relaxations
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Exact Recovery in the Stochastic Block Model
- Improved Graph Clustering
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Community Detection and Stochastic Block Models
- A Simple SVD Algorithm for Finding Hidden Partitions
- Exponential Error Rates of SDP for Block Models: Beyond Grothendieck’s Inequality
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- How well do local algorithms solve semidefinite programs?
- Clustering of sparse data via network communities—a prototype study of a large online market
- Community detection thresholds and the weak Ramanujan property
- Spectral techniques applied to sparse random graphs
- Semidefinite programs on sparse random graphs and their application to community detection
- How robust are reconstruction thresholds for community detection?
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Absolutely summing operators in $ℒ_{p}$-spaces and their applications
