COMP5313 - Chapter 2 Graphs 图

Posted on Edited on In , Word count in article: 4.9k Reading time ≈ 18 mins.

Chapter 2: Graphs（图）

教材：Networks, Crowds, and Markets: Reasoning about a Highly Connected World 作者：David Easley & Jon Kleinberg, Cambridge University Press, 2010

一、章节总览

第二章是全书第一部分（图论与社会网络） 的开端，系统介绍了图论（Graph Theory） 的基本概念。图论为研究网络结构提供了统一的数学语言。本章从最基础的定义出发，逐步引入路径、连通性、距离、广度优先搜索等核心概念，并通过大量真实网络案例加以说明。最后概述了大规模网络数据集的主要来源。

二、基本定义（Section 2.1: Basic Definitions）

2.1 图的定义

图（Graph） 是一种描述一组事物之间关系的方式。一个图由以下两部分组成：

  • 节点（Nodes）：又称顶点（vertices），代表图中的对象，通常用小圆圈表示
  • 边（Edges）：又称链接（links），连接某些节点对，通常用线段表示

形式化定义：图 G = (V, E)，其中 V 是节点集合，E 是边集合，每条边连接 V 中的一对节点。

邻居（Neighbors）：如果两个节点由一条边相连，则称它们互为邻居。

2.2 无向图与有向图

（1）无向图（Undirected Graph） - 边是对称的：如果 A 与 B 相连，则 B 也与 A 相连 - 边用不带箭头的线段表示 - 除非特别说明，本书中的图默认为无向图

（2）有向图（Directed Graph） - 边是不对称的：A 指向 B 不意味着 B 指向 A - 边称为有向边（Directed Edges），用带箭头的线段表示 - 用于表达非对称关系，如"A 指向 B"、"A 引用 B"等

典型案例（Figure 2.1）：展示了同样 4 个节点 A, B, C, D 的无向图和有向图版本。

2.3 图作为网络的模型（Graphs as Models of Networks）

图在许多领域中都有广泛应用，可用于表示各类网络结构：

网络类型 节点含义 边的含义 典型案例
通信网络（Communication Network） 计算机或设备 可传输消息的直接链路 1970年 Arpanet（Figure 2.2, 2.3）
社交网络（Social Network） 人或人群 社交互动关系 友谊网络、空手道俱乐部
信息网络（Information Network） 网页或文档 超链接、引用、交叉引用 Web 链接网络
交通网络（Transportation Network） 目的地 直接连接（航线、铁路等） 航线图、地铁图（Figure 2.4a, 2.4b）
依赖网络（Dependency Network） 任务 先后依赖关系（有向边） 课程先修关系（Figure 2.4c）
结构网络（Structural Network） 节点/关节 物理连接 桥梁结构（Figure 2.4d）

关键概念：在画图时，节点的实际空间位置无关紧要——重要的是哪些节点之间有边相连。因此同一个图可以有不同的画法（如 Figure 2.2 和 Figure 2.3 是同一个 13 节点 Arpanet 图的两种不同画法）。

三、路径与连通性（Section 2.2: Paths and Connectivity）

3.1 路径（Path）

定义：图中的一条路径（Path） 是一个节点序列，其中每对连续节点之间都由一条边相连。

要点： - 路径可以重复经过同一节点（一般情况下的路径定义） - 简单路径（Simple Path）：不重复经过任何节点的路径 - 路径体现了图中"事物沿边从一个节点移动到另一个节点"的核心思想——信息传递、航班旅行、网页跳转等

案例：在 1970 年 Arpanet 图中，MIT → BBN → RAND → UCLA 是一条路径，CASE → LINCOLN → MIT → UTAH → SRI → UCSB 也是一条路径。

3.2 环（Cycle）

定义：环（Cycle） 是一种特殊的非简单路径，形成一个"环形"结构——首尾节点相同，且至少包含三条边，中间所有节点各不相同。

重要性： - 通信和交通网络中，环的存在提供了冗余性（Redundancy）——如果某条边失效，可以沿环的"另一个方向"绕行 - 1970 年 Arpanet 的每条边都属于至少一个环，这是刻意设计的：即使一条线路被切断，任何节点仍可到达其他任何节点 - 社交网络中也常见环结构：例如发现妻子的表亲的高中好友恰好是自己兄弟的同事

3.3 连通性（Connectivity）

定义：如果图中每对节点之间都存在一条路径，则称该图是连通的（Connected）。

要点： - 通信和交通网络通常期望是连通的（因为它们的目标是传输流量） - 社交网络不一定是连通的（可能存在完全无法通过朋友链到达的两个人）

3.4 连通分量（Connected Component）

定义：图的一个连通分量（Connected Component）（简称分量/组件）是满足以下两个条件的节点子集： 1. 内部连通：子集中任意两个节点之间存在路径 2. 最大性：该子集不是某个更大的满足条件(1)的子集的真子集

直觉理解：如果一个图不连通，它会自然分裂为若干个独立的"碎片"，每个碎片就是一个连通分量。

案例： - Figure 2.5 展示了一个有三个连通分量的图：{A, B}、{C, D, E}、{F, G, H, I, J, K, L, M} - Figure 2.6 展示了生物研究中心 SGPP 的合作网络，也有三个连通分量

分量的内部结构： - 将图分解为连通分量只是描述结构的第一步 - 在一个连通分量内部，可能存在更丰富的结构——密集连接的区域、中心节点等 - 移除某个关键节点可能导致一个连通分量分裂成多个分量（例如 Figure 2.6 中最大分量的中心节点）

3.5 巨分量（Giant Component）

定义：巨分量（Giant Component） 是一个非正式术语，指包含图中相当大比例节点的连通分量。

核心性质： - 大规模复杂网络通常拥有一个巨分量 - 当网络中存在巨分量时，几乎总是只有一个 - 原因：如果存在两个巨分量（各含数亿人），只需一条边就能将它们合并为一个——这种边的存在几乎不可避免

巨分量的唯一性论证： - 假设全球社交网络有两个巨分量，各含数亿人 - 只需第一个分量中的一个人与第二个分量中的一个人成为朋友，两个巨分量就合并了 - 在现实中，这样的边必然存在，因此两个共存的巨分量几乎从未在真实网络中观察到

历史案例： - 大约五千年前，全球社交网络可能有两个巨分量——美洲与欧亚大陆 - 当欧洲探险家到达西半球时，这两个分量突然合并，结果是灾难性的（技术和疾病的不对称传播）

小规模案例： - Figure 2.7 展示了美国高中生 18 个月内的恋爱关系网络 - 该网络有一个显著的巨分量，对理解性传播疾病的传播至关重要 - 一个只有一个伴侣的学生可能不知不觉地处于巨分量中，成为潜在传播路径的一部分

4.1 路径长度（Path Length）

定义：路径的长度（Length） 是该路径中包含的边的数量（即步数）。

4.2 距离（Distance）

定义：两个节点之间的距离（Distance） 是它们之间最短路径的长度。

案例：在 Arpanet 图（Figure 2.3）中，LINC 与 SRI 之间的距离为 3。

4.3 广度优先搜索（Breadth-First Search, BFS）

定义与过程：广度优先搜索是一种从起始节点出发，逐层向外探索的系统方法，用于确定从一个节点到所有其他节点的距离。

算法步骤（从节点 s 开始）： 1. 将 s 的所有直接邻居声明为距离 1（第 1 层） 2. 将第 1 层节点的所有未被发现的邻居声明为距离 2（第 2 层） 3. 将第 2 层节点的所有未被发现的邻居声明为距离 3（第 3 层） 4. 以此类推，每一层由尚未被发现的、与上一层某节点相邻的所有节点构成

关键特性： - BFS 从起始节点向外搜索，先到达近的节点，后到达远的节点 - 每个节点只被"发现"一次，发现时所在层即为其到起始节点的距离 - BFS 不仅是一种计算距离的方法，也是按距离组织图结构的概念框架

案例（Figure 2.9）：从 MIT 出发对 Arpanet 进行 BFS： - 距离 1（第 1 层）：UTAH, BBN, LINC - 距离 2（第 2 层）：SRI, SDC, RAND, HARV, CASE - 距离 3（第 3 层）：UCSB, STAN, UCLA, CARN

4.4 小世界现象（The Small-World Phenomenon）

核心观察：在典型的大型网络中，不仅大部分节点属于同一个巨分量（即存在路径相连），而且这些路径出乎意料地短。

六度分隔（Six Degrees of Separation）： - 该概念源于 John Guare 的戏剧 - 核心思想：地球上任意两个人之间，平均只需经过大约六个中间人即可建立联系

Milgram 实验（1960s）： - 实验设计：Stanley Milgram 选择 296 个随机"出发者"，要求他们通过转寄信件（每次只转给认识的人），将信送到波士顿郊区的一位目标人物（股票经纪人） - 实验结果：64 封信成功到达目标；成功链的中位长度为 6（Figure 2.10） - 实验意义：这是第一个实验性地验证"小世界"假说的研究 - 实验局限： - 目标只是一个人，且是相对富裕的人群 - 许多信件未能到达目标 - 重复实验因参与率低而困难

Milgram 的洞见：如果每个人是自己社交"世界"的中心，那么"六步之遥"实际上意味着"六个世界之隔"——这让"六"这个数字的含义比表面看起来要大得多。

4.5 小世界现象的现代验证

（1）Microsoft 即时通讯网络研究 - 研究者：Jure Leskovec 和 Eric Horvitz - 数据：2.4 亿活跃 Microsoft Instant Messenger 用户账户 - 边的定义：两个用户在一个月观察期内进行过双向对话 - 结果： - 网络有一个包含几乎所有节点的巨分量 - 巨分量内的距离非常短 - 平均距离约 6.6，中位距离为 7 - Figure 2.11 展示了距离分布（对数坐标），峰值在 6-7 附近 - 局限：该网络只追踪有即时通讯工具的人，且基于通信行为而非真正的友谊关系

（2）Erdős 数（Erdős Number） - 数学家 Paul Erdős 一生发表约 1500 篇论文，是数学合作网络的中心人物 - Erdős 数：一个数学家到 Erdős 在合作图中的距离 - 大多数数学家的 Erdős 数不超过 4 或 5 - 跨学科延伸：Einstein 的 Erdős 数为 2，Fermi 为 3，Chomsky 和 Pauling 为 4 - 说明科学界确实是一个"小世界"

（3）Bacon 数（Bacon Number） - 类似 Erdős 数，但针对好莱坞演员合作网络 - 节点是演员，如果两个演员共同出演过电影则有边相连 - Bacon 数：演员到 Kevin Bacon 在该图中的距离 - IMDB 中所有演员的平均 Bacon 数约为 2.9，很难找到大于 5 的 - 进一步证实了"小世界"在各种网络中普遍存在

五、网络数据集概述（Section 2.4: Network Datasets: An Overview）

5.1 研究网络数据集的动机

研究某个网络数据集可能有三种不同但往往共存的动机： 1. 领域关注：关心数据本身所在的具体领域 2. 代理作用：将该数据集作为难以直接测量的更大网络的近似 3. 普遍规律：寻找跨越不同领域的共同网络属性

5.2 大规模网络数据集的五大类型

（1）合作图（Collaboration Graphs） - 记录谁与谁合作的网络 - 典型案例： - 科学共同作者网络 - 演员共同出演网络 - 企业董事会共同任职网络（Fortune 500 公司） - Wikipedia 编辑合作网络 - 魔兽世界玩家合作网络 - 研究价值：合作网络提供了长期社交互动的详细快照，可追踪跨越一个世纪的学科内合作模式

（2）谁和谁通话图（Who-Talks-to-Whom Graphs） - 捕获通信模式的网络 - 典型案例： - Microsoft IM 网络（2.4 亿用户） - 企业内部电子邮件日志 - 大学电子邮件网络 - 电话通话记录图（Call Graphs） - 面对面接触图（通过蓝牙手机记录物理接近） - 隐私问题：这类网络中的节点通常是有强烈隐私期望的个人——通信痕迹可被用于重建行为细节，因此研究受到严格限制 - 经济延伸：经济网络测量记录市场或金融社区的"谁和谁交易"结构，可用于研究不同的市场准入水平如何导致不同的市场力量和价格

（3）信息链接图（Information Linkage Graphs） - Web 快照是典型的信息链接网络：节点是网页，有向边代表从一个页面到另一个页面的链接 - Web 数据特点： - 规模极大（数十亿信息片段） - 多样性极高（个人页面、企业页面、政府页面等） - 不仅是信息本身，背后还有复杂的社会和经济结构 - 研究实践：由于全 Web 规模过大，很多研究集中在有趣的子集上——博客链接网络、Wikipedia 页面、社交网站页面、购物网站评论等 - 引用网络（Citation Networks）：信息链接图的研究远早于 Web——引用分析从 20 世纪初就开始研究科学论文或专利之间的引用网络结构

（4）技术网络（Technological Networks） - Web 虽然建立在技术之上，但本质是人类创造的思想、信息和社会经济结构在技术上的投射 - 更纯粹的技术网络： - 互联网：节点是路由器/计算机，边是物理连接 - 电力网：节点是发电站，边是输电线路 - 互联网有两个层次：底层是设备级物理连接图；高层是自治系统图（AS Graph）——节点是ISP（互联网服务提供商），边代表ISP之间的数据传输协议

（5）自然界中的网络（Networks in the Natural World） - 生物学和自然科学中广泛存在图结构，涉及从种群到分子的多个尺度：

尺度 网络类型 节点 边 说明
种群 食物网（Food Web） 物种 捕食关系（有向边：A→B 表示 A 吃 B） 可用于推理级联灭绝
器官 神经网络（Neural Network） 神经元 神经连接 线虫 C. Elegans 的完整脑图（302 节点，~7000 边）已被绘制
分子 代谢网络（Metabolic Network） 化合物 化学反应关系 可揭示细胞内的复杂反应通路和调节反馈环

六、课后习题中的重要概念（Section 2.5: Exercises）

6.1 关键节点（Pivotal Node）

定义：对于两个不同节点 Y 和 Z，如果节点 X（X ≠ Y 且 X ≠ Z）出现在 Y 和 Z 之间的每一条最短路径上，则称 X 对 (Y, Z) 对是关键的（Pivotal）。

案例（Figure 2.13）： - 节点 B 对两个节点对是关键的：(A, C) 和 (A, D) - 节点 D 对任何节点对都不是关键的 - 注意：B 对 (D, E) 不是关键的，因为存在不经过 B 的最短路径（通过 C 和 F）

6.2 守门人（Gatekeeper）与局部守门人（Local Gatekeeper）

守门人（Gatekeeper）： - 定义：如果对于某两个节点 Y 和 Z，从 Y 到 Z 的每一条路径（不仅是最短路径）都经过 X，则称 X 是守门人 - 这是一个"全局"概念——需要考虑图中的所有路径

局部守门人（Local Gatekeeper）： - 定义：如果节点 X 有两个邻居 Y 和 Z，且 Y 与 Z 之间没有边，则 X 是局部守门人 - 这是一个"局部"概念——只需检查邻居之间的连接情况

关系：守门人一定是局部守门人，但局部守门人不一定是守门人。

案例（Figure 2.14）： - 节点 A 既是守门人又是局部守门人 - 节点 D 是局部守门人（邻居 B 和 C 之间无边），但不是守门人（B 和 C 之间存在不经过 D 的路径）

6.3 直径与平均距离

直径（Diameter）：图中任意两个节点之间最大距离。

平均距离（Average Distance）：图中所有节点对之间距离的算术平均值。

关键洞察：在许多图中直径和平均距离接近，但也存在两者差异极大的图——可以构造直径超过平均距离 3 倍甚至任意倍数的图。

七、关键术语汇总

英文术语 中文翻译 简要说明
Graph 图 由节点和边组成的结构
Node (Vertex) 节点（顶点） 图中的对象
Edge (Link) 边（链接） 连接两个节点的关系
Neighbor 邻居 由边直接相连的节点
Undirected Graph 无向图 边是对称的图
Directed Graph 有向图 边有方向的图
Directed Edge 有向边 从一个节点指向另一个节点的边
Path 路径 每对连续节点间有边相连的节点序列
Simple Path 简单路径 不重复经过任何节点的路径
Cycle 环 首尾相同、中间不重复的路径（≥3 边）
Connected 连通 任意两节点间存在路径
Connected Component 连通分量 最大的内部连通节点子集
Giant Component 巨分量 包含网络中大部分节点的连通分量
Path Length 路径长度 路径中的边数
Distance 距离 两节点间最短路径的长度
Breadth-First Search (BFS) 广度优先搜索 逐层向外探索的图搜索算法
Small-World Phenomenon 小世界现象 大型网络中任意两节点间路径极短
Six Degrees of Separation 六度分隔 任意两人约需六个中间人即可连接
Erdős Number Erdős 数 数学家到 Erdős 在合作图中的距离
Bacon Number Bacon 数 演员到 Kevin Bacon 在合作图中的距离
Collaboration Graph 合作图 记录合作关系的网络
Communication Network 通信网络 节点间可传递消息的网络
Information Network 信息网络 信息资源通过链接相连的网络
Transportation Network 交通网络 目的地之间有直接连接的网络
Dependency Network 依赖网络 任务间先后依赖关系的有向网络
Food Web 食物网 物种间捕食关系的有向网络
Neural Network 神经网络 神经元间连接的网络
Metabolic Network 代谢网络 化合物间化学反应关系的网络
AS Graph 自治系统图 ISP 间数据传输协议关系的网络
Citation Network 引用网络 论文/专利间引用关系的网络
Call Graph 通话记录图 基于电话通话记录的网络
Pivotal Node 关键节点 出现在某节点对所有最短路径上的节点
Gatekeeper 守门人 某节点对的所有路径都必须经过的节点
Local Gatekeeper 局部守门人 有两个不相连邻居的节点
Diameter 直径 图中任意两节点间的最大距离
Average Distance 平均距离 所有节点对距离的算术平均值