Convex relaxation methods for community detection

DOI10.1214/19-STS715MaRDI QIDQ2038282

Yanyan Li

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

zbMATH Keywords

robustnessweak consistencystrong consistencycommunity detectionsemidefinite programdegree correction

Mathematics Subject Classification ID

Statistics (62-XX)

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