arXiv:2601.16427stat.MLcs.LG2026-01

提出新方法实现稀疏有向网络的精确社区发现,突破传统谱方法局限。

Perfect Clustering for Sparse Directed Stochastic Block Models

  • 通过邻域平滑估计有向概率矩阵,避免谱分解在稀疏非对称网络中的失效
  • 理论证明在弱稀疏与分离条件下可实现所有社区标签的精确恢复
  • 适用于社区数增长、网络高度稀疏且有向性强的场景,适合网络分析研究者

稀疏有向随机块模型(SBMs)中的精确社区恢复问题在无向情形下已有较好理解,但在有向和稀疏网络中仍不充分。现有谱方法在非对称、低度情形下缺乏稳定性,非谱方法多集中于无向或稠密情形。本文提出一种全非谱的两阶段社区检测方法,首先使用针对非对称结构设计的邻域平滑方案估计有向概率矩阵,再对估计行进行K-均值聚类,规避了在稀疏非对称网络中使用特征或奇异值分解的限制。主要理论贡献为:通过新论证控制非对称邻域并分离入度与出度影响,获得平滑估计器的统一行级集中界。该结果表明,在允许γ_n→0且K_n→∞的温和稀疏与分离条件下,社区标签可几乎必然精确恢复。模拟实验显示,在高有向性、稀疏且非对称的块结构下,该方法性能稳定,优于现有有向谱方法与评分法。据我们所知,这是首个针对此类非谱邻域平滑方法在稀疏有向设置下的精确恢复保证。

原文摘要 · Abstract (English)

Exact recovery in stochastic block models (SBMs) is well understood in undirected settings, but remains considerably less developed for directed and sparse networks, particularly when the number of communities diverges. Spectral methods for directed SBMs often lack stability in asymmetric, low-degree regimes, and existing non-spectral approaches focus primarily on undirected or dense settings. We propose a fully non-spectral, two-stage procedure for community detection in sparse directed SBMs with potentially growing numbers of communities. The method first estimates the directed probability matrix using a neighborhood-smoothing scheme tailored to the asymmetric setting, and then applies $K$-means clustering to the estimated rows, thereby avoiding the limitations of eigen- or singular value decompositions in sparse, asymmetric networks. Our main theoretical contribution is a uniform row-wise concentration bound for the smoothed estimator, obtained through new arguments that control asymmetric neighborhoods and separate in- and out-degree effects. These results imply the exact recovery of all community labels with probability tending to one, under mild sparsity and separation conditions that allow both $γ_n \to 0$ and $K_n \to \infty$. Simulation studies, including highly directed, sparse, and non-symmetric block structures, demonstrate that the proposed procedure performs reliably in regimes where directed spectral and score-based methods deteriorate. To the best of our knowledge, this provides the first exact recovery guarantee for this class of non-spectral, neighborhood-smoothing methods in the sparse, directed setting.

社区发现有向网络稀疏图非谱方法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。