别把『平均度』当『连通性』:Erdős–Rényi 随机图的相变为什么让 1.0 与 1.1 天差地别
【锚点】这一讲只钉一个判断:【平均度】不是【连通性】的充分描述;在随机图里,真正决定巨分量是否出现的是【超临界条件】,而它由【度分布的二阶矩】控制。
【显式】在 Erdős–Rényi 图 G(n,p) 中,平均度 =p(n-1)。当 n=10000 时,p=1.0e-5 给 ≈1.0;p=1.1e-5 给 ≈1.1;p=2.0e-5 给 ≈2.0。
【流程节点链路】:【≤1】→【Poisson 度分布】→【分支过程灭绝】→【无巨分量】;【>1】→【超临界】→【巨分量出现】→【网络可达性突变】。
【隐式】很多人把 当成“平均每个节点连几条边”,然后线性外推。但在临界点附近,网络不是“稍微更连通”,而是从“几乎所有分量都小”跳到“存在包含常数比例节点的巨分量”。
【细微】对 Poisson 度分布,Molloy–Reed 判据 E[K2] > 2E[K] 简化为 > 1。因为 Poisson 的 E[K2]=+2。若 =1.1,巨分量比例 S 满足 S=1-exp(-1.1S),解约 S≈0.18;若 =2.0,S≈0.80。也就是说,平均度从 1.1 到 2.0,不是“多连一点”,而是巨分量从约 18% 跳到约 80%。
【极难发现】平均度相同的两个网络,只要 2> 不同,连通性可以完全不同。报告 而不报告度分布尾部或 ,等于隐藏了连通性的主要信息。行为上,这像把“平均收入”当“中位收入”:尾部被少数高连接节点抬高,读者却以为整体均匀。
【可证伪检验】生成 10000 个 n=10000 的 G(n,p):p=1.0e-5 的最大分量应接近零;p=1.1e-5 的最大分量应集中在约 18%;p=2.0e-5 应集中在约 80%。若最大分量显著偏离,说明实现或有限尺寸效应需要检查。
【结尾辩论】如果你的系统 =1.05,你会把它解释成“接近可用”,还是“处于危险临界点”?在哪些场景下,1.05 应该触发扩容/冗余,而不是继续观察?







0 Comments