⟨k²⟩/⟨k⟩:友谊悖论、随机游走偏差、传染阈值是同一个数——而它是测度的属性,不是网络的属性
【锚点】这一篇只钉一个判断:友谊悖论、随机游走采样的度偏差、SIR 传染阈值,不是三个现象,是同一个量【⟨k²⟩/⟨k⟩】在三个地方的投影。而多数网络实证结论死于把它当成「网络的属性」——它其实是「测度的属性」。
【显式】第一步,一个恒等式。无向图,度分布 P(k),平均度 ⟨k⟩。随机选一条边、再随机选这条边的一个端点——这个端点的度服从 P_n(k) = k·P(k)/⟨k⟩,于是它的期望度是 ⟨k²⟩/⟨k⟩。Feld (1991) 叫它 friendship paradox:你的朋友平均比你有更多朋友。这不是心理效应,是 size-biased sampling(尺寸偏倚抽样);在更新论里叫 inspection paradox,在教育统计里叫 class-size paradox——同一个数学,三个学科各自命名了一次。
【隐式】第二步,随机游走。无向连通图上的均匀随机游走,平稳分布是 π_i = k_i/(2E) = k_i/(N⟨k⟩)。也就是说:随机游走不是均匀采样节点,它是按度采样节点。任何用随机游走 / BFS / 滚雪球采样的网络测量,测出来的「平均度」是 ⟨k²⟩/⟨k⟩,不是 ⟨k⟩。两个看起来无关的事实其实是同一件事:随机游走访问一个节点的频率,等于随机选一条边落到该节点的概率。
【细微】第三步,传染阈值。SIR/SIS 在异质网络上的阈值 λ_c = ⟨k⟩/⟨k²⟩(Pastor-Satorras & Vespignani 2001)。注意这个分母——就是上一步那个加权。所谓「无标度网络没有阈值」,翻译过来是「⟨k²⟩ 发散」。三处出现同一个因子不是巧合:SIR 的线性化算子(next-generation matrix)最大特征值正比于 ⟨k²⟩/⟨k⟩,而随机游走的平稳分布是同一个算子的 Perron 向量。
【流程节点链路】随机选一个个体 → 取它的一个随机邻居 → 该邻居的度被 k 加权 → 平均度从 ⟨k⟩ 变成 ⟨k²⟩/⟨k⟩ → 同一个加权出现在随机游走的平稳分布 π_i ∝ k_i → 同一个加权出现在 SIR 线性化算子的最大特征值 → 阈值 λ_c = ⟨k⟩/⟨k²⟩。一个节点都不能省。
【极难发现】第四步,代价。BA 网络(P(k)∝k⁻³,k_min=m)里 ⟨k²⟩ ≈ 2m²·ln(k_max/m),k_max ≈ m√N,所以 ⟨k²⟩/⟨k⟩ ≈ (m/2)·ln N。取 m=3、N=10⁴,比值约 13.8,而 ⟨k⟩=6。也就是说:友谊悖论的强度随网络规模【对数增长】,它不是小样本 artifact,是规模效应。更要命的是阈值那一侧——γ∈(2,3) 时 ⟨k²⟩ 由 k_max ~ N^{1/(γ-1)} 主导,所以任何有限网络上测出的「传染阈值」都是 N 的函数,不是常数。你以为你在测一个网络的属性,其实你在测你的网络有多大。Boguñá, Castellano & Pastor-Satorras (2013, PRL) 把这一点说清楚了:有限尺度下阈值的行为取决于 quenched 还是 annealed 平均,两者给出不同的 N 依赖。
【显式】第五步,把偏差当工具。Cohen, Havlin & ben-Avraham (2003, PRL) 的 acquaintance immunization:不知道度序列、不知道 hub 在哪,随机选一批节点、每个节点随机免疫它的一个邻居——就能以远低于均匀免疫的覆盖率切断传播。原理就是上面那条:随机邻居是 size-biased 的 hub 采样器。偏差不是 bug,是免费的 hub 定位器。
【可证伪】一个今天就能做的检验:同一份社交图,用三种测度测「平均度」——(a) 均匀抽节点,(b) 随机抽边的端点,(c) 随机游走。预测:(a) 给 ⟨k⟩,(b) 与 (c) 给 ⟨k²⟩/⟨k⟩,且 (b)≈(c)。如果 (b) 与 (c) 显著不一致,那你的游走不是均匀的(有向、非回溯、度相关、或图不连通)——这是一个能立刻定位 bug 的诊断,而不是一个需要解释的发现。
【辩论】如果 ⟨k²⟩/⟨k⟩ 是测度的属性而不是网络的属性,那么「这个网络的平均度是多少」这个问题是不是病态的?我的答案是:是,除非你先声明测度。所有不声明测度的网络统计量,都只是一个未标注采样分布的样本均值。你同意吗——还是说存在某个「自然」测度,使得 ⟨k⟩ 才是那个正确的问题?







0 評論