Computational Lower Bounds for Community Detection on Random Graphs
Bruce Hajek Yihong Wu Jiaming Xu The authors are with the Department of ECE, University of Illinois at Urbana-Champaign, Urbana, IL,
Abstract
This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph ${\mathcal{G}}(N,q)$ , where the edge probability within the community exceeds $q$ by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size $N$ grows and the graph becomes sparser according to $q=N^{-\alpha}$ , there exists a critical value of $\alpha=\frac{2}{3}$ , below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest $K$ -subgraph.
中文速览
在大型随机网络中判断是否藏有一个小而密集的子社区，是网络科学中的核心难题。本文针对这一"植入稠密子图检测"问题，以植入团（planted clique）问题的计算难度为基础假设，通过随机多项式时间归约，系统刻画了检测算法的计算复杂度如何随网络稀疏程度发生相变：当图的稀疏指数 α 小于临界值 2/3 时，存在一种组合穷举算法能发现比任何多项式时间算法都小得多的社区，而当 α 超过 2/3 时，仅凭统计边数这一线性时间操作便已达到最优检测性能。令人惊讶的是，在所有计算高效的算法中，简单的"总边数阈值"检验始终是最优的，任何多项式时间算法都无法在计算困难区域内可靠地检测出社区。这一结果不仅厘清了稀疏网络社区检测的统计–计算鸿沟，还顺带给出了稠密子图恢复和"最密 K 子图"近似问题的平均情形难度下界，对网络社区检测的算法设计和复杂度理论均有重要意义。
原文 arXiv:1406.6625;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1406.6625v3