COMP5313 Week 10 Power Law 与 Small World 讲课总结
COMP5313 Week 10 讲课总结：Power Law 与 Small World Search
1. 本讲主题
本讲有两部分：
- Power law distribution：为什么真实网络中少数节点特别流行。
- Small world / decentralized search：怎样构造既有短路径又能被局部搜索找到的网络。
2. Power Law Distribution
老师用网页入链数作为例子。
令 \(f(k)\) 表示有 \(k\) 条入链的网页比例。很多真实网络中：
[ f(k) ]
其中 \(c\) 通常略大于 2。
含义：
- 大多数节点只有很少链接。
- 少数节点有极高 degree。
- tail 比 normal / exponential distribution 厚很多。
3. Power Law 与 Normal Distribution 的区别
Normal distribution 在远离均值时概率下降非常快。
Power law 下降慢得多：
[ ]
所以真实网络中会出现极端热门网页、城市、论文、歌曲等。
4. Log-log Plot 检测 Power Law
从
[ f(k)= ]
两边取 log：
[ f(k)=A-ck ]
如果画 \(\log f(k)\) 对 \(\log k\)：
- 近似直线，说明可能是 power law。
- 斜率是 \(-c\)。
- 截距是 \(\log A\)。
这是数据题可能会问的判断方法。
5. Preferential Attachment
老师用 Web graph 解释 power law 的形成。
核心机制：
节点越流行，未来越容易获得新链接。
一种模型：
- 新网页按顺序加入。
- 它创建出链到旧网页。
- 可能随机选一个旧网页。
- 也可能复制某个旧网页的链接，或以当前入链数成比例地选择目标。
如果节点 \(i\) 当前入链越多，被新节点链接的概率越高，就会产生 power law。
6. Rich-get-richer Effect
Preferential attachment 是 rich-get-richer 的网络版本。
例子：
- 城市人口：大城市增长更快。
- 论文引用：高引用论文更容易被继续引用。
- 音乐下载：早期下载量高的歌更容易继续获得下载。
老师强调这个过程具有不稳定性：
- 早期小差异可能被不断放大。
- 哪个对象最终最流行可能很偶然。
7. Small World 回顾
Small world phenomenon：
- 网络中有很多短路径。
- Milgram 实验说明人们还能用局部信息协作找到短路径。
这引出 decentralized search：
每个节点不知道全图，只知道自己的邻居和目标位置，仍希望把消息转到目标附近。
8. Greedy Routing / Decentralized Search
设每个节点有几何位置，目标节点是 \(t\)。
每一步：
- 当前节点只看自己的邻居。
- 把消息转发给距离目标 \(t\) 最近的邻居。
这叫 greedy routing。
它不保证一定最短，也可能卡住，但它是 decentralized，因为没有全局图信息。
9. Watts-Strogatz 思路
老师讲了一个 small world 构造直觉：
- 节点放在二维 grid 上。
- 基于 homophily 连到地理 / 社会距离近的节点。
- 再加少量 random weak ties。
局部边：
- 产生很多三角形。
- 保留 homophily。
随机弱联系：
- 产生长距离捷径。
- 让网络存在短路径。
但老师强调：纯随机弱联系不一定支持高效 decentralized search，因为随机边缺少可利用的层次结构。
10. Kleinberg Generalized Model
Kleinberg 模型保留二维 grid 和局部边，同时让长程边概率随距离衰减。
若节点 \(u,v\) 的 grid distance 为 \(d(u,v)\)，则：
[ P(uv)d(u,v)^{-q} ]
\(q\) 叫 clustering exponent。
不同 \(q\) 的含义：
- \(q=0\)：完全随机长程边，等价于原始随机弱联系。
- \(q\) 小：长距离边多。
- \(q\) 大：短距离边多。
- 在二维 grid 中，decentralized search 最有效时 \(q=2\)。
11. 为什么二维中 q=2 最好
老师给的是直觉，不要求正式证明。
在二维 grid 中，距离在 \(d\) 到 \(2d\) 的环带内，节点数量大约和 \(d^2\) 成正比。
如果连接概率是：
[ d^{-2} ]
那么“节点数量增长”和“单个节点连接概率下降”大致抵消。
结果：
- 每个距离尺度都有差不多机会获得弱联系。
- 搜索可以先用长边跨大范围，再用中距离边、短距离边逐步接近目标。
- 距离能按常数比例下降。
12. Rank-based Friendship
真实人口分布不均匀，不能直接用二维 uniform grid。
老师介绍 rank-based friendship：
- 对节点 \(v\) 来说，节点 \(w\) 的 rank 是比 \(w\) 更接近 \(v\) 的节点数量。
- 连接到 \(w\) 的概率与 rank 的负幂成比例：
[ P(vw)_v(w)^{-p} ]
在 uniform grid 中，rank 大约等于距离平方，所以 \(p=1\) 对应二维的 \(q=2\)。
结论：
- 高效 decentralized search 需要连接概率与“closer nodes 的数量”成反比。
- 也就是近似 \(1/\text{rank}\)。
13. 考点重点
- 会写 power law：\(f(k)\approx A/k^c\)。
- 会用 log-log plot 判断 power law，斜率为 \(-c\)。
- 会解释 preferential attachment 和 rich-get-richer。
- 会说明 pure random graph 通常不产生 power law。
- 会解释 small world 的三个目标：多三角形、短路径、可 decentralized search。
- 会定义 greedy routing。
- 会写 Kleinberg 长程边概率 \(P(u\to v)\propto d(u,v)^{-q}\)。
- 记住二维 grid 中最优 \(q=2\)。
- 会解释 rank-based friendship 中 \(p=1\) 是 \(q=2\) 的推广。