简化谱算法逼近社区检测理论极限
Simplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detection
- 去掉冗余预处理，直接利用邻接矩阵谱特性
- 误差率逼近信息论下界，优于已有方法
- 适合追求高效高精度社区发现的研究者
我们在常数边密度假设下，针对两社区随机块模型（SBM）提出一种简化的谱社区检测算法。通过消除非必要预处理步骤，该方法直接利用邻接矩阵的谱特性。我们证明，该算法通过挖掘第二特征向量的特定性质，可实现更优的误差界，逼近信息论极限，显著优于现有方法。理论分析表明，其误差率紧于文献中已有结果。全面实验验证了理论发现，并展示了该简化方法的实用性。结果表明，算法简化不仅提升计算效率，还能增强性能。
原文摘要 · Abstract (English)
We propose a streamlined spectral algorithm for community detection in the two-community stochastic block model (SBM) under constant edge density assumptions. By reducing algorithmic complexity through the elimination of non-essential preprocessing steps, our method directly leverages the spectral properties of the adjacency matrix. We demonstrate that our algorithm exploits specific characteristics of the second eigenvector to achieve improved error bounds that approach information-theoretic limits, representing a significant improvement over existing methods. Theoretical analysis establishes that our error rates are tighter than previously reported bounds in the literature. Comprehensive experimental validation confirms our theoretical findings and demonstrates the practical effectiveness of the simplified approach. Our results suggest that algorithmic simplification, rather than increasing complexity, can lead to both computational efficiency and enhanced performance in spectral community detection.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。