度分布

度分布刻画了“连接是如何在节点之间分配的”。两类典型形状：

• 均匀型：大多数节点的度集中在平均值附近，分布有一个峰，远离峰值的概率迅速衰减。规则网格（所有节点度相同）和 ER 随机网络（泊松分布）属于这一类。
• 重尾型（heavy-tailed）：大多数节点度很小，但存在少数度极大的节点（枢纽，hub），分布的“尾巴”拖得很长。社交网络、万维网、许多生物分子网络属于这一类。

矩与异质性

度分布的 $n$ 阶矩 $\langle k^n\rangle=\sum_k k^nP(k)$ 在后续理论中反复出现：一阶矩是平均度；二阶矩 $\langle k^2\rangle$ 决定“沿一条边走到的邻居平均有多少个其他邻居”，即剩余度（excess degree）均值 $\langle k^2\rangle/\langle k\rangle-1$，它控制巨连通分支的出现、传播阈值和平均距离。常用异质性指数 $\kappa=\langle k^2\rangle/\langle k\rangle$ 或变异系数 $\sigma_k/\langle k\rangle$ 概括度分布的宽窄：泊松分布 $\sigma_k/\langle k\rangle=1/\sqrt{\langle k\rangle}$，平均度越大越“均匀”；重尾分布的 $\langle k^2\rangle$ 随网络规模增大而增大（见无标度网络）。

判断重尾的实用做法

1. 看最大度与平均度之比。均匀型网络中二者相差几倍；重尾型网络可达几十到上百倍。对 ER 网络可以算出“期望最大度”（自然截断，见ER 随机网络），它只比平均度高出若干个标准差；
2. 在双对数坐标下画分布。重尾分布在双对数图上衰减缓慢，接近一条下倾的直线；均匀型分布则会急剧“掉崖”；
3. 画互补累积分布（CCDF）$P(K \ge k)$，它比直方图更平滑，尾部不需要分箱（详见幂律判断）。