Day 03：幂律、重尾和 hub
Day 03：幂律、重尾和 hub
1. 一句话定义
幂律 power law 表示尾部概率按幂函数下降，例如 P(D > x) ~ x^{-alpha}。
2. 解决什么问题
它解释为什么真实网络中会出现少数极端高度数节点。
在很多真实网络中：
- 大多数节点连接很少；
- 少数节点连接非常多；
- 最大度数远高于平均度。
这类现象不能只用平均值解释，需要看尾部。
3. 专业表达
RGCN 中常用类似记号：
P(D > x) = L(x) x^{-(tau-1)}
其中：
D是度数；P(D > x)是尾部分布；tau是幂律指数；L(x)是 slowly varying function，入门阶段可先理解为“变化很慢的修正项”。
4. 极值公式
如果有 n 个节点，最大度数的典型量级来自：
n P(D > x_n) approx 1
若：
P(D > x) approx x^{-(tau-1)}
则：
x_n approx n^{1/(tau-1)}
这说明 tau 越小，最大度数增长越快，hub 越极端。
5. 典型场景
- 社交网络中的超级用户；
- 互联网中的核心路由节点；
- 引用网络中的高被引论文；
- 网页网络中的高 PageRank 页面。
6. 交流时可以怎么说
如果 degree distribution 具有 power-law tail，那么最大度数不是普通异常值，而是网络规模增大后自然会出现的极值现象。
7. 可以追问老师/同学的问题
- 这里说的 power law 是经验观察，还是有统计检验支持？
- 应该看 PMF 还是 CCDF？
tau的估计对阈值选择有多敏感？
8. 今日任务
打开 ../../07_notebooks/rgcn_01_extreme_scaling.ipynb，只看第一部分。
写下：
- 幂律尾部和指数尾部的最大值有什么不同？
- 为什么最大值可以用
n P(X > x_n) approx 1理解？