期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 62, 期 5, 页码 2788-2797出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2016.2546280
关键词
Community detection; stochastic block model; semidefinite programming; Erdos-Renyi random graph
资金
- Division of Computing and Communication Foundations [1409106, 1423088]
- College of Engineering, University of Illinois, Strategic Research Initiatives on Big-Data Analytics
- Division of Information and Intelligent Systems [1447879]
- Division of Integrative Organismal Systems [1339388]
- Simons Foundation [328025]
- U.S. Department of Defense, Office of Naval Research [N00014-14-1-0823]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1423088, 1749241, 1527105] Funding Source: National Science Foundation
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1409106] Funding Source: National Science Foundation
- Division Of Integrative Organismal Systems
- Direct For Biological Sciences [1339388] Funding Source: National Science Foundation
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [1447879] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据