随机块模型的大规模并行算法

基于摘要分析。本文研究随机块模型（Stochastic Block Model，SBM）生成图的社区精确恢复问题，提出适用于一般 s-space Massively Parallel Computation（MPC）模型的算法，主要贡献是放宽单机内存要求，并给出不同信号强度条件下的并行轮数与总空间保证。研究对象是随机图社区检测，而非状态空间模型或神经信号解码。 理论设定包含 kn 个顶点，分属 k 个大小均为 n 的社区；社区内连边概率为 p，社区间为 q，且 p>q>0。每台机器的内存满足 s=Ω(log n)。算法收集各顶点的 r 步邻域，通过比较顶点对的局部邻域统计信息进行聚类，并为此设计可并行执行的基本图操作；摘要未给出具体统计量及其实现细节。 作者报告：当 (p−q)/√p ≥ Ω̃(k^{1/2}n^{−1/2+1/(2(r−1))})、整数 r∈[3,O(log n)] 时，第一种算法可在 O(kr log_s n) 轮、Õ(m) 总空间下精确恢复全部社区，或以 Õ(km) 总空间将轮数降至 O(r log_s n)。当 (p−q)/√p ≥ Ω̃(k^{3/4}n^{−1/4}) 时，第二种算法达到 O(log_s n) 轮及 Õ(m) 总空间。这里的结果是特定 SBM 参数条件下的理论复杂度保证，不是实际数据上的 Accuracy；摘要未明确说明符号 m 的定义。 作者称，相比 Cohen-Addad 等人的 PODC’22 工作，新算法支持更一般的单机内存条件，并减弱了对 p、q、k 的要求；具体比较边界、成功概率、证明及实际运行表现尚未验证。其保证依赖等规模社区和随机连边结构，不能直接推广至真实脑连接图。材料未提供 EEG 对应机制或验证，故不据此提出 BCI 迁移效果判断；已有 EEG 相关工作尚未检索确认。