度、平均度与密度

由“每条边贡献两个度”（握手定理 $\sum_i k_i = 2M$）可得平均度：

$$\langle k \rangle = \frac{1}{N}\sum_i k_i = \frac{2M}{N}.$$

有向网络中每条边贡献一个入度和一个出度，故 $\langle k^{\text{in}}\rangle=\langle k^{\text{out}}\rangle=M/N$。

密度（density）是实际边数与最大可能边数之比：

$$\rho = \frac{M}{N(N-1)/2} = \frac{\langle k \rangle}{N-1}.$$

有向简单图最多有 $N(N-1)$ 条边，密度为 $M/[N(N-1)]$。

真实网络几乎都很稀疏（$\langle k \rangle \ll N$）。比如 Zachary 空手道俱乐部网络 $N=34$、$M=78$，$\langle k \rangle \approx 4.6$，$\rho \approx 0.14$；而一个 2 万节点、平均度 20 的蛋白质网络，密度只有 0.001。稀疏性决定了计算策略：用边列表或稀疏矩阵存储，算法复杂度以 $N+M$ 而非 $N^2$ 衡量。