随机块模型

随机块模型（stochastic block model，SBM）把顶点分成若干组，并让一对顶点的连边概率只依赖它们的组别。给定组别后，各条边独立生成。它既可描述组内密集的社群，也可描述组间密集的二部式关系；“分块”并不自动要求对角概率较大。

取五个顶点，前三个属于组一，后两个属于组二，概率矩阵为 $$P=\left(\begin{array}{cc}0.8& 0.2\\ 0.2& 0.5\end{array}\right).$$ 同属组一的一对以概率 $0.8$ 相连，跨组一对以 $0.2$ 相连，同属组二的一对以 $0.5$ 相连。这是教学模型的设定，不是从某个真实网络估计得到的数据。

概率赋给可能的顶点对；图中组间示意连线不表示每次抽样都出现。

条件独立的准确对象

设固定顶点集为 $\{1,\dots ,n\}$，组标签为 $z_i\in \{1,\dots ,K\}$，$P$ 为对称 $K\times K$ 矩阵、元素在 $[0,1]$。无向无自环 SBM 要求对每个 $i<j$， $$A_{ij}\mid z\sim \mathrm{Bernoulli}(P_{z_i{z}_j}),$$ 且这些上三角变量在给定 $z$ 后相互独立；再令 $A_{ji}=A_{ij},A_{ii}=0$。因此不能把整个对称矩阵的所有元素说成彼此独立。

若组 $r$ 有 $n_r$ 个顶点，该组内边数为 $\mathrm{Bin}((\genfrac{}{}{0ex}{}{n_r}{2}),P_{rr})$；两不同组间边数为 $\mathrm{Bin}(n_r{n}_s,P_{rs})$。因为这些边计数使用不重叠的独立顶点对，它们在固定标签下也相互独立。期望边数为 $$𝔼M=\sum _r(\genfrac{}{}{0ex}{}{n_r}{2})P_{rr}+\sum _{r<s}{n}_r{n}_s{P}_{rs}.$$ 主例为 $3(0.8)+6(0.2)+1(0.5)=4.1$。组一顶点期望度为 $2(0.8)+2(0.2)=2$，组二顶点为 $3(0.2)+1(0.5)=1.1$；期望度和 $3(2)+2(1.1)=8.2$，等于期望边数的二倍。

固定标签下的似然与估计

对已知组别，记某一组对有 $N_{rs}$ 个可能顶点对，观察到其中 $m_{rs}$ 条边。一个具体邻接矩阵的似然为各组对项的乘积，每项为 $$P_{rs}^{m_{rs}}(1-P_{rs}{)}^{N_{rs}-m_{rs}}.$$ 这不是仅观察边数的二项概率；后者还需乘二项式系数。最大似然估计可按组对分别求解：当 $0<m<N$ 时，对数似然导数为 $m/p-(N-m)/(1-p)$，其唯一零点为 $p=m/N$，二阶导数严格为负。$m=0$ 时最大值在零，$m=N$ 时在一；$N=0$ 时该参数没有观测信息。

假设主例实际观察到组一内部两边、跨组一边、组二内部一边。估计分别是 $2/3,1/6,1$。在原先设定参数下，这一具体图的概率为 $$0.8^2(0.2)\cdot 0.2(0.8{)}^5\cdot 0.5=\mathrm{0.004194304.}$$ 最后估计一是一个顶点对的边界估计，不足以证明真实组二内部概率必为一。

变式。 如果矩阵每个元素都等于 $p$，模型退化为G(n,p)，边数据不再携带区分组标签的信息。交换组号并同时交换矩阵行列也不改变同一图的分布，所以潜在标签至少具有重命名的不唯一性。

标签若本身随机且未被条件化，边一般不再联合独立。例如三点各独立等概率取两个标签，设同组必连、异组必不连。每条边出现概率一半，但三条边全出现要求三标签相同，概率为 $1/4$，并非独立边模型的 $1/8$。因此“给定标签独立”和“没有标签信息时仍独立”必须分开。标准 SBM 还使同组顶点具有相同的期望度模式；若同组内度差异很大，需检查这种假设或考虑加入顶点效应的扩展。