生物医学网络科学Biomedical Network Science
社团结构与社区发现02 / 19

社团的基本假设与形式化定义

阅读
约 4 分钟

Barabási《Network Science》第 9 章用四条“假设”串起社团发现的逻辑。它们不是定理，而是各类方法赖以成立的前提，理解它们有助于看清每种方法“默认了什么”。

四条基本假设

  • H1 基本假设（fundamental hypothesis）：网络的社团结构唯一地蕴含在其连边图中，原则上只用邻接矩阵 AA 就能把它找出来。
  • H2 连通与密度假设（connectedness and density hypothesis）：社团是局部稠密的连通子图——社团内任意两个节点之间应能只经由社团内部节点到达。
  • H3 随机假设（random hypothesis）：随机网络没有内在的社团结构；判断一个划分“好”，要与同样度序列的随机网络比较。
  • H4 最大模块度假设（maximal modularity hypothesis）：对给定网络，模块度最大的划分对应最优的社团结构。

H1 让社团发现成为纯粹的图论问题；但在生物医学数据中，节点注释（基因功能、脑区位置）与网络之外的信息常常被用来“检验”社团，这实际上偏离了 H1——网络结构与外部注释可以不一致（Peel 等 2017）。H2 是 Leiden 算法相对 Louvain 的改进动机。H3 是模块度零模型的出发点，也是可检测性阈值讨论的起点。H4 则被分辨率极限和模块度平台所质疑，这也是随机块模型和 Infomap 等方法出现的原因之一。

由严到宽的几种社团定义

记子图 CC 中节点 ii 的内度 kiintk_i^{\text{int}}（连向 CC 内部的边数）和外度 kiextk_i^{\text{ext}}（连向 CC 外部的边数）。

定义 条件 说明
团（clique） CC 是完全子图 最严格；在真实网络中很少有大团，且团内节点地位完全对称
强社团（strong community） 对每个 i∈Ci\in C，kiint>kiextk_i^{\text{int}}>k_i^{\text{ext}} 每个成员“更忠于”本社团（Radicchi 等 2004）
弱社团（weak community） ∑i∈Ckiint>∑i∈Ckiext\sum_{i\in C}k_i^{\text{int}}>\sum_{i\in C}k_i^{\text{ext}} 只要求社团整体的内部连接多于外部连接

每个团都是强社团，每个强社团都是弱社团，反之不成立。以上是局部定义：只看子图自身和它的边界。模块度、随机块模型等则是全局定义：社团是整个划分的一部分，好坏由全网的质量函数或似然决定。

社团不一定“内部稠密”

“内部稠密、外部稀疏”的同配（assortative）结构只是众多分块结构中的一种。二分网络（如药物–靶点网络）中，同类节点之间没有边，组之间才有边，是典型的异配（disassortative）结构；核心–边缘结构中，核心节点彼此相连并连接边缘节点，而边缘节点之间很少相连。模块度只奖励同配结构，而随机块模型可以同时描述这几类结构。在把“社团”一词用于某个生物网络之前，先想清楚要找的是哪一种结构。

划分数目：为什么不能穷举

最简单的社团问题是图二分（graph bisection）：把 NN 个节点分成两个等大的组，使两组之间的边数（割，cut size）最小。等大二分的方式有 (NN/2)=N![(N/2)!]2≈2N+12πN\binom{N}{N/2}=\frac{N!}{[(N/2)!]^2}\approx \frac{2^{N+1}}{\sqrt{2\pi N}} 种（由 Stirling 公式得到）。若不限定组数和组的大小，NN 个节点的全部划分数是 Bell 数 BNB_N，满足递推 BN+1=∑j=0N(Nj)BjB_{N+1}=\sum_{j=0}^{N}\binom{N}{j}B_j，并有 Dobinski 公式 BN=1e∑j≥0jN/j!B_N=\frac1e\sum_{j\ge0} j^N/j!。Bell 数增长得比任何指数函数都快：B10=115975B_{10}=115\,975，B20≈5.2×1013B_{20}\approx5.2\times10^{13}，B50≈1.9×1047B_{50}\approx1.9\times10^{47}（代码示例）。

计算复杂性：模块度最大化是 NP 难问题（Brandes 等 2008）。因此所有实用的模块度算法都是启发式的，只能保证得到“好的”而非“最优的”划分。只有在十几个节点以内的网络上，才能穷举全部 BNB_N 种划分求得精确最优。

手算例：4 个节点的路径 1–2–3–4（m=3m=3，度为 1,2,2,1）。B4=15B_4=15 种划分中，{1,2}{3,4}\{1,2\}\{3,4\} 的模块度为 2×[13−(36)2]=16≈0.1672\times\left[\frac13-\left(\frac36\right)^2\right]=\frac16\approx0.167；{1}{2,3,4}\{1\}\{2,3,4\} 为 [0−(16)2]+[23−(56)2]=−136+−136=−118\left[0-\left(\frac16\right)^2\right]+\left[\frac23-\left(\frac56\right)^2\right]=-\frac1{36}+\frac{-1}{36}=-\frac{1}{18}。可以逐一验证，{1,2}{3,4}\{1,2\}\{3,4\} 是 15 种划分中模块度最大的。

描述性方法与推断性方法

Peixoto（2023）把社团发现方法区分为两类：描述性方法（如模块度最大化）给出一个满足某种准则的划分，回答“这个网络可以怎样被概括”；推断性方法（如贝叶斯随机块模型）假设网络由某个含分组的生成过程产生，回答“哪种分组最可能产生了这个网络、证据有多强”。两者问的是不同问题：描述性方法在随机网络中也会“找到”社团（见下页），推断性方法则会在证据不足时报告“没有结构”。选择方法前应先明确研究问题属于哪一类。

继续阅读