它有什么作用?
随机块模型(Stochastic Block Model, SBM)由 Holland, Laskey 和 Leinhardt 于 1983 年提出,是一种图的概率生成模型,它将节点分配给潜在的块,并参数化估计块之间的连接概率。它是社区检测、核心-边缘识别和网络分析中层次结构发现的基础方法。
方法背后的直觉
想象一个社交网络,人们聚集在不同的群体中——同事、家人、运动队——群体内部的连接比群体之间的连接更常见。随机块模型将这种直觉形式化:它假设每个节点都有一个隐藏的群组标签,并且任意两个节点之间存在边的概率仅取决于这两个节点所属的群组。拟合模型意味着找到最能解释观察到的边模式的隐藏标签。结果是对网络进行原则性、统计学上合理的块划分,而无需假设群组是密集的派系——该模型可以适应核心-边缘结构,甚至可以适应组间连接超过组内连接的异配模式。
历史学
随机块模型由 Holland, Laskey 和 Leinhardt 于 1983 年在他们的《社会网络》论文中提出,作为社会网络分析中早期块建模工作的概率泛化。在二十年间,它主要作为一种理论工具;随着 2010 年代可扩展推理算法——变分 EM 和 MCMC——的发展,它获得了实际应用。度校正 SBM 由 Karrer 和 Newman(2011)提出,以解决度异质性问题。Lee 和 Wilkinson 在 2019 年《应用网络科学》中的综述整合了扩展家族,涵盖了植入式划分模型、混合成员 SBM 和层次变体。如今,SBM 及其衍生模型是社区检测和图聚类的参考概率框架。
何时使用
当您有一个至少包含 50 个节点的网络,并且希望发现潜在的群组结构,而不假设群组必须是密集的派系时,请使用随机块模型。它适用于有向或无向图、加权或无加权图,并且适合探索性任务以及分类任务。当节点度数差异很大时,首选 DCSBM 变体。如果图的节点少于 20 个,则无法可靠地估计社区结构,应使用更简单的描述性指标。假设:块成员资格是潜在的且未被观察到;块连接矩阵在每个块对内被假定为同质的;K 必须通过 BIC 或贝叶斯因子选择,而不是任意固定。
局限与注意事项
- 需要至少约 50 个节点才能可靠地估计块;非常小的图会产生不稳定的解。
- 对于大型图,推理计算成本高昂:需要变分 EM 或 MCMC,并且不保证收敛。
- 当块内连接率不同时,基本 SBM 在块对内的同质性假设会失效——DCSBM 缓解了这一点但并未完全消除。
- 如果图的社区分离较弱,通过 BIC 或贝叶斯因子进行块选择仍可能导致欠分割或过分割。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 原则性的概率框架,允许通过 BIC 或贝ess 因子进行模型选择,避免任意参数选择。
- 可容纳各种结构模式——社区、核心-边缘、二分图和层次结构——超越了算法方法对密集派系的假设。
- 度校正变体能够处理具有异质度分布和中心节点的图,而不会扭曲块分配。
- 提供后验成员概率,实现软或不确定的节点分配,而非硬划分。
应用
- 在社会科学和自然科学的引文和合作网络中检测研究社区。
- 识别生物网络中的功能模块,例如蛋白质-蛋白质相互作用和基因共表达图。
- 在交易和金融网络中发现客户细分或欺诈团伙。
- 描述组织间或国家间贸易网络中的核心-边缘结构。
- 使用 SBM 生成的合成图作为真实数据,对其他社区检测算法进行基准测试和评估。
使用方式
使用方式
分析师指定块数量 K 的候选范围并选择一个变体:基本 SBM 假设块内同质的度分布,而度校正 SBM(Degree-Corrected SBM, DCSBM)增加了节点级别的度参数来处理中心节点和异质度序列。变体的选择取决于观察图的度分布。
给定邻接矩阵,模型使用推理算法估计块成员资格和 K×K 连接概率矩阵。对于小型到中型图,精确最大化是可行的;对于大型图,使用变分期望最大化(variational Expectation-Maximisation, 变分 EM)或马尔可夫链蒙特卡洛(Markov Chain Monte Carlo, MCMC)抽样来使推理变得可行。
块的数量 K 不是预先知道的,必须从数据中选择。首选的选择标准是贝叶斯信息准则(Bayesian Information Criterion, BIC)和贝叶斯因子,两者都惩罚模型复杂性,并选择在拟合度和简约性之间取得最佳平衡的 K。最小描述长度(minimum description length, MDL)原理是 graph-tool 实现的基础。
一旦确定了最优 K 和块分配,就检查块连接矩阵以表征结构:同配块对应于社区,异配块对应于二分图模式,混合模式对应于核心-边缘排列。如果推理算法提供后验概率,则报告节点的后验成员概率。
常见陷阱
- 任意固定 K 而非通过 BIC 或贝叶斯因子选择 K 会产生不可靠的划分——始终使用有原则的模型选择标准。
- 将基本 SBM 应用于具有异质度序列(中心节点、幂律度分布)的图会夸大块计数估计;应使用 DCSBM。
- 当后验分布分散时,将块成员资格视为确定会夸大置信度——在可用时报告不确定性。
- 将 SBM 输出与真实社区混淆:模型发现的是统计上合理的潜在结构,不一定是社会学上有意义的群体。需根据领域知识进行验证。
- 在少于 20 个节点的图上运行 SBM 会产生退化解——对于小型图,应退回到描述性网络指标或简单的社区检测方法。
常见问题
随机块模型与基于模块度的社区检测有何不同?
模块度最大化(例如 Louvain、Leiden)优化了一个启发式目标,该目标隐式假设同配的、大致相等大小的社区,并且存在已知的分辨率限制,阻碍了小社区的检测。SBM 是一个具有明确假设的生成概率模型;块计数通过模型选择(BIC 或贝叶斯因子)而非启发式优化来选择,并且它可以检测模块度方法遗漏的异配和核心-边缘结构。
我应该何时使用 DCSBM 而不是基本 SBM?
当节点度分布异质时——例如,当少数中心节点占据了大部分边,或者当度序列遵循近似幂律时——使用 DCSBM。基本 SBM 将块内的所有节点视为可互换的,这会导致中心节点被拉入其自身的虚假块中。DCSBM 增加了度校正项,将结构位置与度分离,从而在此类图中产生更具解释性的块分配。
我如何选择块的数量 K?
拟合一系列 K 值的模型,并选择使 BIC 最小化或贝叶斯因子最大化(或等效地使描述长度最小化)的 K 值。不要根据图的视觉检查或先验期望来选择 K。大多数实现(graph-tool,R 中的 blockmodels)都会自动执行此搜索。还建议进行敏感性分析——检查当 K 变化一个单位时,定性块结构是否发生变化。
SBM 可靠的最小网络规模是多少?
注册表规定可靠推理的最小节点数为 50。节点少于 20 个时,模型无法识别有意义的社区结构,并且会拟合噪声——此时应使用描述性网络统计或简单的社区检测方法。在 20 到 50 个节点之间,结果应视为探索性的,并谨慎解释。