提出新算法，在接近KS阈值时实现最优社区检测，且对节点干扰有强鲁棒性。
Rate-optimal community detection near the KS threshold via node-robust algorithms
- 用平方和框架改进多数投票，提升算法鲁棒性
- 在C≥Kk²logk条件下，达到最优错误率exp(−(1±o(1))C/k)
- 首次在多项式时间内逼近KS阈值，适合高精度社区发现场景
研究对称k-随机块模型中的社区检测问题，其中n个节点均分为k个簇，簇内与簇间连接概率分别为p和q。本文提出一种多项式时间算法，在C = (√(pn) − √(qn))² ≥ K k² log k（K为常数）条件下，实现了最小最大错误率exp(−(1±o(1))C/k)，逼近凯斯滕-斯蒂格姆（KS）阈值仅差log k因子。该误差率在对抗者破坏最多η ≤ exp(−(1±o(1))C/k)比例节点时仍成立。此前最优方法要么计算不可行，要么需更强假设C ≥ K k³，或在鲁棒设置下需远强于C ≥ K k¹⁰²的条件。本工作首次在两种情形下均实现近KS阈值的最优率。关键技术：（1）基于平方和框架的鲁棒多数投票；（2）设计新型图二分算法，使初始估计错误率降至1/poly(k)。
原文摘要 · Abstract (English)
We study community detection in the \emph{symmetric $k$-stochastic block model}, where $n$ nodes are evenly partitioned into $k$ clusters with intra- and inter-cluster connection probabilities $p$ and $q$, respectively. Our main result is a polynomial-time algorithm that achieves the minimax-optimal misclassification rate \begin{equation*} \exp \Bigl(-\bigl(1 \pm o(1)\bigr) \tfrac{C}{k}\Bigr), \quad \text{where } C = (\sqrt{pn} - \sqrt{qn})^2, \end{equation*} whenever $C \ge K\,k^2\,\log k$ for some universal constant $K$, matching the Kesten--Stigum (KS) threshold up to a $\log k$ factor. Notably, this rate holds even when an adversary corrupts an $η\le \exp\bigl(- (1 \pm o(1)) \tfrac{C}{k}\bigr)$ fraction of the nodes. To the best of our knowledge, the minimax rate was previously only attainable either via computationally inefficient procedures [ZZ15] or via polynomial-time algorithms that require strictly stronger assumptions such as $C \ge K k^3$ [GMZZ17]. In the node-robust setting, the best known algorithm requires the substantially stronger condition $C \ge K k^{102}$ [LM22]. Our results close this gap by providing the first polynomial-time algorithm that achieves the minimax rate near the KS threshold in both settings. Our work has two key technical contributions: (1) we robustify majority voting via the Sum-of-Squares framework, (2) we develop a novel graph bisection algorithm via robust majority voting, which allows us to significantly improve the misclassification rate to $1/\mathrm{poly}(k)$ for the initial estimation near the KS threshold.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。