提出新模型与判据，实现带节点属性网络的精确社区发现
Exact Recovery in the Data Block Model
- 引入切尔诺夫-电视距离刻画数据块模型的可恢复性边界
- 给出高效算法并证明该边界不可超越，理论与实践一致
- 适合关注网络社区检测与统计推断的科研人员
网络中的社区检测是机器学习与统计推断中的基础问题，广泛应用于社交网络、生物系统和通信网络。随机块模型（SBM）是研究社区结构的标准框架，而精确恢复（以高概率识别真实社区）是核心理论问题。经典结果仅基于图连通性刻画精确恢复的相变阈值，但许多现实网络包含额外信息，如节点属性或标签。本文研究数据块模型（DBM），即在SBM基础上增加节点关联数据，由Asadi、Abbe与Verdú（2017）形式化定义。我们引入切尔诺夫-电视（Chernoff--TV）距离，精确刻画了DBM的尖锐精确恢复阈值，并提出一个能达成此阈值的高效算法，同时提供匹配的反向结论，证明低于该阈值时恢复不可能。最后，模拟验证了理论结果，展示了利用顶点数据作为辅助信息在社区检测中的优势。
原文摘要 · Abstract (English)
Community detection in networks is a fundamental problem in machine learning and statistical inference, with applications in social networks, biological systems, and communication networks. The stochastic block model (SBM) serves as a canonical framework for studying community structure, and exact recovery, identifying the true communities with high probability, is a central theoretical question. While classical results characterize the phase transition for exact recovery based solely on graph connectivity, many real-world networks contain additional data, such as node attributes or labels. In this work, we study exact recovery in the Data Block Model (DBM), an SBM augmented with node-associated data, as formalized by Asadi, Abbe, and Verdú (2017). We introduce the Chernoff--TV divergence and use it to characterize a sharp exact recovery threshold for the DBM. We further provide an efficient algorithm that achieves this threshold, along with a matching converse result showing impossibility below the threshold. Finally, simulations validate our findings and demonstrate the benefits of incorporating vertex data as side information in community detection.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。