Exact Recovery by Semidefinite Programming in the Binary Stochastic Block Model with Partially Revealed Side Information
Exact Recovery by Semidefinite Programming in the Binary Stochastic Block Model with Partially Revealed Side Information
复制标题
部分揭示辅助信息的二元随机块模型中半定规划的精确恢复
DOI：
10.1109/icassp.2019.8682223
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Aria Nosratinia
中科院分区：
文献类型：
--
作者：
Mohammadjafar Esmaeili;H. Saad;Aria Nosratinia
我们提出了一种半确定规划（SDP）方法，用于存在额外非图形侧信息的图中的社区检测，并分析了相应的精确恢复阈值。社区检测问题是在二进制对称随机块模型（SBM）的背景下考虑的，侧信息以部分显示的标签的形式存在，其擦除概率为λ。结果表明，极大似然估计器的半定规划松弛可以精确地恢复到最优阈值。通过有限合成数据集的仿真验证了本文的理论发现，表明本文的渐近结果也可以解释有限n下的性能。
We propose a semidefinite programming (SDP) approach to community detection in graphs in the presence of additional non-graphical side information, and analyze the corresponding exact recovery threshold. The community detection problem is considered in the context of the binary symmetric Stochastic Block Model (SBM), and the side information is in the form of partially revealed labels with erasure probability ϵ. Our results show that the semidefinite programming relaxation of the maximum likelihood estimator can achieve exact recovery down to the optimal threshold. The theoretical findings of this paper are validated via simulations on finite synthetic data-sets, showing that the asymptotic results of this paper can also shed light on the performance at finite n.
登录
查看更多内容
DOI：
10.1109/isit.2018.8437517
发表时间：
2018
期刊：
IEEE International Symposium on Information Theory
影响因子：
--
作者：
Saad, Hussein;Nosratinia, Aria
通讯作者：
Nosratinia, Aria
带有辅助信息的信念传播用于恢复单个社区
DOI：
10.1109/isit.2018.8437840
发表时间：
2018
期刊：
International Symposium on Information Theory
影响因子：
--
作者：
Saad, Hussein;Nosratinia, Aria
通讯作者：
Nosratinia, Aria
使用辅助信息恢复单个社区
影响因子：
2.5
作者：
Saad, Hussein;Nosratinia, Aria
通讯作者：
Nosratinia, Aria
DOI：
10.1109/jstsp.2018.2834874
发表时间：
2018-10-01
影响因子：
7.5
作者：
Saad, Hussein;Nosratinia, Aria
通讯作者：
Nosratinia, Aria