Community Detection with Side Information via Semidefinite Programming
Community Detection with Side Information via Semidefinite Programming
复制标题
通过半定规划利用辅助信息进行社区检测
DOI：
10.1109/isit.2019.8849686
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Aria Nosratinia
中科院分区：
文献类型：
--
作者：
Mohammadjafar Esmaeili;H. Saad;Aria Nosratinia
半定规划在解决社区检测问题时是有效的和渐近最优的，但只有当观察结果是纯图形性质时，它才被研究。在本文中，我们将半定规划在社区检测中的使用扩展到具有图形和非图形组件的观察。本文研究了具有n个结点的二元截尾块模型，研究了部分显示标签对半定规划性能的影响。我们解决这个问题：部分显示标签帮助半定规划解决方案，因为他们帮助最大似然解决方案。首先，我们证明了部分揭示的标签改变了精确恢复的相变，当且仅当它们提供的信息增长不慢于log（n）。其次，我们证明了半定规划松弛的最大似然可以实现精确的恢复到最佳阈值下部分显示标签。
Semidefinite programming is known to be both efficient and asymptotically optimal in solving community detection problems, but it has been studied in this context only when observations are purely graphical in nature. In this paper, we extend the use of semidefinite programming in community detection to observations that have both a graphical and a nongraphical component. We consider the binary censored block model with n nodes and study the effect of partially revealed labels on the performance of semidefinite programming. We address the question: do partially revealed labels help the semidefinite programming solution as much as they help the maximum likelihood solutionƒ Our results are twofold. First, we show that partially revealed labels change the phase transition of exact recovery if and only if the information they provide grows no slower than Ω(log(n)). Second, we show that the semidefinite programming relaxation of maximum likelihood can achieve exact recovery down to the optimal threshold under partially revealed labels.
登录
查看更多内容
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