Exact recovery threshold in the binary censored block model
Exact recovery threshold in the binary censored block model
复制标题
二元删失块模型中的精确恢复阈值
DOI：
10.1109/itwf.2015.7360742
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Jiaming Xu
中科院分区：
文献类型：
--
作者：
B. Hajek;Yihong Wu;Jiaming Xu
给定一个具有n个顶点的背景图，二分删失区块模型假设顶点被划分成两个簇，并且如果两个端点在同一簇中，则用来自BERN(1-ε)或来自BERN(ε)的标签随机地标记每条边，其中εE[0，1/2]是固定常数。对于边概率p=a logn/n且a固定的ErdóS-Rényi图，我们证明了极大似然估计的半定规划松弛达到了从标号图精确恢复划分的最优阈值a(√1-ε-√ε)2>；1，且概率趋于1。对于度尺度为对数n的随机正则图，我们证明了半定规划松弛也达到了最优恢复阈值ad(bern(1/2)IIbern(ε))>；1，其中D表示Kullback-Leibler散度。
Given a background graph with n vertices, the binary censored block model assumes that vertices are partitioned into two clusters, and every edge is labeled independently at random with labels drawn from Bern(1 - ε) if two endpoints are in the same cluster, or from Bern(ε) otherwise, where ε E [0, 1/2] is a fixed constant. For Erdós-Rényi graphs with edge probability p = a log n/n and fixed a, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold a(√1 - ε - √ε)2 > 1 for exactly recovering the partition from the labeled graph with probability tending to one as n oo. For random regular graphs with degree scaling as a log n, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold aD(Bern(1/2)IIBern(ε)) > 1, where D denotes the Kullback-Leibler divergence.