COMP5313 - Chapter 3 Advanced Material - Betweenness and Graph Partitioning 中介性与图划分

Posted on In , Word count in article: 9.4k Reading time ≈ 34 mins.

Chapter 3 Advanced Material: Betweenness Measures and Graph Partitioning（中介性度量与图划分）

教材：Networks, Crowds, and Markets: Reasoning about a Highly Connected World 作者：David Easley & Jon Kleinberg, Cambridge University Press, 2010 章节：Section 3.6（章末进阶内容）

一、引言：为何需要图划分（Graph Partitioning）

1.1 Advanced Material 章节的定位

每章末的 Advanced Material（进阶内容） 部分面向有兴趣深入研究的读者，提供本章核心概念的数学化和技术化扩展。第 3 章前几节通过定性讨论介绍了网络中的"紧密相连区域（tightly-knit regions）"及其与边界的弱联系现象，但缺乏严格的数学定义和可操作的算法方法。

Section 3.6 的目标是提供： - 严格的量化方法，用于识别网络中的紧密相连区域 - 图划分算法，将网络自动分解为区域，使得： - 区域内节点高度互联 - 区域间连接稀疏 - 能够处理多层嵌套结构

1.2 两个驱动示例

示例 1：物理学家共同作者网络（Figure 3.12）

该图基于实际的科学合著关系网络（co-authorship network）： - 节点代表物理学家 - 边表示共同发表过论文 - 图中清晰可见多个紧密相连的簇（clusters），代表不同研究领域或机构的研究小组 - 簇之间有稀疏的连接边，由跨领域合作或个别研究者的多学科活动形成 - 直观上可识别出网络的"社区结构（community structure）"，但缺乏定量标准

示例 2：Wayne Zachary 的空手道俱乐部（Karate Club, Figure 3.13）

这是社交网络分析领域的经典数据集（Zachary 1977）： - 节点数：34（俱乐部成员） - 边：基于俱乐部外各种社交活动的互动关系 - 历史背景：1970 年代初，俱乐部会长（admin，节点 34）与空手道教练（instructor，节点 1）发生纠纷，导致俱乐部分裂成两个独立组织 - 核心问题：能否仅从网络拓扑结构预测出这个实际发生的分裂？即，是否存在算法能自动识别出与真实分裂一致的两个派系？

这个例子的重要性在于提供了ground truth（实际分裂结果），可用于验证图划分算法的有效性。

1.3 图划分问题的正式定义

问题陈述：给定图 \(G = (V, E)\)，其中 \(|V| = n\)，\(|E| = m\)，求将顶点集 \(V\) 分割为 \(k\) 个不相交子集 \(C_1, C_2, \ldots, C_k\)，使得：

\[\text{cut}(C_1, C_2, \ldots, C_k) = \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} |E(C_i, C_j)|\]

最小化，其中 \(E(C_i, C_j)\) 表示连接 \(C_i\) 和 \(C_j\) 的边数（割集（cut set））。

然而，单纯最小化割集可能产生平衡差、信息量少的分割。更好的目标是找到自然的、嵌套的多层分割结构。

二、图划分的两类方法（General Approaches to Graph Partitioning）

2.1 分裂式方法（Divisive Methods）

核心思想：自顶向下地递归分裂网络。

算法框架： 1. 识别当前连通分量内的"跨区连接"（spanning links）——即连接两个紧密相连子区域的边 2. 移除这些边，使网络分裂为多个分量，每个分量代表一个自然的区域 3. 对每个新产生的分量递归执行相同过程 4. 继续直至达到停止条件（如各分量内边数低于阈值，或节点数过少）

特点： - 自然揭示网络的嵌套分层结构 - 每一步的移除产生一个层级的划分结果 - 本章介绍的 Girvan-Newman 方法 就是典型的分裂式方法

视觉类比：想象从网络的"最脆弱"的跨区边开始，逐步剥离，好似剥洋葱。

2.2 聚合式方法（Agglomerative Methods）

核心思想：自底向上地递归合并相似节点。

算法框架： 1. 初始化：每个节点都是独立的"簇" 2. 识别最相似的节点对或最相似的簇对（相似性通常基于它们的邻域结构或共同邻居数） 3. 合并这两个簇 4. 重新计算相似性，继续合并 5. 持续直至所有节点合并为一个簇

特点： - 产生一个层级聚类树（hierarchical clustering dendrogram） - 可在树的任何高度"切割"以获得所需的分区数 - 计算相似性时通常不需要重新计算所有边的指标（视方法而定）

视觉类比：自最紧密的小团体开始，逐步将相似的团体并入更大的社群。

2.3 嵌套结构的重要性（Nested Regions）

现实观察（Figure 3.14）：现实网络中的社区往往存在多层次、多尺度的嵌套结构： - 大的地理区域内包含更小的次区域 - 公司内的部门下还有更小的工作组 - 学术合作网中，国家、大学、研究小组形成多层嵌套

数学表达：设 \(C_1, C_2, \ldots, C_k\) 是某一层的划分，则对于层级中的上一层，可能存在划分 \(D_1, D_2, \ldots, D_\ell\)（\(\ell < k\)），使得每个 \(D_j\) 是多个 \(C_i\) 的并集。

图划分算法应产生的结果：不是单一的平面划分，而是一个树状的层级划分结构，称为 dendrogram，可视化为二叉树，其中： - 每个内部节点代表一个合并/分裂操作 - 叶子节点代表单个或少量原始节点 - 树的高度反映了"社区的紧密程度"

三、中介性的概念（The Notion of Betweenness）

3.1 问题的动机

观察 Figure 3.14(a) 的网络图：直观上应该首先移除 7-8 边以完成第一步分裂。但如何系统地识别这条"最重要"的边？

初步想法与不足：

想法 1：移除 bridges（桥） 和 local bridges（局部桥）（回顾 Section 3.2）。 - 桥（bridge）：其删除后增加图的连通分量数的边 - 局部桥（local bridge）：两端点在三角形中不相邻的边

不足之处： 1. 若有多条桥或多条局部桥，不知道应该先移除哪一条 2. 在 Figure 3.15 的网络中，没有任何局部桥——每条边都至少在一个三角形内——但网络仍有明显的两部分结构需要分离

想法 2：考虑节点对间的最短路径依赖关系。

关键观察： - 桥和局部桥之所以重要，是因为它们构成了不同部分节点间的必经之路 - 若要从左半部分的某节点到达右半部分的某节点，必须经过这条边 - 如果没有这样的结构桥，路径虽然存在，但必须绕远路

基于这个观察，我们需要一个更一般的概念，能够量化"一条边对网络流量的重要性"。

3.2 网络流量的概念（Traffic on the Network）

定义流量的方式：

想象对图中每一对可达的节点 \(A\) 和 \(B\)，有一个单位的流体从 \(A\) 流向 \(B\)（无论物理距离多远，"流体"按数学方式流动）。

流量分配规则：这个单位流体在 \(A\) 到 \(B\) 的所有最短路径上均匀分配：

\[\text{Flow}_{A \to B}(e) = \frac{1}{k(A,B)} \quad \text{（对每条最短路径上的边 } e \text{）}\]

其中 \(k(A,B)\) 是从 \(A\) 到 \(B\) 的最短路径数。

特殊情况： - 若 \(A\) 和 \(B\) 不在同一连通分量中，\(A\) 和 \(B\) 间没有任何流量 - 若 \(k(A,B) = 1\)（唯一最短路径），这条路径上的边各承载 1 单位流量 - 若 \(k(A,B) > 1\)（多条最短路径），流量均摊

3.3 边中介性的定义（Edge Betweenness）

正式定义：

边 \(e\) 的中介性（betweenness） 是所有节点对 \((A, B)\) 通过 \(e\) 的流量之和：

\[B(e) = \sum_{A \neq B} \text{Flow}_{A \to B}(e)\]

直观意义： - 中介性量化了边在网络信息流、资源转移等过程中的"枢纽地位" - 高中介性的边连接了网络的不同部分，是最稀缺的资源 - 最高中介性的边往往是跨越社区边界的关键连接

单位：在无权图中，中介性通常是非负的有理数或整数（取决于最短路径数的结构）。

3.4 详细计算示例（Figure 3.14(a)）

考虑 Figure 3.14(a) 中的网络。该图有两个清晰的部分： - 左半部分：节点 1-7，形成较密集的结构 - 右半部分：节点 8-14，形成较密集的结构
- 连接边：仅 7-8 一条边

计算 7-8 边的中介性：

所有从左半部分 {1,2,3,4,5,6,7} 到右半部分 {8,9,10,11,12,13,14} 的路径必须经过 7-8 边。

  • 左半部分节点数：7
  • 右半部分节点数：7
  • 所有节点对 \((A, B)\) 的组合，其中 \(A\) 在左，\(B\) 在右：\(7 \times 7 = 49\)
  • 每一对的最短路径数为 1（无其他替代路径）
  • 因此，\(B(7\text{-}8) = 49\)

计算 3-7 边的中介性：

边 3-7 连接节点 3 和 7。哪些节点对的最短路径经过这条边？

  • 从节点 1, 2, 3 出发到节点 4,5,6,7,8,9,10,11,12,13,14 的某些对会使用 3-7
  • 具体地，{1,2,3} 中的节点经 3-7 到达右半部分的所有节点
  • 计数：3 个节点 × 11 个目标节点（右半 7 个 + 左半 4 个）
  • 实际上，从左半到右半只有 3×7 = 21 对；从 {1,2,3} 内部到 {4,5,6,7} 还有 3×4 = 12 对
  • 因此，\(B(3\text{-}7) = 21 + 12 = 33\)

对称地： - \(B(6\text{-}7) = 33\)（由于左半结构的对称性） - \(B(8\text{-}9) = 33\) - \(B(8\text{-}12) = 33\)

计算 1-3 边的中介性：

边 1-3 的中介性较低，因为： - 只有经过 1 且目标在 3 的"右侧"的节点对才会使用它 - 由于 1 的度数低，相对较少的路径依赖于 1-3 - 计算得 \(B(1\text{-}3) = 12\)

类似地，由于结构对称性，多条边的中介性为 12。

计算 1-2 边的中介性：

边 1-2 的中介性最低，因为： - 1 和 2 的距离为 1 - 只有以 1 或 2 为源/目的地的流量会使用这条边 - \(B(1\text{-}2) = 1\)（仅来自 1 到 2 及反向的流量）

类似地，{4-5, 10-11, 13-14} 等短连接的中介性都是 1。

小结：

中介性最高的边 7-8（值为 49）确实是跨越两个主要社区的唯一桥梁，符合直观预期。

3.5 节点中介性（Node Betweenness）

虽然本节重点是边中介性，但类似的定义也适用于节点：

节点中介性：经过节点 \(v\) 的所有最短路径的总和（Linton Freeman 最初定义）。

  • 高中介性的节点往往是网络的"枢纽"或"中介人（bridge person）"
  • 节点中介性在社会网络分析中用于识别影响力最大的个人
  • 计算节点中介性时，需注意是否计入以该节点为源/目的地的路径

四、Girvan-Newman 方法（The Girvan-Newman Algorithm）

4.1 算法核心思想

Girvan-Newman 分裂式算法（Girvan & Newman, 2002）基于以下原理：

  1. 计算网络中所有边的中介性
  2. 删除中介性最高的边（若多条并列，一起删除）；删除后网络可能分裂为多个连通分量，各分量代表找到的第一层社区
  3. 重新计算所有剩余边的中介性
  4. 再次删除中介性最高的边
  5. 重复步骤 3-4，直至所有边被删除

关键特性： - 该方法自然地暴露嵌套结构——每个删除步骤产生一个层级的分割 - 删除顺序反映了边的"社区间性"的强弱 - 最终产生的 dendrogram 可用于在不同粒度选择最终的社区划分

4.2 算法伪代码

Algorithm GIRVAN_NEWMAN(G = (V, E))
Input: Graph G with vertex set V and edge set E
Output: Dendrogram representing hierarchical community structure

dendrogram ← empty tree
edges_removed_sequence ← []

while E is not empty do
    for each edge e in E do
        compute_betweenness(e)  // 重新计算 e 的中介性
    end for
    
    e_max ← edge(s) with maximum betweenness
    
    remove e_max from E
    edges_removed_sequence.append(e_max)
    
    record current connected components in dendrogram
    
end while

return dendrogram

4.3 应用于 Figure 3.14(a) 的步骤演示（Figure 3.16）

Step 1（第一次删除）：

计算所有边的中介性（如前所述）： - 7-8：49（最高） - 3-7, 6-7, 8-9, 8-12：33 - 其他：更低

删除 7-8 边： - 网络分裂为两个连通分量 - 分量 1：{1,2,3,4,5,6,7}（7 个节点） - 分量 2：{8,9,10,11,12,13,14}（7 个节点） - 第一级社区识别完成

Step 2（第二次删除）：

对两个分量分别重新计算中介性：

在分量 1 中： - 之前被 7-8 的流量分散的节点对现在直接相互连接 - 中介性最高的边变为 3-7, 6-7（均为 33，因为已经消除了跨分量流量） - 实际上，在一个 7 节点的小网络中，这两条边仍有相对高的中介性

在分量 2 中： - 类似地，8-9 和 8-12 或其他边成为最高中介性的候选

假设删除：3-7, 6-7, 8-9, 8-12（假设并列最高） - 这些边连接的是分别的"核心"与"外围" - 删除后进一步分裂

Step 3 及以后：

继续这个过程，三角形内部的边（如 3-4, 4-5 等）因为有多条绕行路径，中介性较低，被保留更长时间。

最终的 dendrogram 显示： - 最顶层：整个网络 - 次层：两个 7-节点的主社区 - 更下层：每个主社区内的子结构

4.4 应用于 Figure 3.15 的步骤演示

Figure 3.15 是一个更复杂的网络，其中： - 左侧 5 个节点 {1,2,3,4,5}，形成紧密的连接 - 右侧 7 个节点 {7,8,9,10,11,12,13}，形成紧密的连接 - 连接边：5-6 和 6-7（通过中间节点 6）

Step 1：

计算所有边的中介性。关键的是 5-6 边（或 6-7 边）： - 从 {1,2,3,4,5} 中的任何节点到 {7,8,9,10,11,12,13} 中的任何节点，所有最短路径都必须经过中间节点 6 - 经过 5-6 边的流量：\(5 \times 7 = 35\) - 经过 6-7 边的流量：\(5 \times 7 = 35\) - 经过 5-7 边的流量（间接连接）：取决于路由（假设 5-7 不直接相连）

计算精确值（假设图的具体结构）： - 若 5-7 是直接边，则流量分摊于 {5-6-7} 和 {5-7} - 若 {1,2,3,4,5} 内部和 {7,8,9,10,11,12,13} 内部都是全连接或接近全连接，则有多条最短路径 - 假设 5-7 边的中介性为 25（详见下文）

删除 5-7 边（若其中介性最高）：分裂为两个分量。

但根据教材，实际流程如下：

Step 1（修正）：

重新审视 Figure 3.15 的结构。若图具体如下（根据教材描述）： - 左簇 {1,2,3,4,5}：这 5 个节点形成接近完全图的紧密连接 - 右簇 {7,8,9,10,11,12,13}：7 个节点的紧密连接 - 中间节点 6 作为桥

路径分析： - 从左簇任意节点 \(A\) 到右簇任意节点 \(B\)，最短路径经过 6 - 若左簇内部多条路径都能到达 5 或其他外围节点，且都通过 6，则所有这些路径的"出口"都经过 5-6 - 类似地，6-7 是从 6 进入右簇的"入口"

5-7 边（假设存在）的中介性计算： - 5-7 可能是 5 到右簇的直接连接（local bridge） - 经过 5-7 的流量：所有以 5 为源/目的地且目标在右簇（或反之）的节点对 - 假设 5 是左簇的外围节点，到它的最短路径数相对较少 - 估计 \(B(5\text{-}7) = 25\)（具体数字取决于左簇内的精确拓扑）

第一步删除 5-7（中介性 25 最高）： - 删除后，任何从左簇到右簇的路径必须使用 5-6-7 序列或其他中介路径

Step 2：

重新计算。原本经过 5-7 的流量现在必须重新路由： - 从左簇到右簇：改为 5-6-7 路线 - 这增加了 5-6 和 6-7 的中介性

新的中介性计算（具体数字需根据完整网络拓扑）： - 原本 5-6 的中介性：假设为 5（仅来自 5 周围节点的流量） - 删除 5-7 后，5-6 的中介性增至 \(5 + 25 = 30\)（原有流量加上重新路由的流量） - 类似地，6-7 的中介性变为 30

删除 5-6 和 6-7（现在中介性并列最高）： - 网络分裂，左右两个簇完全分离

这个例子展示了 Girvan-Newman 方法的自适应性：删除一条边后，其他边的"重要性排名"会因流量重新分配而改变。

4.5 Zachary 空手道俱乐部的验证（Figure 3.13）

实验结果： - 该 34 节点网络在 Girvan-Newman 算法下运行 - 当删除到第一次明显的两个分量分裂时，结果产生两个社群 - 这两个社群与 1970 年实际发生的俱乐部分裂 高度吻合 - 34 个成员中，33 个被正确分配到与其实际加入的派系相同的社群 - 仅有 1 个成员（node 9）被错误分类

对 node 9 的解释（Zachary 本人提供）： - node 9 是俱乐部的一个相对外围成员，与两位领导都有联系 - 当时 node 9 离获得黑带认证仅剩 3 周时间 - 他倾向于跟随教练（node 1）是为了完成认证，这是个人激励而非网络结构决定的 - 这说明网络结构虽然强大，但并非完全决定性的——社会动因和个人利益也会影响真实选择

Zachary 的原始方法对比： - Zachary 原始论文使用的方法：给网络的边赋予权重/强度值，基于社交互动的频繁程度 - 然后使用最小割（minimum cut） 方法分离两位领导人 - Girvan-Newman 使用的是拓扑结构和流量分析，不需要边权重

4.6 Leskovec 等人的深入发现

后续研究（Leskovec et al., 2008）指出了 Girvan-Newman 及其他图划分方法的一个重要限制：

观察： - 在小规模网络（~100-1000 节点）上，图划分方法能找到与真实社区高度吻合的结果 - 在大规模网络（超过几千节点）上，即使是真实的、经验验证的"社区"也很难从网络其他部分清晰"剥离"出来 - 换句话说，真实大网络的社区往往有分散的外围边界，而非清晰的割集

定量发现： - 社群大小与其"与外界的连接密度"之间存在权衡 - 小的、紧密的社群容易被分离 - 大的社群往往与其他社群有大量的跨界边，难以完全分离

启示： - 图划分不是一个绝对的"找到正确答案"问题，而是一个多尺度、相对的问题 - 同一网络在不同分辨率下可能有定性不同的社区结构 - 选择多少个社区、社区大小的分布，都需要根据应用背景和分析目标来确定

五、计算中介性的高效算法（Computing Betweenness Values）

5.1 计算的挑战

直接方法的复杂度： - 若直接列举所有节点对 \((A, B)\) 及它们的所有最短路径，在大网络中计算量巨大 - 节点对数：\(O(n^2)\) - 每对的最短路径数可能呈指数增长（完全图或高对称性网络） - 总的直接枚举复杂度：\(O(n^2 \cdot \text{exponential paths})\)

高效方法的关键： - 不显式枚举最短路径，而是通过累加和分解（aggregation and decomposition） 计算 - 基于广度优先搜索（Breadth-First Search, BFS） 的框架 - 对每个源节点进行一次 BFS，累计该源的所有流量贡献 - 最后汇总所有源的贡献，得到每条边的总中介性

5.2 基于 BFS 的三步计算框架

对每个源节点 \(s\)，执行以下三步：

步骤 1：BFS 分层

从源节点 \(s\) 执行标准的广度优先搜索，将图的所有节点分配到"层（layers）"：

\[\text{Layer}_d = \{v \in V : \text{dist}(s, v) = d\}\]

其中 \(\text{dist}(s, v)\) 是从 \(s\) 到 \(v\) 的最短路径长度（边数）。

数据结构记录： - 每个节点的层号 \(d_v\) - 来自前一层（上一层）的邻接（predecessors 或 parents）：即在 BFS 树中"上方"的节点 - \(\text{pred}(v) = \{u \in \text{Layer}_{d_v - 1} : (u,v) \in E\}\)

示例（Figure 3.18，从节点 A 出发）： - Layer 0：{A} - Layer 1：A 的所有邻接节点 - Layer 2：不在前两层，且与 Layer 1 有边连接的节点 - ...以此类推，直至所有连通节点被分配

5.3 步骤 2：计数最短路径（Counting Shortest Paths）

关键观察：

从源 \(s\) 到任意节点 \(v\) 的最短路径数可以递推计算：

\[\sigma(s, v) = \sum_{u \in \text{pred}(v)} \sigma(s, u)\]

初始条件：\(\sigma(s, s) = 1\)（从 \(s\) 到自己有一条长度为 0 的路径）

逻辑： - \(s\) 到 \(v\) 的最短路径必定经过 \(v\) 的某个前驱节点 \(u\)（即 \(u\) 在 Layer \(d_v - 1\) 且与 \(v\) 相邻） - 从 \(s\) 到 \(v\) 的不同最短路径对应于从 \(s\) 到 \(u\) 的不同最短路径，然后加上边 \((u,v)\) - 因此，\(\sigma(s, v)\) 就是所有 \(\sigma(s, u)\) 的和

计算顺序： - 从 Layer 0 开始，按层递推（从上到下） - 对 Layer 1 中的节点，\(\sigma(s, v) = 1\)（因为它们的前驱只有 \(s\)，且 \(\sigma(s,s) = 1\)） - 对 Layer 2 中的节点，根据前驱累加 - ...以此类推

5.4 步骤 3：确定流量值（Determining Flow Values）

这是最微妙的一步。我们需要自下而上地（从远离源的节点开始）确定每条边携带的流量。

流量的传播： - 对每个节点 \(v\)，维护一个"流量累积器" \(\delta(s, v)\)，表示从 \(s\) 经过 \(v\) 前往更远节点的单位流量 - 初始化：对于最远层（距离最大）的节点 \(v\)，\(\delta(s, v) = 1\)（目标节点本身产生 1 单位流量） - 然后自下而上地回传

流量回传公式：

对于节点 \(v\) 的每条前驱边 \((u, v)\)（即从 \(u\) 到 \(v\) 的边，\(u\) 在前一层）：

\[\text{Flow}_{s}(u, v) = \frac{\sigma(s, u)}{\sigma(s, v)} \cdot \delta(s, v)\]

以及：

\[\delta(s, u) = \sum_{v : (u,v) \in E, d_v = d_u + 1} \text{Flow}_s(u, v)\]

（即，\(u\) 累积来自所有后继节点 \(v\) 的流量）

直观理解： - 从 \(v\) 出发到更远节点的每一单位流量，在返回 \(v\) 的所有前驱时，按最短路径数的比例分摊 - 若有 \(k\) 条不同的最短路径从 \(u\) 到 \(v\)，且 \(v\) 有 \(m\) 单位流量需要传回上层，则每条路径（即每个 \(u\)）承担 \(m/k\) 单位 - 这确保了流量守恒和合理的分摊

5.5 图 3.19 的详细计数示例

考虑一个 11 节点的图，从节点 A 执行 BFS（Figure 3.19）：

图的结构（示例）：
Layer 0: A
Layer 1: B, C, D, E（4 个节点，都直接连 A）
Layer 2: F, G, H（3 个节点）
Layer 3: I, J（2 个节点）
Layer 4: K（1 个节点）

前驱关系（示例）：

B: pred(B) = {A}
C: pred(C) = {A}
D: pred(D) = {A}
E: pred(E) = {A}
F: pred(F) = {B, C}         // F 从 B 和 C 都能到达，距离相同
G: pred(G) = {D}
H: pred(H) = {D, E}
I: pred(I) = {F, G}
J: pred(J) = {G, H}
K: pred(K) = {I, J}

计算最短路径数 \(\sigma(A, v)\)：

初始：\(\sigma(A, A) = 1\)

Layer 1： - \(\sigma(A, B) = \sigma(A, A) = 1\) - \(\sigma(A, C) = 1\) - \(\sigma(A, D) = 1\) - \(\sigma(A, E) = 1\)

Layer 2： - \(\sigma(A, F) = \sigma(A, B) + \sigma(A, C) = 1 + 1 = 2\) - \(\sigma(A, G) = \sigma(A, D) = 1\) - \(\sigma(A, H) = \sigma(A, D) + \sigma(A, E) = 1 + 1 = 2\)

Layer 3： - \(\sigma(A, I) = \sigma(A, F) + \sigma(A, G) = 2 + 1 = 3\) - \(\sigma(A, J) = \sigma(A, G) + \sigma(A, H) = 1 + 2 = 3\)

Layer 4： - \(\sigma(A, K) = \sigma(A, I) + \sigma(A, J) = 3 + 3 = 6\)

结果总结： - 从 A 到 K 有 6 条不同的最短路径！ - 这反映了多条并行的最短路径结构

计算流量值（自下而上）：

初始化（最远节点）： - \(\delta(A, K) = 1\)

Layer 4 → Layer 3（K 的回传）：

K 有两个前驱：I 和 J

\[\text{Flow}_A(I, K) = \frac{\sigma(A, I)}{\sigma(A, K)} \cdot \delta(A, K) = \frac{3}{6} \cdot 1 = \frac{1}{2}\]

\[\text{Flow}_A(J, K) = \frac{\sigma(A, J)}{\sigma(A, K)} \cdot \delta(A, K) = \frac{3}{6} \cdot 1 = \frac{1}{2}\]

Layer 3 处的流量累积： - \(\delta(A, I) = 1 + \text{Flow}_A(I, K) = 1 + \frac{1}{2} = \frac{3}{2}\)（I 本身流量 1，加上来自 K 的 1/2） - \(\delta(A, J) = 1 + \text{Flow}_A(J, K) = 1 + \frac{1}{2} = \frac{3}{2}\)

Layer 3 → Layer 2（I 和 J 的回传）：

I 的前驱：F 和 G

\[\text{Flow}_A(F, I) = \frac{\sigma(A, F)}{\sigma(A, I)} \cdot \delta(A, I) = \frac{2}{3} \cdot \frac{3}{2} = 1\]

\[\text{Flow}_A(G, I) = \frac{\sigma(A, G)}{\sigma(A, I)} \cdot \delta(A, I) = \frac{1}{3} \cdot \frac{3}{2} = \frac{1}{2}\]

J 的前驱：G 和 H

\[\text{Flow}_A(G, J) = \frac{\sigma(A, G)}{\sigma(A, J)} \cdot \delta(A, J) = \frac{1}{3} \cdot \frac{3}{2} = \frac{1}{2}\]

\[\text{Flow}_A(H, J) = \frac{\sigma(A, H)}{\sigma(A, J)} \cdot \delta(A, J) = \frac{2}{3} \cdot \frac{3}{2} = 1\]

Layer 2 处的流量累积： - \(\delta(A, F) = 1 + 1 = 2\)（自身 1 + 来自 I 的 1） - \(\delta(A, G) = 1 + \frac{1}{2} + \frac{1}{2} = 2\)（自身 1 + 来自 I 的 1/2 + 来自 J 的 1/2） - \(\delta(A, H) = 1 + 1 = 2\)（自身 1 + 来自 J 的 1）

Layer 2 → Layer 1：

F 的前驱：B 和 C

\[\text{Flow}_A(B, F) = \frac{\sigma(A, B)}{\sigma(A, F)} \cdot \delta(A, F) = \frac{1}{2} \cdot 2 = 1\]

\[\text{Flow}_A(C, F) = \frac{\sigma(A, C)}{\sigma(A, F)} \cdot \delta(A, F) = \frac{1}{2} \cdot 2 = 1\]

G 的前驱：D

\[\text{Flow}_A(D, G) = \frac{\sigma(A, D)}{\sigma(A, G)} \cdot \delta(A, G) = \frac{1}{1} \cdot 2 = 2\]

H 的前驱：D 和 E

\[\text{Flow}_A(D, H) = \frac{\sigma(A, D)}{\sigma(A, H)} \cdot \delta(A, H) = \frac{1}{2} \cdot 2 = 1\]

\[\text{Flow}_A(E, H) = \frac{\sigma(A, E)}{\sigma(A, H)} \cdot \delta(A, H) = \frac{1}{2} \cdot 2 = 1\]

Layer 1 处的流量累积： - \(\delta(A, B) = 1 + 1 = 2\) - \(\delta(A, C) = 1 + 1 = 2\) - \(\delta(A, D) = 1 + 2 + 1 = 4\) - \(\delta(A, E) = 1 + 1 = 2\)

（注意：这些 \(\delta\) 值不再用于进一步回传，因为 A 是源点，但它们记录了该节点的"依赖性"）

边中介性的累积：

对每条边 \((u, v)\)，跨所有源节点 \(s\) 求和 \(\text{Flow}_s(u, v)\)，并除以 2（因为每对 \((s, t)\) 被计算了两次：一次从 \(s\)，一次从 \(t\)）：

\[B(e) = \frac{1}{2} \sum_{s} \text{Flow}_s(e)\]

5.6 算法的时间复杂度

单源 BFS 的复杂度：\(O(n + m)\)（标准 BFS）

计数最短路径的复杂度：\(O(n + m)\)（随 BFS 进行）

流量回传的复杂度：\(O(n + m)\)（每条边最多处理常数次）

总复杂度（对所有 \(n\) 个源节点）：\(O(n(n + m)) = O(n^2 + nm)\)

对于： - 稠密图（\(m \approx n^2\)）：\(O(n^3)\)（过高，不实用于大网络） - 稀疏图（\(m \approx n\)）：\(O(n^2)\)（更可接受，但仍需在中等规模网络上）

这是一个显著的改进，相比于显式枚举所有最短路径。

5.7 扩展与优化

节点中介性的计算：

在流量回传过程中，可以同时追踪每个节点被经过的次数，得到节点中介性。

加权网络：

若边有权重，"最短路径"改为"最小权重路径"，BFS 改为 Dijkstra 算法。

近似算法：

对于超大规模网络（数百万节点），完整计算仍然过慢。研究者开发了基于随机抽样的中介性近似方法，在牺牲精度的前提下大幅加速。

六、方法的扩展、局限与未来方向

6.1 原始 Girvan-Newman 的计算开销

每轮重新计算的成本： - 每次删除一条或多条边后，网络拓扑改变 - 需要对所有源节点重新执行一遍中介性计算 - 删除过程中最多进行 \(|E|\) 轮迭代

总体复杂度： - 若有 \(m\) 条边，每轮计算成本 \(O(n^2 + nm)\)（如上所述） - 总成本：\(O(m \cdot (n^2 + nm)) = O(m \cdot n^2)\) 或更高（对稠密图） - 对中等规模网络（~1000-10000 节点，10000-100000 边）可行，但对更大网络不实用

实践中的优化： - 仅重新计算受删除影响的子网络 - 使用增量算法避免完全重计算 - 但即使有优化，原始方法的可扩展性仍有限

6.2 大网络中的挑战

计算瓶颈： - 对百万级节点的网络（如社交媒体、互联网拓扑），原始 Girvan-Newman 在实际中计算不可行 - 研究者转向更高效的替代方法

社区结构的粗粒度性： - Leskovec 等人的发现表明，大网络中"真实社区"的边界往往模糊 - 完全的分离可能不存在或不有意义 - 图划分的结果对参数、初始化、算法细节敏感

6.3 替代和改进方法

聚合式方法（Agglomerative Approaches）：

  • 如 Fast Modularity Optimization（Newman & Girvan, 2006）
  • 直接优化模块性指标（modularity metric），评估社区紧密程度相对于随机预期的偏离
  • 在大网络上更高效

局部社区检测：

  • 从单个节点或小种子集出发，贪心扩展到相邻节点
  • 不需要全局计算，适合大网络
  • 如 Local Spectral Clustering（Spielman & Teng, 2013）

随机游走方法：

  • 基于随机游走 或强化学习的思想
  • 如 DeepWalk、Node2Vec（虽然主要用于节点嵌入，也可用于社区检测）

谱方法（Spectral Methods）：

  • 基于图的Laplacian 矩阵的特征向量
  • 如谱聚类（Spectral Clustering）
  • 理论基础扎实，计算复杂度 \(O(n^3)\)（特征分解），但可高效近似

6.4 多尺度和嵌套结构

当代的洞察： - 社区检测不是单一的、绝对的任务，而是多分辨率的、相对的观点 - 同一网络可在不同"放大倍数"下暴露不同的社区结构 - 最优的社区数可能不存在；而是一系列嵌套的替代分割

分辨率参数： - 现代方法（如 Louvain 算法）引入分辨率参数，允许用户在不同粒度间切换 - 低分辨率：大社区（宏观视角） - 高分辨率：小社区（微观视角）

6.5 模块性指标（Modularity）

定义：模块性 \(Q\) 衡量实际社区结构与随机网络模型的偏离程度。

\[Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)\]

其中： - \(A_{ij}\)：邻接矩阵元素（实际边的存在） - \(k_i, k_j\)：节点 \(i, j\) 的度数 - \(\delta(c_i, c_j)\)：指示函数（若 \(c_i = c_j\)，值为 1，否则为 0） - \(m\)：总边数

解释： - 第一项：实际存在的同社区边数 - 第二项：在配置模型（节点度数相同但随机连接）中的期望同社区边数 - 差异越大，社区划分越"真实"和"有意义"

范围：\(Q \in [-1, 1]\)，通常 \(Q > 0.3\) 被认为表明显著的社区结构。

七、与章节其他部分的联系

7.1 与 Section 3.2（局部桥、弱联系）的联系

回顾（Section 3.2）： - 局部桥（local bridge）：两端点没有共同邻居的边 - 弱联系假说：信息和机会往往通过弱关系（如局部桥）传播 - 社会资本：处于局部桥位置的个人可获得信息优势

关系： - 局部桥往往具有高的边中介性，因为它们是连接不同社区的关键 - 但并非所有高中介性边都是局部桥（在没有局部桥的网络中仍有高中介性边，如 Figure 3.15） - 中介性是局部桥概念的推广：在没有明显的三角形或局部桥的网络中，中介性仍能识别关键边

7.2 与 Section 3.5（结构洞、社会资本）的联系

结构洞（Structural Holes）： - Burt 的理论强调，占据不同社群之间"洞（hole）"的个人拥有信息优势和影响力 - 这样的个人充当"中介人"，桥接隔离的信息流

联系： - 高中介性的节点往往占据结构洞 - Girvan-Newman 等图划分算法识别出的社区边界往往对应于结构洞的位置 - 删除高中介性的节点往往会增加网络的分裂，反映了结构洞对网络连通性的关键作用

应用含义： - 在组织中识别出结构洞占据者（高中介性节点） - 这些个人对创新、资源流动和跨部门协调特别重要 - 但同时，他们的"中介地位"可能使其成为权力变化中的关键目标

7.3 与社会网络分析和组织研究的应用

实证应用：

  1. 企业组织中的团队识别：
    • 利用 Girvan-Newman 等方法自动识别组织内的自然分组
    • 相比于正式的组织结构图（往往滞后于实际合作网络）更新
  2. 在线社区的演化分析：
    • 跟踪社区随时间的形成、分裂、合并
    • 理解社群的成长和衰落
  3. 信息传播和谣言控制：
    • 识别关键节点和边，理解信息如何在社区间流动
    • 设计干预策略（如目标化接种或内容审核）
  4. 犯罪网络和恐怖网络的分析：
    • 执法机构使用图划分识别帮派、犯罪组织的内部结构
    • 识别关键人物（高中介性）以进行破坏

八、核心概念总结表

下表总结了本节的关键概念和术语：

中文术语 English Term 简要说明
图划分 Graph Partitioning 将网络分解为紧密相连的子图，子图间连接稀疏的任务
紧密相连区域 Tightly-knit Regions 内部高度互联的节点子集
分裂式方法 Divisive Method 自顶向下递归删除边以分裂网络的方法
聚合式方法 Agglomerative Method 自底向上递归合并节点以形成社区的方法
层级聚类树 Dendrogram 表示递归划分/合并过程的树状结构
中介性（边） Edge Betweenness 一条边承载的通过它的所有节点对的流量之和
中介性（节点） Node Betweenness 一个节点在最短路径中被经过的频率
最短路径 Shortest Path 两节点间最少边数的路径
最短路径数 Shortest Path Count 从源到目的地的不同最短路径的条数
流量分配 Flow Distribution 在最短路径上均匀分配流量的规则
Girvan-Newman 方法 Girvan-Newman Algorithm 迭代删除最高中介性边的图划分算法
广度优先搜索 Breadth-First Search (BFS) 从源节点逐层遍历图的搜索算法
前驱/父节点 Predecessor / Parent Node BFS 树中位于上一层且有边相连的节点
后继/子节点 Successor / Child Node BFS 树中位于下一层且有边相连的节点
流量回传 Flow Propagation / Backtracking 自下而上地从叶节点向源节点累积流量的过程
局部桥 Local Bridge 两端点无共同邻居的边
社区结构 Community Structure 网络中高度互联的节点簇
社区检测 Community Detection 识别网络社区结构的算法过程
模块性 Modularity 评估社区划分质量的指标，范围 [-1, 1]
配置模型 Configuration Model 保持节点度数但随机重连接的网络模型
随机游走 Random Walk 从节点出发，随机选择邻接点移动的过程
谱方法 Spectral Method 基于图 Laplacian 矩阵特征向量的方法
结构洞 Structural Hole 不同社群之间的"缝隙"，占据者拥有信息优势
割集 Cut Set 连接两个子图的所有边的集合
最小割 Minimum Cut 大小最小的割集
连通分量 Connected Component 网络中最大的连通子图
空手道俱乐部 Karate Club Zachary 的经典社交网络数据集
共同作者网络 Co-authorship Network 以科学家为节点，共同发表论文为边的网络
多分辨率 Multi-resolution 在不同粒度观察网络的能力
分辨率参数 Resolution Parameter 控制社区检测粒度的可调参数
Louvain 算法 Louvain Algorithm 高效的模块性优化社区检测算法
边权重 Edge Weight 边的强度或重要性数值
加权网络 Weighted Network 边带有权重的图
Dijkstra 算法 Dijkstra Algorithm 计算加权图最短路径的算法
近似算法 Approximation Algorithm 在精度和速度间做出权衡的算法
随机抽样 Random Sampling 从大规模问题中抽取代表样本的技术

总结与思考

本章 Advanced Material 部分详细阐述了如下要点：

  1. 图划分的必要性：网络中的社区结构是普遍现象，需要严格的数学方法来识别

  2. 中介性概念的强大：通过流量模型，中介性推广了桥和局部桥的概念，适用于更一般的网络

  3. Girvan-Newman 方法的优雅性：迭代删除最高中介性边，自然暴露嵌套的社区结构，并在真实数据（如 Zachary 空手道俱乐部）上验证有效

  4. 高效计算的关键：基于 BFS 的流量计算避免了显式枚举最短路径的指数成本，使得中等规模网络的分析变得可行

  5. 现实的复杂性：大规模网络的社区往往边界模糊，完美的分离可能不存在；分析应在多个分辨率下进行

  6. 理论与实践的连系：结构洞、弱联系、社会资本等定性概念在这里得到量化和算法化

这些洞察对于理解现代网络分析、社交媒体监控、企业组织、信息流传播等众多领域都有深远的影响。

参考资源与进一步阅读：

  • Girvan, M., & Newman, M. E. (2002). Community structure in social and biological networks. PNAS, 99(12), 7821-7826.
  • Newman, M. E. (2004). Fast algorithm for detecting community structure in networks. Physical Review E, 69(6), 066133.
  • Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4), 452-473.
  • Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008). Statistical properties of community structure in large social and information networks. WWW 2008.

文档生成时间：2026-04-15
教材：Easley, D., & Kleinberg, J. (2010). Networks, Crowds, and Markets. Cambridge University Press.
章节：Section 3.6 Advanced Material