COMP5313 Tutorial 11 - Network Dynamics 题解
Week 11 Tutorial: Network Dynamics 题解
课程：COMP5313/COMP4313 — Large Scale Networks, S1 2026 主题：网络动力学 —— 幂律分布（power law）与去中心化搜索（decentralised search） 依据教材 Networks, Crowds, and Markets（Easley & Kleinberg）第 18、20 章，以及 Chord/一致性哈希
本次 tutorial 复习网络动力学部分的三块内容：幂律分布、小世界现象，以及把去中心化搜索思想落到分布式系统里的 Chord DHT。下面逐题给出答案与解析。
一、预备知识回顾
1.1 幂律分布与「富者愈富」
幂律分布（power law）：某个量取值为 \(k\) 的对象所占比例约为
\[f(k) \approx a\,k^{-c}\]
其中指数 \(c\) 在网页入链等场景常略大于 2。它的尾部比正态/指数分布衰减得慢得多，所以极端流行的对象（爆款）不是异常值，而是结构性的必然结果。
产生幂律的核心机制是 优先连接（preferential attachment）/ 富者愈富（rich-get-richer）：一个对象越流行，就越容易被进一步选择，从而进一步变流行，形成正反馈。任何让流行度变得可见的设计（排行榜、播放量、点赞数、点击计数器）都会强化这种正反馈，使分布更接近幂律。
1.2 小世界现象、强弱联系与去中心化搜索
- 小世界现象（small world）：大型网络中大多数节点对之间存在很短的路径（「六度分隔」）。注意是「大多数」而非「所有」。
- 强联系 vs 弱联系：强联系（close friends）因三元闭包而高度重叠 —— 你的好友彼此多半也认识，信息冗余；弱联系（acquaintances / distant friends）往往跨越不同社群，是连接不同 cluster 的捷径，带来非冗余信息。这正是「弱联系的力量」（Granovetter）。
1.3 Chord DHT 与一致性哈希
- 把节点 ID 与文件 key 都哈希到同一个大小为 \(2^m\) 的环形 ID 空间。
- key \(k\) 由其 successor（顺时针方向第一个 \(\text{ID} \ge k\) 的节点）负责。
- 每个节点维护一张 finger table：节点 \(i\) 的第 \(j\) 项指向
\[\text{finger}[j] = \text{successor}\big((i + 2^{\,j-1}) \bmod 2^m\big), \qquad j = 1,\dots,m\]
即提供 \(1,2,4,8,\dots\) 这些不同尺度的「跳跃边」。 - lookup 路由原则：Go as far as possible, but never pass the target —— 转发给 finger table 中不越过目标的最大节点。每跳至少把到目标的距离减半，因此 lookup 的消息数为 \(O(\log_2 n)\)。
二、题解
Exercise 1：Power Law（幂律分布）
题目：某新闻网站（如 CNN、NYT）首页有指向大量文章的链接，运营者关心文章的流行度分布：「作为 \(k\) 的函数，有多少比例的文章被恰好 \(k\) 个人浏览过？」。现在网站打算改版，在每个链接旁显示一个点击计数器（如「30,480 人已阅读」，并实时更新）。
(1) 这个改动会如何影响用户行为？
答案：人们更倾向于点击旁边数字最大的链接。
解析：计数器把「流行度」变成了公开可见的信号。在信息不充分时，用户会把「别人读得多」当作「这篇值得读」的线索（类似信息级联里的从众）。于是注意力进一步向已经热门的文章集中。
(2) 加上这个功能后，文章流行度分布会更接近还是更不接近幂律？为什么？
答案：会更接近幂律分布。因为人们更可能去点击浏览量已经最高的页面。
解析：计数器把流行度反馈给了用户，制造了 rich-get-richer / 优先连接 的正反馈 —— 已经热门的文章获得更多点击、数字更大、又吸引更多点击。这种「按当前流行度成比例地获得新流行度」的机制，正是幂律分布的生成原因，因此分布会更接近 \(f(k)\approx a\,k^{-c}\)。反之，若不显示计数器，用户选择更分散、更接近独立随机，分布的重尾会被削弱。
(Duration: 10 min)
Exercise 2：Small World（小世界）
题目：经典「六度分隔」问的是：社交网络里大多数人对之间是否存在长度不超过 6 的路径（边表示两人以名相称地认识）。现在做一个变体：让每个人列出自己最熟的 30 个人，按熟悉程度降序排列（假设每人都能列满 30 人），并据此构造两个有向网络：
- close-friend 网络：每人只向列表中最熟的前 10 人连有向边；
- distant-friend 网络：每人只向列表中第 21–30 位的人连有向边。
(1) 在 close-friend 网络中，是否「每一对」人之间都很可能存在长度 ≤ 6 的路径？
答案：不会。小世界现象说的是大多数（MOST）人对之间存在 ≤ 6 的路径，而不是所有。总会存在一些相距很远的人对，其最短距离大于 6。
解析：这是对小世界陈述的精确理解 —— 它是关于「绝大多数节点对」的统计性质，而非对每一对都成立的全称命题。尤其在只保留强联系（前 10 名）的网络里，捷径很少，更容易出现距离 > 6 的边缘人对。
(2) 设 \(C\) = close-friend 网络中一个人 6 步内平均能到达的人数，\(D\) = distant-friend 网络中的对应值（对全体取平均）。实证研究通常发现 \(C\)、\(D\) 中有一个一致地更大。你认为哪个更大？简述理由。
答案：\(D > C\)。因为「远距离朋友」这类弱联系连接到不同的 cluster，而你最熟的朋友们彼此往往也互相认识。
解析：
- close-friend（强联系）网络中存在强烈的 三元闭包 / 重叠：你的前 10 名好友很可能彼此也是好友，于是从你出发几步能到的人高度重复，可达集合扩张慢 → \(C\) 小。
- distant-friend（弱联系）网络中的边更像 捷径（long-range / weak ties），跳到与你社群不同的人群里，重叠少、每一步都打开新的、非冗余的人群 → 可达集合扩张快 → \(D\) 大。
这正是「弱联系的力量」在去中心化扩散上的体现：弱联系虽不亲密，却对短路径与信息传播至关重要，故 \(D > C\)。
(Duration: 20 min)
Exercise 3：P2P Overlays（Chord DHT）
背景（Figure 1）：16 个节点编号 \(1,2,\dots,16\) 顺时针均匀排布在一个环形 overlay 上（ID 空间大小 \(2^m=16\)，即 \(m=4\)；编号 16 等价于位置 0）。本题所有节点都在线，因此 \(\text{successor}(x)\) 就是 \(x\) 本身（其中 \(17\equiv 1,\,18\equiv 2,\dots\)）。
(1) 实现 Chord DHT，每个节点的 finger table 应有几项？
答案：\(\log_2 16 = 4\) 项。
解析：finger table 的项数等于 ID 用的位数 \(m\)。这里 \(2^m = 16 \Rightarrow m = \log_2 16 = 4\)，对应偏移量 \(2^0,2^1,2^2,2^3 = 1,2,4,8\)。
(2) 画出节点 5 和节点 14 的出向 finger 边。
用公式 \(\text{finger}[j]=\text{successor}\big((i+2^{\,j-1})\bmod 16\big)\) 计算（所有节点在线，successor 即取模后的编号）：
为什么 \(j\) 只到 4、没有 \(j=5\)？ finger table 的项数恒等于 \(m\)（由 ID 空间位数决定，本题 \(2^m=16\Rightarrow m=4\)），与节点的编号无关。所以无论是节点 5、节点 14 还是任何节点，\(j\) 都只取 \(1,2,3,4\)，对应偏移量 \(2^{0},2^{1},2^{2},2^{3}=1,2,4,8\)。这里的「5」是节点 id \(i\)，不是表项数——别把节点编号和索引 \(j\) 混淆了。（若 \(m=5\)、ID 空间 \(2^5=32\)，才会有 \(j=5\)。）
节点 5 的 finger table：
| \(j\) | start \(=(5+2^{j-1})\bmod 16\) | successor（finger 指向） |
|---|---|---|
| 1 | 6 | 6 |
| 2 | 7 | 7 |
| 3 | 9 | 9 |
| 4 | 13 | 13 |
→ 节点 5 的出向 finger 边：\(5\to 6,\ 5\to 7,\ 5\to 9,\ 5\to 13\)。
节点 14 的 finger table：
| \(j\) | start \(=(14+2^{j-1})\bmod 16\) | successor（finger 指向） |
|---|---|---|
| 1 | 15 | 15 |
| 2 | 16 | 16 |
| 3 | \(18\equiv 2\) | 2 |
| 4 | \(22\equiv 6\) | 6 |
→ 节点 14 的出向 finger 边：\(14\to 15,\ 14\to 16,\ 14\to 2,\ 14\to 6\)。
（与讲义 Figure 2 一致。）
(3) 节点 1 发起、目标 key 为 16 的 lookup，会经过哪些 finger 边？
答案：\(\langle 1,9\rangle,\ \langle 9,13\rangle,\ \langle 13,15\rangle,\ \langle 15,16\rangle\)。
解析：路由规则是「在不越过目标的前提下尽量走远」——每一步转发给当前节点 finger table 中不超过目标 16 的最大 finger。逐跳追踪：
| 当前节点 | finger table | 不越过 16 的最大 finger | 转发到 |
|---|---|---|---|
| 1 | \(\{2,3,5,9\}\) | 9 | 9 |
| 9 | \(\{10,11,13,1\}\) | 13 | 13 |
| 13 | \(\{14,15,1,5\}\) | 15 | 15 |
| 15 | \(\{16,1,3,7\}\) | 16（即 \(\text{successor}(15)=16\)，恰好负责 key 16） | 16 |
于是路径为 \(1\to 9\to 13\to 15\to 16\)，依次经过 finger 边 \(\langle1,9\rangle,\langle9,13\rangle,\langle13,15\rangle,\langle15,16\rangle\)，共 4 跳命中。
(4) 一次 lookup 最多会触发多少条消息？
答案：\(\log_2 16 = 4\) 条。
解析：每一跳至少把当前节点到目标的环上距离减半（finger 提供 \(1,2,4,8\) 的跳跃尺度），所以从任意节点到任意 key 最多需要 \(\log_2 n\) 跳。此处 \(n=16 \Rightarrow \log_2 16 = 4\)，与 (3) 中的最长路径一致。
(Duration: 20 min)
三、小结
| 主题 | 核心结论 |
|---|---|
| 幂律 | 让流行度可见 → 富者愈富正反馈 → 分布更接近 \(f(k)=ak^{-c}\) |
| 小世界 | 小世界是「大多数」节点对短路径；弱联系（distant friends）跨社群，6 步可达人数 \(D>C\) |
| Chord | finger 项数 \(=m=\log_2 n\)；\(\text{finger}[j]=\text{succ}(i+2^{j-1})\)；路由「不越过目标尽量走远」，消息数 \(O(\log_2 n)\) |