B0782
Title: A semidefinite program for structured blockmodels
Authors: David Choi - Carnegie Mellon (United States) [presenting]
Abstract: Semidefinite programs (SDP) have been intensely studied for a particular class of the stochastic blockmodel, which exhibits assortative connectivity and corresponds to community detection. However, there exist blockmodels outside of this class for which the known SDP formulation is not applicable, and it is of interest to consider whether this is an inherent limitation to the semidefinite programming approach, or if alternate formulations exist. We present a family of semidefinite programs that can be tailored to such 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 known (though not the best known) results for community detection. When the blockmodel exhibits symmetry or label-switching ambiguities, the computation time the SDP can be significantly reduced by parameterizing out the non-identifiable subspace, using a concept known in combinatorics as an association scheme.
