COMP5313 - Chapter 18 Power Laws and Rich-Get-Richer Phenomena 幂律与富者愈富
Chapter 18: Power Laws and Rich-Get-Richer Phenomena（幂律与富者愈富）
教材：Networks, Crowds, and Markets: Reasoning about a Highly Connected World 作者：David Easley & Jon Kleinberg, Cambridge University Press, 2010
一、核心问题：为什么流行度如此不均衡
这一章讨论的是流行度 (popularity) 的分布。
典型现象：
- 大多数网页、书、论文、歌曲、城市都只获得很少关注；
- 少数对象获得非常多关注；
- 极少数对象获得超级巨大的关注。
在 Web 中，网页的流行度可以用 in-links（入链数量） 衡量：
\[ k = \text{number of in-links to a page}. \]
核心问题是：
作为 \(k\) 的函数，有多少比例的网页拥有 \(k\) 条入链？
也就是研究：
\[ f(k) = \Pr[\text{a page has } k \text{ in-links}]. \]
这看起来像一个普通统计问题，但结果非常重要：流行度分布不是普通的钟形曲线，而是幂律。
二、为什么 normal distribution 不适合解释流行度
一个自然猜想是：网页入链数是否服从正态分布 (normal/Gaussian distribution)？
正态分布的基本特征是：
- 大多数值集中在平均值附近；
- 偏离平均值很多的极端值非常少；
- 尾部下降很快，通常是指数级下降。
中心极限定理 (Central Limit Theorem) 给出正态分布常见的原因：
如果一个量是许多小的、独立随机因素相加而成，那么它通常近似服从正态分布。
如果 Web 链接是这样产生的：
- 每个网页独立随机决定是否链接到另一个网页；
- 某个网页的入链数是很多独立随机变量的和；
那么入链数应该近似正态分布，极高入链数的网页会极其罕见。
但真实 Web 数据不是这样。
三、幂律分布 (Power Law)
真实测量发现，拥有 \(k\) 条入链的网页比例大约满足：
\[ f(k) \propto \frac{1}{k^c}, \]
其中 \(c\) 通常略大于 \(2\)。在教材例子中，Web 入链分布近似为：
\[ f(k) \propto \frac{1}{k^2}. \]
这类形式称为 power law（幂律）。
3.1 幂律和指数下降的差别
幂律下降得很慢：
\[ \frac{1}{k^2} \]
当 \(k=1000\) 时仍然是：
\[ \frac{1}{1000^2} = \frac{1}{1,000,000}. \]
但指数下降如：
\[ 2^{-k} \]
在 \(k=1000\) 时几乎小到不可见。
所以幂律分布的核心含义是：
极端热门对象不是异常，而是会以可观概率出现。
这解释了为什么 Web 上会有 Google、Wikipedia 这类拥有巨大入链数的页面，也解释了为什么论文引用、电话呼叫、图书销量等流行度指标经常出现极端不均衡。
四、如何检测幂律：log-log plot
假设：
\[ f(k) = \frac{a}{k^c}. \]
写成：
\[ f(k) = ak^{-c}. \]
两边取对数：
\[ \log f(k) = \log a - c \log k. \]
这是一条直线形式：
\[ y = b + mx, \]
其中：
- \(y = \log f(k)\)；
- \(x = \log k\)；
- 截距为 \(\log a\)；
- 斜率为 \(-c\)。
所以检测幂律的常用方法是：
- 横轴画 \(\log k\)；
- 纵轴画 \(\log f(k)\)；
- 如果图像近似一条直线，则数据可能符合幂律；
- 直线斜率的绝对值就是幂律指数 \(c\)。
考试要点：
幂律在 log-log plot 上表现为直线；斜率越负，尾部下降越快。
五、富者愈富模型 (Rich-Get-Richer Model)
幂律为什么会出现？教材给出的核心机制是：
流行度越高，未来越容易获得更多关注。
这叫 rich-get-richer effect（富者愈富效应），也叫 preferential attachment（优先连接）。
5.1 Web 链接复制模型
假设网页按顺序生成：
\[ 1,2,3,\ldots,N. \]
当新网页 \(j\) 生成时，它向一个已有网页创建一条链接。规则如下：
- 以概率 \(p\)，网页 \(j\) 从所有早期网页中均匀随机选一个网页 \(i\)，并链接到 \(i\)；
- 以概率 \(1-p\)，网页 \(j\) 从所有早期网页中均匀随机选一个网页 \(i\)，但不链接到 \(i\)，而是复制 \(i\) 的链接，链接到 \(i\) 指向的网页。
第二步是关键。它表示：
新网页作者会模仿已有网页作者的链接选择。
如果某个网页已经有很多入链，那么随机选到一个指向它的网页的概率就更高；复制这个网页的链接时，就更可能继续链接到它。
因此：
\[ \Pr[\text{new link points to page } x] \propto \text{current in-links of } x. \]
这就是 preferential attachment：
一个节点获得新链接的概率与它当前已有的链接数成正比。
六、为什么富者愈富会产生幂律
富者愈富的增长逻辑类似复利：
\[ \text{growth rate} \propto \text{current popularity}. \]
如果一个网页早期因为随机波动稍微领先，它之后会更容易被复制和链接，从而进一步扩大领先优势。
和正态分布背后的独立随机因素不同：
- 正态分布中，随机误差容易相互抵消；
- 富者愈富中，早期优势会被反馈机制放大。
这就是幂律产生的直觉基础。
七、富者愈富效应的不可预测性
富者愈富不仅会产生不平等，也会产生不可预测性 (unpredictability)。
原因是：
早期随机波动会被后续反馈放大。
一个网页、一本书、一首歌是否爆红，可能取决于早期很小的偶然优势。一旦优势形成，rich-get-richer 会继续推动它变得更热门。
7.1 音乐下载实验
Salganik, Dodds, and Watts 做过一个实验：
- 建立一个音乐下载网站；
- 放入 48 首不知名歌曲；
- 访问者可以试听并下载；
- 用户会看到每首歌当前的下载次数；
- 但用户被随机分配到 8 个互相独立的“平行世界”版本。
每个平行世界一开始完全相同，但之后会因为用户行为而独立演化。
结果：
- 不同平行世界中，歌曲的市场份额差异很大；
- 好歌一般不会垫底，差歌一般不会登顶；
- 但具体哪首歌最火，很难预测。
实验还设置了一个没有下载次数反馈的版本。没有反馈时，歌曲之间的市场份额差异明显更小。
结论：
社会反馈会增加结果的不平等，也会增加成功路径的不确定性。
八、幂律与信息级联的关系
信息级联和富者愈富有共同点：
- 都由人群中的相互影响产生；
- 都可能让早期少量信息被放大；
- 都可能导致结果对初始条件敏感。
但两者也有区别：
| 模型 | 选择对象 | 机制 |
|---|---|---|
| 信息级联 | 通常是两个选择，如 accept/reject | 个体根据前人行为做贝叶斯推断 |
| 富者愈富 | 很多可选对象，如网页、歌曲、书 | 后来者复制或偏向已有热门选择 |
教材指出，一个更深的问题是：
能否把富者愈富的复制行为，也从更基础的理性决策模型中推导出来？
这可以理解为：流行度幂律可能来自许多相互竞争的信息级联。
九、长尾 (The Long Tail)
幂律分布不仅解释头部超级热门对象，也解释尾部大量小众对象。
媒体产业中的问题是：
销售额主要来自少数爆款，还是来自大量小众产品的总和？
传统实体店受空间限制，只能摆放热门商品；但互联网平台如 Amazon、Netflix 可以储存和展示巨大库存，因此可以从大量小众商品中获得可观收益。
这就是 Long Tail（长尾）。
9.1 从 popularity plot 到 rank plot
前面研究的是：
\[ f(k) = \text{拥有 popularity } k \text{ 的对象比例}. \]
长尾讨论更常用 rank plot / Zipf plot：
- 第 1 名最热门；
- 第 2 名次热门；
- 第 \(j\) 名的销量为 \(k\)。
横轴是排名 \(j\)，纵轴是销量 \(k\)。
如果曲线向右缓慢下降，说明虽然每个小众产品销量不高，但右侧尾部很长，累计起来可能很重要。
9.2 长尾的商业含义
曲线左侧面积代表爆款产品贡献；
\[ \text{hits revenue} \]
曲线右侧面积代表小众产品贡献；
\[ \text{niche products revenue}. \]
如果右侧总面积很大，平台就可以通过大量小众产品获利。
考试理解：
幂律既说明头部超级热门对象存在，也说明尾部大量小众对象合起来可能有重要规模。
十、搜索工具和推荐系统的影响
搜索引擎和推荐系统对富者愈富有双重影响。
10.1 可能放大富者愈富
如果搜索引擎总是把热门页面排在前面，那么：
- 热门页面更容易被用户看到；
- 用户更可能继续链接或点击这些页面；
- 这些页面变得更热门；
- 排名继续升高。
这会进一步强化不平等。
10.2 也可能削弱富者愈富
另一方面，用户搜索的 query 非常多样化。对于小众 query，搜索工具可能帮助用户发现原本很难通过浏览找到的小众页面。
推荐系统也是如此：
- 如果只推荐热门内容，会强化头部；
- 如果根据用户兴趣推荐小众内容，就能帮助长尾产品被发现。
所以搜索和推荐系统是更高层次的反馈机制：
它们可以放大、削弱，甚至重新塑造 rich-get-richer dynamics。
十一、可选推导：富者愈富模型的幂律指数
这一节对应教材 18.7 Advanced Material。考试若不要求推导，理解结论即可。
设页面 \(j\) 在时间 \(t\) 的入链数为 \(X_j(t)\)。用连续函数 \(x_j(t)\) 近似它。
新链接指向页面 \(j\) 的概率由两部分组成：
- 均匀随机选择：概率贡献 \(\frac{p}{t}\)；
- 富者愈富选择：概率贡献 \(\frac{(1-p)x_j(t)}{t}\)。
因此近似增长方程为：
\[ \frac{dx_j}{dt} = \frac{p}{t} + \frac{(1-p)x_j}{t}. \]
令：
\[ q = 1-p. \]
则：
\[ \frac{dx_j}{dt} = \frac{p+q x_j}{t}. \]
解这个微分方程并使用初始条件 \(x_j(j)=0\)，得到：
\[ x_j(t) = \frac{p}{q} \left[ \left(\frac{t}{j}\right)^q - 1 \right]. \]
由此可以推出，入链数至少为 \(k\) 的节点比例近似满足：
\[ F(k) \propto k^{-1/q}. \]
因此入链数恰好为 \(k\) 的节点比例满足：
\[ f(k) \propto k^{-(1+1/q)}. \]
因为 \(q=1-p\)，幂律指数为：
\[ c = 1 + \frac{1}{1-p}. \]
解释：
- 当 \(p \to 1\) 时，几乎都是均匀随机链接，富者愈富很弱，\(c \to \infty\)，极端热门节点变少；
- 当 \(p \to 0\) 时，几乎都是复制/优先连接，富者愈富很强，\(c \to 2\)，极端热门节点更常见。
十二、本章考试级总结
- 流行度通常不是正态分布，而是幂律分布。
- 幂律形式：
\[ f(k) \propto \frac{1}{k^c}. \]
- 幂律在 log-log plot 上表现为直线，斜率为 \(-c\)。
- 幂律尾部下降慢，所以极端热门对象会以非忽略概率出现。
- 富者愈富/优先连接机制：
\[ \Pr[\text{new link to } x] \propto \text{current popularity of } x. \]
- 富者愈富会放大早期随机优势，因此结果既不平等又不完全可预测。
- 长尾说明大量小众对象的总贡献可能非常大。
- 搜索和推荐系统既可能强化头部，也可能帮助用户发现长尾。
十三、常见坑点
- 不要把幂律和正态分布混淆：正态分布尾部下降快，幂律尾部下降慢。
- 不要只看平均值：在幂律分布中，平均值可能无法代表典型对象。
- log-log 直线不等于普通坐标直线：检测幂律必须在对数坐标上看。
- 富者愈富不是说质量不重要：质量可能影响初始成功，但社会反馈会放大早期差异。
- 长尾不是否认爆款重要：它强调尾部小众产品累计起来也可能重要。