随机块模型与统计推断

从“找划分”到“拟合模型”

模块度最大化问的是“哪个划分使某个分数最高”；随机块模型（stochastic block model, SBM）问的是“什么样的分组最可能生成了观测到的网络”。SBM 最早由 Holland、Laskey 与 Leinhardt（1983）在社会网络分析中提出，后来成为社团发现中统计推断方法的基础（Peixoto 2019 的综述）。

最简单的特例是种植划分模型（planted partition model）：$B$ 个等大的组，组内连边概率 $p_{\text{in}}$，组间 $p_{\text{out}}$。它是检验算法和研究可检测性的标准模型。

度修正随机块模型

标准 SBM 中同组节点的期望度相同，而真实网络的度分布高度异质。Karrer 与 Newman（2011）发现，用标准 SBM 拟合空手道网络时，最大似然的二分并不是两派，而是把少数高度节点和其余低度节点分开——模型只能用“组”来解释度的差异。他们提出度修正 SBM（degree-corrected SBM, DC-SBM）： $$A_{ij}\sim \text{Poisson}\left(\theta_i\theta_j\,\omega_{b_ib_j}\right),$$ 节点参数 $\theta_i$ 刻画节点自身的“活跃度”，$\omega_{rs}$ 刻画组间的连接倾向。用最大似然消去 $\theta$ 与 $\omega$ 后，只剩下依赖划分的目标函数（推导见数学推导与算法）： $$\mathcal L_{\text{SBM}}=\sum_{rs}m_{rs}\ln\frac{m_{rs}}{n_rn_s},\qquad \mathcal L_{\text{DC}}=\sum_{rs}m_{rs}\ln\frac{m_{rs}}{\kappa_r\kappa_s},$$ $m_{rs}$ 为组 $r$、$s$ 之间的边数（$r=s$ 时计两次），$n_r$ 为组的节点数，$\kappa_r$ 为组内节点度之和。在空手道网络上，DC-SBM 的最大似然二分与两派分裂基本一致（代码示例中只与真实两派差 2 个节点）。

与模块度的关系：Newman（2016）证明，带分辨率参数 $\gamma$ 的模块度最大化，等价于一个特殊的“种植划分 DC-SBM”的最大似然估计——所有组内连接倾向都等于 $\omega_{\text{in}}$、组间都等于 $\omega_{\text{out}}$，且 $$\gamma=\frac{\omega_{\text{in}}-\omega_{\text{out}}}{\ln\omega_{\text{in}}-\ln\omega_{\text{out}}}.$$ 这给 $\gamma$ 提供了统计解释，也说明模块度隐含了“所有社团同样紧密”的强假设。

模型选择：组数 $B$ 怎么定

最大似然有一个根本问题：组数越多，似然越大（每个节点自成一组时最大），所以不能直接用似然选择 $B$。常见解决办法：

• 贝叶斯推断与最小描述长度（Peixoto 2017, 2019）：给参数加上无信息先验，计算划分的后验概率 $P(\mathbf b\mid A)\propto P(A\mid\mathbf b)P(\mathbf b)$。$-\ln P(A,\mathbf b)$ 可以解释为用模型“压缩”网络所需的描述长度：数据部分 $-\ln P(A\mid\mathbf b)$ 随组数增加而减小，模型部分 $-\ln P(\mathbf b)$ 随组数增加而增大，二者之和自动权衡复杂度与拟合度。在没有结构的随机网络上，后验最可能的结果是 $B=1$——这与模块度在随机网络上也能找到高 $Q$ 的行为形成对照。
• 嵌套 SBM（Peixoto 2014）：把组本身再看作一个网络的节点，用更高一层的 SBM 描述组间连接矩阵，逐层向上，形成层次结构。Peixoto（2013）指出，非层次 SBM 用描述长度做模型选择时，可检测的组数上限约随 $\sqrt N$ 增长——这也是一种分辨率极限；嵌套的先验大大放宽了这一上限，使大网络中的小组仍可被识别。
• 后验不确定性：贝叶斯方法不只给一个“最优”划分，还可以对后验分布抽样，得到每个节点属于各组的边际概率，以及划分的整体不确定性。

SBM 的扩展

• 混合成员 SBM（Airoldi 等 2008）：每个节点有一个在各组上的隶属概率向量，可用于重叠社团；
• 加权、多层与时变 SBM：边权、多种关系或多个时间层由相应的分布描述，适用于共表达、多组学和纵向脑网络数据；
• 带元数据的 SBM：把节点注释作为额外信息纳入模型，可以检验“元数据与网络结构是否相关”，而不是默认二者一致。