生物医学网络科学Biomedical Network Science
小世界与无标度网络模型04 / 17

幂律度分布与无标度网络

阅读
约 3 分钟

观察：长尾分布

1999 年前后，研究者在万维网、互联网路由器、论文引用和演员合作网络中都发现：度分布在双对数坐标下近似为一条直线，

P(k)∼k−γ,P(k) \sim k^{-\gamma},

其中 γ\gamma 称为度指数，常见值在 2 到 3 之间（例如万维网入度约 2.1，演员网络约 2.3）。这与 ER 网络的泊松分布截然不同：泊松分布在平均度附近有一个峰，远离平均值的概率按阶乘速度衰减，几乎不可能出现度为平均值 10 倍的节点；幂律分布则以多项式速度缓慢衰减，大量低度节点与少数极高度的枢纽节点共存。

无标度网络（scale-free network）：度分布（至少在尾部）服从幂律 P(k)∼k−γP(k) \sim k^{-\gamma} 的网络。“无标度”指幂律函数的尺度不变性：P(ak)=a−γP(k)P(ak) = a^{-\gamma}P(k)，把 kk 放大任意倍数，分布的形状不变，因此不存在一个“典型”的度。

离散形式与连续形式

度是整数，严格写法是离散幂律 pk=k−γζ(γ,kmin),ζ(γ,kmin)=∑k=kmin∞k−γ,p_k = \frac{k^{-\gamma}}{\zeta(\gamma, k_{\min})},\qquad \zeta(\gamma,k_{\min})=\sum_{k=k_{\min}}^{\infty}k^{-\gamma}, 分母是 Hurwitz zeta 函数，保证归一化。推导时常用连续近似 p(k)=(γ−1)kmin⁡γ−1k−γ,k≥kmin,p(k) = (\gamma-1)\,k_{\min}^{\gamma-1}\,k^{-\gamma},\qquad k\ge k_{\min}, 它让矩、截断、最大似然估计都有简单闭式。两者在大 kk 处一致，在小 kk 处有可见差别；拟合真实数据时应使用离散形式或带修正的近似（见小世界与无标度的统计判别）。纯幂律在 k=0k=0 处发散，所以总要配一个下界 kmink_{\min}；许多真实网络只在尾部（k≥kmink\ge k_{\min}）近似幂律，小度区另有形状。

为什么说“没有典型尺度”

对幂律分布计算矩：⟨kn⟩=∫kminkmaxknP(k)dk\langle k^n \rangle = \int_{k_{\min}}^{k_{\max}} k^n P(k)\,dk。当 kmax→∞k_{\max} \to \infty 时，若 n>γ−1n > \gamma - 1 则该积分发散。对 2<γ<32 < \gamma < 3：

  • 一阶矩（平均度）有限；
  • 二阶矩 ⟨k2⟩\langle k^2 \rangle 随网络规模增大而发散，即方差没有上界。

所以说一个节点的度是“平均度 ± 标准差”是没有意义的：随机抽一个节点，它的度可能是 2，也可能是 2000。这一点影响深远：流行病阈值正比于 ⟨k⟩/⟨k2⟩\langle k \rangle / \langle k^2 \rangle，无标度网络中阈值趋于 0（见网络上的传播与免疫）；无标度网络对随机删点很稳健，对攻击枢纽却很脆弱（见网络鲁棒性、渗流与级联失效）。

有限网络的自然截断

真实网络的节点数有限，最大度也有限。对度指数为 γ\gamma 的网络，最大度大约按 kmax∼kminN1/(γ−1)k_{\max} \sim k_{\min} N^{1/(\gamma-1)} 增长（推导见数学推导与算法）。γ=3\gamma = 3 时 kmax∼N1/2k_{\max} \sim N^{1/2}：一万个节点的网络，枢纽的度约为最小度的 100 倍。作为对比，同样规模的 ER 网络最大度只比平均度高出几倍。

度指数决定的三个区间

度指数 γ\gamma 不只是一个拟合参数，它把网络分成性质截然不同的区间：

区间 矩与枢纽 平均距离 ⟨d⟩\langle d\rangle 说明
γ<2\gamma<2（反常区） 平均度也发散；kmax∼N1/(γ−1)k_{\max}\sim N^{1/(\gamma-1)} 比 NN 增长更快 γ=2\gamma=2 时为常数 最大枢纽的度会超过节点总数，在不允许重边的简单图中无法维持，大型网络中罕见
2<γ<32<\gamma<3（无标度区） ⟨k⟩\langle k\rangle 有限，⟨k2⟩\langle k^2\rangle 发散 ∼ln⁡ln⁡Nln⁡(γ−1)\sim \dfrac{\ln\ln N}{\ln(\gamma-1)}（超小世界） 枢纽主导结构与动力学；流行病阈值趋零
γ=3\gamma=3（临界点） ⟨k2⟩\langle k^2\rangle 对数发散 ∼ln⁡Nln⁡ln⁡N\sim \dfrac{\ln N}{\ln\ln N} BA 模型恰好落在这里
γ>3\gamma>3（类随机区） ⟨k⟩\langle k\rangle、⟨k2⟩\langle k^2\rangle 都有限 ∼ln⁡N\sim \ln N 行为接近随机网络；枢纽不大

（距离标度见 Cohen 与 Havlin 2003；区间划分沿用 Barabási《Network Science》第 4 章。）

γ>3\gamma>3 时还有一个实际问题：kmax/kmin∼N1/(γ−1)k_{\max}/k_{\min}\sim N^{1/(\gamma-1)}，例如 γ=5\gamma=5 时要让度跨越两个数量级（kmax/kmin=100k_{\max}/k_{\min}=100）就需要约 N=108N=10^8 个节点。普通规模的网络根本无法在这么窄的度范围内把幂律与其他分布区分开——这也是为什么“γ\gamma 很大的幂律”在经验上几乎无从检验。

普适性及其边界

Barabási 等早期研究强调无标度结构在万维网、互联网、引文、代谢、蛋白质相互作用等系统中反复出现，认为背后有共同的生长机制。但同样有大量网络不是无标度的：电网、道路网等受物理容量或空间限制的网络，节点度有硬性上限；晶格状的材料网络度几乎相同；许多社会接触网络的度分布更接近对数正态或带截断的分布。后来的系统检验（Broido 与 Clauset 2019）进一步表明严格的幂律并不普遍（见小世界与无标度的统计判别）。更稳妥的表述是：度分布的重尾与枢纽普遍存在，其确切形状因系统而异。

继续阅读