Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
复制标题
DOI：
10.1109/tit.2016.2546280
复制
发表时间：
2016-05-01
影响因子：
2.5
通讯作者：
Xu, Jiaming
中科院分区：
文献类型：
--
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
二元对称随机块模型处理由 n 个顶点组成的随机图，该图被划分为两个大小相等的簇，使得每对顶点以簇内概率 p 和簇间概率 q 独立连接。在 p = a log n/n 和 q = b log n/n（对于固定 a、b 和 n -> 无穷大）的渐近状态中，我们证明最大似然估计器的半定规划松弛达到了从概率趋于 1 的图中精确恢复分区的最佳阈值，解决了 Abbe 等人的猜想。此外，我们表明半定规划松弛在包含大小与 n 成比例的单个簇的种植密集子图模型中也达到了最佳恢复阈值。
The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is independently connected with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b, and n -> infinity, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.