A semidefinite program for unbalanced multisection in the stochastic block model
We propose a semidefinite programming (SDP) algorithm for community detection in the stochastic block model, a popular model for networks with latent community structure. We prove that our algorithm achieves exact recovery of the latent communities, up to the information-theoretic limits determined by Abbe and Sandon (2015). Our result extends prior SDP approaches by allowing for many communities of different sizes. By virtue of a semidefinite approach, our algorithms succeed against a semirandom variant of the stochastic block model, guaranteeing a form of robustness and generalization. We further explore how semirandom models can lend insight into both the strengths and limitations of SDPs in this setting.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Multisection in the Stochastic Block Model using Semidefinite Programming
We consider the problem of identifying underlying community-like structures in graphs. Towards this end we study the Stochastic Block Model (SBM) on $k$-clusters: a random model on $n=km$ vertices, partitioned in $k$ equ…
Open-Ended Question AnsweringStochastic Block ModelCommunity Detection with a Subsampled Semidefinite Program
Semidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. However, semidefinite programs are often slow in practice, so …
ClusteringCommunity DetectionStochastic Block ModelA Semidefinite Program for Structured Blockmodels
Semidefinite programs have recently been developed for the problem of community detection, which may be viewed as a special case of the stochastic blockmodel. Here, we develop a semidefinite program that can be tailored …
Community DetectionPerformance of a community detection algorithm based on semidefinite programming
The problem of detecting communities in a graph is maybe one the most studied inference problems, given its simplicity and widespread diffusion among several disciplines. A very common benchmark for this problem is the s…
Community DetectionStochastic Block ModelAchieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recoverin…
Community DetectionStochastic Block Model