Exact recovery in the binary stochastic block model with binary side information
Exact recovery in the binary stochastic block model with binary side information
复制标题
具有二进制辅助信息的二进制随机块模型中的精确恢复
DOI：
10.1109/allerton.2017.8262824
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Aria Nosratinia
中科院分区：
文献类型：
--
作者：
H. Saad;A. Abotabl;Aria Nosratinia
我们考虑一个泛化的社区检测问题，其中的推理，我们有机会获得额外的观察，携带信息（边信息）的标签，每个节点。研究了边信息的质量对二进制对称随机块模型的精确恢复相变的影响.我们证明了当α是常数或接近零时，使得log（1-α/α）= o（log（n）），边信息对精确恢复没有帮助，相变也不会改变。另一方面，当log（1-α/α）= O（log（n））时，我们证明了边信息有助于精确恢复。我们提供了对α的不同渐近区域是紧的充分必要条件。提出了一种有效的算法，结合边信息的影响，使用局部改进过程相结合的部分恢复算法。充分条件推导出精确恢复下，这种有效的算法。
We consider a generalization of the community detection problem, where for inference we have access to an additional observation that carries information (side information) about the label of each node. We study the effect of the quality of side information on the exact recovery phase transition of the binary symmetric stochastic block model by passing the true label through a binary symmetric channel (BSC) with crossover probability α. We show that when α is constant or approaching zero such that log(1−α/α) = o(log(n)), side information does not help exact recovery and the phase transition does not change. On the other hand, when log(1−α/α) = O(log(n)), we show that side information helps exact recovery. We provide necessary and sufficient conditions that are tight for different asymptotic regimes of α. An efficient algorithm that incorporates the effect of side information is proposed that uses a partial recovery algorithm combined with a local improvement procedure. Sufficient conditions are derived for exact recovery under this efficient algorithm.
度相关随机块模型中置信传播的 EXIT 分析
DOI：
10.1109/isit.2016.7541404
发表时间：
2016
期刊：
IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Saad, Hussein;Abotabl, Ahmed;Nosratinia, Aria
通讯作者：
Nosratinia, Aria