A Semidefinite Program for Structured Blockmodels
arXiv:1611.05407
Abstract
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 to other instances of the blockmodel, such as non-assortative networks and overlapping communities. We establish label recovery in sparse settings, with conditions that are analogous to recent results for community detection. In settings where the data is not generated by a blockmodel, we give an oracle inequality that bounds excess risk relative to the best blockmodel approximation. Simulations are presented for community detection, for overlapping communities, and for latent space models.
References in corpus (9)
- Stochastic blockmodels and community structure in networks
- Spectral redemption: clustering sparse networks
- Matrix estimation by Universal Singular Value Thresholding
- Stochastic Block Models and Reconstruction
- Achieving Optimal Misclassification Proportion in Stochastic Block Model
- Detecting Overlapping Communities in Networks Using Spectral Methods
- On semidefinite programming relaxations of the traveling salesman problem
- Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
- Statistical clustering of temporal networks through a dynamic stochastic block model