A semidefinite program for unbalanced multisection in the stochastic block model
A semidefinite program for unbalanced multisection in the stochastic block model
复制标题
随机块模型中不平衡分段的半定规划
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Alexander S. Wein
中科院分区：
文献类型：
--
作者：
William Perry;Alexander S. Wein
我们建议在随机块模型中进行社区检测的半决赛编程（SDP）算法，这是一种具有潜在社区结构网络的流行模型。我们证明，我们的算法实现了潜在社区的精确恢复，直到Abbe和Sandon确定的信息理论限制。我们的结果通过允许许多不同规模的社区来扩展先前的SDP方法。借助半决赛方法，我们的算法在随机块模型的半越野变体中取得了成功，保证了一种稳健性和概括的形式。我们进一步探讨了Semirandom模型如何在此环境中洞悉SDP的优势和局限性。
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. 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.