推导方法速查

综合实践 · 08_资料库/RGCN_推导方法速查.md

1. 最大值量级：先让期望超过次数等于 1

直觉解释：如果 n 个样本中大约有 1 个会超过 x_n，那么最大值通常就在 x_n 附近。

专业表达：

令 M_n = max(X_1, ..., X_n)。若 P(X > x) ~ x^{-alpha}，用


n P(X > x_n) approx 1

得到


x_n approx n^{1/alpha}

在 RGCN 的记号里常写 alpha = tau - 1，所以最大度数或最大权重量级是


n^{1/(tau-1)}

应用场景：最大度数、最大权重、极端 hub。

直觉解释：一个节点要和 n-1 个其他节点分别尝试连边，每次成功概率是 lambda/n。试验很多，但每次概率很小，所以 Binomial 近似 Poisson。

专业表达：


D_v ~ Bin(n-1, lambda/n) -> Poisson(lambda)

应用场景：说明 ER 图是基准模型，但它的尾部太轻，不能自然产生大量 hub。

直觉解释：如果某类坏事件的期望个数趋近 0，那么大概率没有坏事件。

专业表达：


P(X >= 1) <= E[X]

应用场景：证明大分量不存在、证明过长路径或过大团的概率很小。

直觉解释：不仅要知道期望大，还要知道随机波动不太大。

专业表达：


P(X > 0) >= E[X]^2 / E[X^2]

应用场景：证明某种结构大概率存在，例如某些大小的连通分量。

直觉解释：把两个随机过程放在同一个概率空间里比较，让一个过程总是压住另一个。

专业表达：用 stochastic domination 给随机图探索过程找上界或下界。

应用场景：把连通分量探索过程和 branching process 比较。

直觉解释：在稀疏大图中，从一个节点向外探索，早期很少碰回已经见过的点，所以像一棵树。

专业表达：用 Galton-Watson process 或 multi-type branching process 近似局部邻域。

应用场景：巨分量条件、局部收敛、典型距离。

直觉解释：随机选一个人和随机选一条边再看边的另一端，看到的度数分布不一样。沿边更容易撞到朋友多的人。

专业表达：


P(D* = k) = k P(D = k) / E[D]

其中 D* 是 size-biased degree。

应用场景：configuration model 的探索过程、forward degree、巨分量阈值。

直觉解释：要证明两点距离不太短，就数短路径的期望条数；要证明距离不太长，就构造或估计能连上的路径。

专业表达：估计长度为 k 的 self-avoiding paths 数量及其出现概率。

应用场景：Volume II 中 small-world 距离上下界。

直觉解释：全图很复杂，但随机选一个点，只看它周围有限层，结构可能稳定地像某棵随机树。

专业表达：rooted graph 的局部邻域分布收敛。

应用场景：把有限随机图的局部问题转为无限随机树问题。

报告中可以按这个顺序写：