可检测性阈值

问题：结构存在，但能找到吗

H3 说随机网络没有社团。反过来问：如果网络确实由含社团的模型生成，但社团之间的差别很弱，算法能不能把它找出来？答案是：存在一个相变式的阈值，低于它时，任何算法都无法以优于随机猜测的准确率恢复真实分组——不是算法不够好，而是信息本身已不足。

稀疏 SBM 的阈值

考虑 $q$ 个等大组的种植划分模型，组内连边概率 $c_{\text{in}}/n$、组间 $c_{\text{out}}/n$，平均度 $c=[c_{\text{in}}+(q-1)c_{\text{out}}]/q$ 为常数（稀疏极限）。Decelle、Krzakala、Moore 与 Zdeborová（2011）用统计物理的方法证明：

几点含义：

• 阈值低于“社团看起来存在”的直觉标准：即使 $c_{\text{in}}>c_{\text{out}}$，组内连边多于组间连边，只要差距不足 $q\sqrt c$，社团结构就无法从网络中恢复。例如 $q=2$、$c=5$ 时，阈值为 $\Delta c=2\sqrt5\approx4.47$，即 $c_{\text{in}}\approx7.2$、$c_{\text{out}}\approx2.8$——组内连边比组间多一倍以上，仍然处在不可检测的边缘。
• 平均度越大，越容易检测：阈值与 $\sqrt c$ 成正比，而 $c_{\text{in}}-c_{\text{out}}$ 可以与 $c$ 同量级增长，所以稠密网络中的社团更容易被检测到。这对稀疏的生物网络（如实验测得的 PPI 网络）是一个提醒：观测到的边越少，能可靠识别的社团结构就越粗。
• $q\ge5$ 时存在“困难区”：在阈值之上的一段参数范围内，信息论上可以检测，但目前已知的多项式时间算法做不到；$q\le4$ 时阈值处是连续相变，不存在这一困难区。

哪些算法能达到阈值

置信传播、基于非回溯矩阵或 Bethe Hessian 的谱方法可以一直工作到阈值（Krzakala 等 2013）；基于邻接矩阵、拉普拉斯矩阵或模块度矩阵的普通谱方法，在稀疏网络中会因为特征向量局域化在高度节点上而提前失效。Nadakuditi 与 Newman（2012）用随机矩阵理论分析了谱方法的可检测转变。在代码示例中，$q=2$、$c=5$、$n=4000$ 的种植划分网络上，Bethe Hessian 恢复的重叠度（0 为随机猜测、1 为完全恢复）在 $\Delta c/2\sqrt c=0.9$ 时约为 0.05，1.1 时约为 0.27，1.5 时约为 0.79，与理论阈值 $\Delta c/2\sqrt c=1$ 吻合；有限规模下阈值附近的转变会被抹平。