Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log*|V|) time
Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log*|V|) time
复制标题
在 O(|E|log*|V|) 时间内恢复超出 KestenâStigum 阈值的隐藏社区
DOI：
10.1017/jpr.2018.22
复制
发表时间：
2018
影响因子：
1
通讯作者：
Xu, Jiaming
中科院分区：
文献类型：
--
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
社区检测被认为是一个随机块模型图的n个顶点，K个顶点在种植社区，边缘概率p的顶点对都在社区，和边缘概率q的其他顶点对。本文主要研究了在次线性区域n1-o（1）≤ K ≤ o（n）中，平均有o（K）个错误分类顶点的图G上的社区弱恢复问题.关键参数是有效信噪比λ = K2（p-q）2 /（（n-K）q），其中λ = 1对应于Kesten-Stigum阈值。我们证明了，如果λ > 1 / e，超过Kesten-Stigum阈值1 /e，则置信传播（BP）算法实现弱恢复。BP算法只需运行log*n + O（1）次迭代，总时间复杂度为O（|E| log*n），其中log*n是n的迭代对数。相反，如果λ ≤ 1 / e，则没有局部算法可以渐近优于平凡随机猜测。此外，一个线性的消息传递算法，对应于应用幂迭代的非回溯矩阵的图被证明达到弱恢复当且仅当λ > 1。此外，BP算法可以与线性时间投票过程相结合，以实现对所有K ≥（n / logn）（ρBP + o（1））的精确恢复（以高概率正确分类所有顶点）的信息限制，其中ρBP是p / q的函数。
Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime n1-o(1) ≤ K ≤ o(n). A critical parameter is the effective signal-to-noise ratio λ = K2(p - q)2 / ((n - K)q), with λ = 1 corresponding to the Kesten–Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if λ > 1 / e, beyond the Kesten–Stigum threshold by a factor of 1 / e. The BP algorithm only needs to run for log*n + O(1) iterations, with the total time complexity O(|E|log*n), where log*n is the iterated logarithm of n. Conversely, if λ ≤ 1 / e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if λ > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K ≥ (n / logn) (ρBP + o(1)), where ρBP is a function of p / q.
登录
查看更多内容
DOI：
10.1002/1098-2418(200103)18:2
发表时间：
1999-08
期刊：
--
影响因子：
--
作者：
A. Condon;R. Karp
通讯作者：
A. Condon;R. Karp
在稀疏图中找到一个社区
影响因子：
1.6
作者：
A. Montanari
通讯作者：
A. Montanari
通过消息传递进行子矩阵定位
影响因子：
6
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming
影响因子：
2.5
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming
在线性时间内寻找隐藏的派系
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
D. Ron;U. Feige
通讯作者：
U. Feige