极值与复杂网络名词表
极值与复杂网络名词表
1. graph / 图
一句话定义：由节点和边组成的结构，用来表示对象之间的关系。
解决什么问题：把真实系统中的连接关系形式化，例如网页链接、社交关系、论文引用。
交流时可以怎么说：这里我把系统抽象成一个 graph，节点表示对象，边表示对象之间的关系。
2. degree / 度数
一句话定义：一个节点连接了多少条边。
解决什么问题：衡量节点在网络中直接连接的规模。
典型场景：社交网络中一个人的好友数，网页网络中一个页面的入链数。
3. degree distribution / 度数分布
一句话定义：随机选一个节点，它的度数服从的分布。
专业表达：令 D_n 表示从 n 个节点中均匀随机选取节点的度数，研究 D_n 的分布极限。
4. empirical degree distribution / 经验度数分布
一句话定义：在一个具体网络中，不同度数节点所占的比例。
应用场景：真实网络数据分析的第一步，通常画 PMF 或 CCDF。
5. CCDF / complementary cumulative distribution function
一句话定义：P(D >= k) 或 P(D > k)，表示度数至少达到某个值的概率。
为什么重要：尾部分布比点概率更稳定，常用于观察幂律尾部。
6. tail distribution / 尾部分布
一句话定义：随机变量超过高阈值的概率，即 P(X > x)。
和极值的关系：尾部越厚，样本最大值越大。
7. power law / 幂律
一句话定义：某个量按幂函数下降，例如 P(X > x) ~ x^{-alpha}。
专业表达：若 P(D > x) = L(x)x^{-(tau-1)}，其中 L(x) slowly varying，则 D 有幂律尾部。
8. scale-free / 无标度
一句话定义：网络没有一个典型的度数尺度，少数节点可以远大于平均水平。
注意：真实数据看起来像幂律，不等于已经严格证明它是幂律。
9. hub / 枢纽节点
一句话定义：度数特别大的节点。
应用场景：传播、搜索、鲁棒性、攻击脆弱性分析。
10. maximum degree / 最大度数
一句话定义：网络中度数最大的节点的度数。
核心公式：若 P(D > x) ~ x^{-(tau-1)}，则 D_max 常为 n^{1/(tau-1)} 量级。
11. order statistics / 顺序统计量
一句话定义：把样本从小到大排序后得到的统计量，最大值就是最后一个顺序统计量。
在本书中的作用：帮助理解最大度数、最大权重和极端 hub。
12. Hill estimator
一句话定义：用样本最大的一部分观测来估计幂律尾部指数的方法。
局限：对选择多少个尾部样本非常敏感，容易受有限样本和截断影响。
13. Erdos-Renyi random graph
一句话定义：每条边独立地以同一概率出现的随机图。
为什么重要：它是基准模型，但度数尾部太轻，通常不能解释复杂网络中的 hub。
14. sparse regime
一句话定义：边数和节点数同阶，平均度保持有限。
典型设定：ER 图中取 p = lambda/n。
15. phase transition / 相变
一句话定义：参数经过临界值时，网络整体结构突然改变。
典型例子：ER 图在 lambda = 1 附近从只有小分量转向出现巨分量。
16. giant component / 巨分量
一句话定义：包含正比例节点的连通分量。
应用场景：网络是否大规模连通、传播是否能扩散到宏观规模。
17. configuration model
一句话定义：给定每个节点的度数后，随机配对 half-edges 生成图。
专业表达：它是保留 degree sequence 的 null model。
18. half-edge
一句话定义：一条边的一半，还没有和另一个 half-edge 配对。
直觉：节点有几个度数，就伸出几根“线头”，再随机把线头两两配对。
19. size-biased degree
一句话定义：沿着一条随机边看到的节点度数分布，会偏向高度数节点。
为什么重要：解释探索过程、分支过程近似和巨分量条件。
20. inhomogeneous random graph
一句话定义：不同节点有不同权重，连接概率依赖节点权重。
和极值的关系：权重分布的尾部会影响最大度数和 hub。
21. preferential attachment
一句话定义：新节点更倾向连接已经有很多连接的旧节点。
专业表达：rich-get-richer mechanism can generate power-law degree distributions.
22. local convergence
一句话定义：从随机节点附近看，大图的局部结构收敛到某种随机树。
学习要求：先理解“局部像树”的直觉，不必先掌握严格度量空间证明。
23. branching process approximation
一句话定义：用分支过程近似从一个节点开始逐层探索邻居的过程。
应用场景：分析连通分量大小、巨分量是否存在、典型距离。
24. typical distance
一句话定义：随机选两个节点，它们之间最短路径长度的典型大小。
和极值的关系：hub 越强，路径越容易通过少数中心节点缩短。
25. doubly logarithmic distance
一句话定义：距离规模像 log log n，比普通 log n 更短。
典型场景：某些无限方差的幂律网络中，极端 hub 强烈缩短路径。
反向链接
数理统计极值