A Semidefinite Program for Structured Blockmodels
This work addresses the need for flexible modeling in network analysis, offering a method applicable to various blockmodel instances, though it appears incremental as it builds on existing semidefinite programming approaches for community detection.
The authors tackled the problem of extending semidefinite programming methods from community detection to more general structured blockmodels, such as non-assortative networks and overlapping communities, by developing a tailored semidefinite program that achieves label recovery in sparse settings and provides an oracle inequality for non-blockmodel data.
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.