• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Exact Recovery in the Stochastic Block Model
【24h】

Exact Recovery in the Stochastic Block Model

机译：随机块模型中的精确恢复

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The stochastic block model with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behavior. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability within clusters and across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower bounds on the scaling of to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if and are constant (with ), recovering the communities with high probability is possible if and is impossible if . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest that it may achieve the threshold. An efficient algorithm that succeeds all the way down to the threshold is also o- tained using a partial recovery algorithm combined with a local improvement procedure.
机译：具有两个社区的随机块模型或等效的种植二等分模型是一种流行的随机图模型，具有集群行为。在对称情况下，图具有两个大小相等的簇，并且顶点在簇内和簇之间以概率连接。在过去的二十年中，统计学和计算机科学领域的大量文献都集中于提供下限以确保精确恢复。在本文中，我们确定了一个精确恢复的尖锐阈值现象：如果和恒定（具有），则如果且不可能，则以高概率恢复社区。特别地，这改善了现有界限。这也为高效的聚类算法开辟了新的视野。虽然最大似然（ML）达到了最佳阈值（根据定义），但在最坏的情况下它是NP-hard。本文提出了一种基于ML的半定规划松弛的有效算法，该算法被证明可以成功地恢复阈值附近的群落，而数值实验表明它可以达到阈值。结合部分改进算法和局部改进过程，还可以获得一种有效的算法，可以一直成功地降低到阈值。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号