数学推导与算法

平均度与密度

由握手定理 $\sum_i k_i = 2M$ 立即得到 $\langle k\rangle = 2M/N$。无向简单图最多有 $N(N-1)/2$ 条边，故 $\rho = 2M/[N(N-1)] = \langle k\rangle/(N-1)$。

ER 网络度分布的泊松极限

节点 $i$ 的度是 $N-1$ 次独立伯努利试验（成功概率 $p$）的成功次数，故 $P(k)=\binom{N-1}{k}p^k(1-p)^{N-1-k}$。令 $\lambda=\langle k\rangle=p(N-1)$ 固定、$N\to\infty$，对固定的 $k$： $$\binom{N-1}{k}p^k=\frac{(N-1)(N-2)\cdots(N-k)}{k!}\cdot\frac{\lambda^k}{(N-1)^k}\to\frac{\lambda^k}{k!},$$ $$\ln(1-p)^{N-1-k}=(N-1-k)\ln\!\left(1-\frac{\lambda}{N-1}\right)\to-\lambda ,$$ 其中用到 $\ln(1+x)\approx x$（$|x|\ll1$）。合起来得到泊松分布 $P(k)=e^{-\lambda}\lambda^k/k!$，其均值与方差都等于 $\lambda$。这一近似要求 $k\ll N$，对稀疏网络总是成立。

最大度与最小度

令 $k_{\max}$ 满足 $N\sum_{k\ge k_{\max}}P(k)\approx1$。泊松分布在 $k>\lambda$ 时随 $k$ 快速下降，和式由首项主导：$N e^{-\lambda}\lambda^{k_{\max}}/k_{\max}!\approx1$，可用对数与 Stirling 公式数值求解。同理 $N\sum_{k\le k_{\min}}P(k)\approx1$ 给出 $k_{\min}$。由于泊松分布在均值附近近似正态，$k_{\max}-\langle k\rangle$ 与 $\sqrt{\langle k\rangle\ln N}$ 同阶，相对偏离 $(k_{\max}-\langle k\rangle)/\langle k\rangle$ 随 $\langle k\rangle$ 增大而减小。

ER 网络的聚集系数

节点 $i$ 有 $k_i$ 个邻居，邻居对共 $k_i(k_i-1)/2$ 个。在 $G(N,p)$ 中，每一对邻居之间是否有边与 $i$ 的连边独立，概率均为 $p$，于是 $\mathbb E[e_i \mid k_i]=p\,k_i(k_i-1)/2$，$\mathbb E[C_i]=p$。

ER 网络的平均路径长度

见小世界性与平均距离：由 $\langle k\rangle^{d}\approx N$ 得 $L_{\text{rand}}\approx\ln N/\ln\langle k\rangle$；有限规模修正为 $(\ln N-\gamma_E)/\ln\langle k\rangle+1/2$（Fronczak 等 2004）。

巨连通分支的自洽方程

写法一（Barabási 书进阶专题 3.C）。记 $u=1-S$ 为不在巨分支中的节点比例。节点 $i$ 经由某个特定节点 $j$ 连到巨分支失败，有两种情况：$i$、$j$ 无边（概率 $1-p$），或有边但 $j$ 不在巨分支中（概率 $pu$）。$i$ 不在巨分支中，当且仅当经由其余 $N-1$ 个节点都失败： $$u=(1-p+pu)^{N-1}.$$ 取对数并用 $p=\langle k\rangle/(N-1)$、$\ln(1+x)\approx x$：$\ln u\approx-(N-1)p(1-u)=-\langle k\rangle(1-u)$，即 $u=e^{-\langle k\rangle(1-u)}$，也就是 $$S=1-e^{-\langle k\rangle S}.$$

写法二（生成函数）。记 $u$ 为“沿一条边到达的节点不通向巨分支”的概率。节点不在巨分支中，当且仅当它的所有邻居都不把它连到巨分支：$1-S=\sum_k P(k)\,u^k=G_0(u)$。对泊松分布，沿边到达的邻居剩余度仍服从均值 $\langle k\rangle$ 的泊松分布，$u$ 满足同样的方程，于是 $\sum_k e^{-\langle k\rangle}\frac{\langle k\rangle^k}{k!}u^k=e^{-\langle k\rangle(1-u)}$，结果相同。这种写法可直接推广到任意度分布（配置模型）。

临界点。$S=0$ 总是一个解。非零解存在的条件是右端函数在 $S=0$ 处的斜率大于 1：$\frac{d}{dS}\big(1-e^{-\langle k\rangle S}\big)\big|_{S=0}=\langle k\rangle>1$。临界点附近展开 $1-e^{-cS}\approx cS-c^2S^2/2$，代入得 $S\approx2(c-1)/c^2\approx2(c-1)$。数值上可用不动点迭代 $S \leftarrow 1-e^{-\langle k\rangle S}$ 求解（见代码示例）。

分支大小分布

亚临界与临界状态下，从一个节点出发的探索近似为后代数服从泊松($\langle k\rangle$)的 Galton–Watson 分支过程。用 Lagrange 反演（或 Borel 分布）可得总后代数为 $s$ 的概率 $p_s=e^{-\langle k\rangle s}(\langle k\rangle s)^{s-1}/s!$。代入 Stirling 公式 $s!\approx\sqrt{2\pi s}\,(s/e)^s$： $$p_s\approx\frac{1}{\sqrt{2\pi}}\,s^{-3/2}\exp\!\big[-(\langle k\rangle-1)s+(s-1)\ln\langle k\rangle\big].$$ $\langle k\rangle=1$ 时指数部分为 $e^0$，$p_s\approx s^{-3/2}/\sqrt{2\pi}$。代码示例在 $N=2\times10^5$ 的临界网络上验证：$p_1$、$p_2$、$p_3$ 的模拟值 0.368、0.137、0.074 与理论值 0.368、0.135、0.075 吻合。

完全连通区的阈值

在 $\langle k\rangle$ 较大时，巨分支已包含几乎所有节点，网络是否连通取决于是否还有孤立节点。一个节点孤立的概率 $(1-p)^{N-1}\approx e^{-pN}$，孤立节点的期望数 $I_N\approx Ne^{-pN}$。令 $I_N=1$ 得 $p=\ln N/N$，即 $\langle k\rangle\approx\ln N$。

广度优先搜索的伪代码与复杂度

算法 1  BFS 求单源距离（无权图）
输入：图 G，源点 s；输出：dist（s 到各可达节点的距离）
1. dist ← {s: 0}；队列 Q ← [s]
2. while Q 非空:
3.     v ← Q.popleft()
4.     for u in 邻居(v):
5.         if u 不在 dist 中:
6.             dist[u] ← dist[v] + 1；Q.append(u)
7. return dist

每个节点入队、出队各一次，每条边在两端各被检查一次，总代价 $O(N+M)$。对全部节点各做一次得到所有点对距离，代价 $O(N(N+M))$。加权网络中改用以优先队列实现的 Dijkstra 算法，单源代价 $O(M+N\log N)$，要求边上的“长度”非负，因此相关系数等“强度型”权重需先转换为长度（如 $1/w$ 或 $-\log w$）。

Brandes 介数算法

关键观察：定义源点 $s$ 对节点 $v$ 的依赖度 $\delta_s(v)=\sum_{t}\sigma_{st}(v)/\sigma_{st}$，则 $C_B(v)=\sum_{s\ne v}\delta_s(v)$，且依赖度满足递推 $$\delta_s(v)=\sum_{w:\,v\in\text{pred}_s(w)}\frac{\sigma_{sv}}{\sigma_{sw}}\big(1+\delta_s(w)\big),$$ 其中 $\text{pred}_s(w)$ 是 $s$ 到 $w$ 的最短路径上 $w$ 的前驱节点。

算法 2  Brandes 介数（无权图）
对每个源点 s：
1. BFS：dist[s]=0，σ[s]=1；访问 v 的邻居 w 时，
   若 w 首次被发现则 dist[w]=dist[v]+1 并入队；
   若 dist[w]=dist[v]+1，则 σ[w] += σ[v]，把 v 加入 pred[w]。
   把出队顺序记入栈 S。
2. 回溯：δ ≡ 0；当 S 非空，弹出 w，
   对每个 v ∈ pred[w]：δ[v] += σ[v]/σ[w]·(1+δ[w])；
   若 w ≠ s：C_B[w] += δ[w]。
无向图最后把 C_B 除以 2。

每个源点的两个阶段都是 $O(N+M)$，总代价 $O(NM)$（稀疏图），远优于朴素方法的 $O(N^3)$。代码示例中的手写实现与 NetworkX 结果之差在 $10^{-14}$ 量级。

谱类中心性的幂迭代与收敛条件

• 特征向量：$\mathbf x^{(t+1)}=A\mathbf x^{(t)}/\|A\mathbf x^{(t)}\|$。把初值按特征向量展开 $\mathbf x^{(0)}=\sum_i c_i\mathbf v_i$，则 $A^t\mathbf x^{(0)}=\sum_ic_i\lambda_i^t\mathbf v_i$，归一化后其他分量以 $|\lambda_i/\lambda_1|^t$ 衰减。二部图中 $-\lambda_1$ 也是特征值，简单幂迭代会振荡，可改用 $A+I$。
• Katz：$(I-\alpha A^{\top})\mathbf x=\beta\mathbf 1$。Neumann 级数 $\sum_t(\alpha A^{\top})^t$ 收敛当且仅当 $\alpha\lambda_1<1$。
• PageRank：$\mathbf x=dP\mathbf x+\frac{1-d}{N}\mathbf 1$，$P=A^{\top}D_{\text{out}}^{-1}$ 为列随机矩阵。迭代映射是压缩映射，误差每步至少乘以 $d$，收敛到 $10^{-6}$ 只需约 $\log(10^{-6})/\log0.85\approx85$ 步，与网络规模无关。
• HITS：交替执行 $\mathbf a\leftarrow A^{\top}\mathbf h$、$\mathbf h\leftarrow A\mathbf a$ 并归一化，等价于对 $A^{\top}A$ 与 $AA^{\top}$ 做幂迭代。若主特征值不唯一（网络由多个互不相连的部分组成），结果依赖初值。

每次迭代只需一次稀疏矩阵–向量乘法，代价 $O(M)$。

k 核分解

算法 3  核数（Batagelj–Zaversnik 思想）
1. 计算所有节点的度，按度放入桶中；k ← 0
2. 重复直到所有节点被删除：
3.     取当前度最小的节点 v；k ← max(k, deg(v))；core[v] ← k
4.     删除 v，把每个未删除邻居的度减 1 并移到相应桶中

每个节点删除一次，每条边导致一次度减少，用桶结构维护最小度，总代价 $O(N+M)$。“$k\leftarrow\max(k,\deg v)$”保证核数单调不减：当剩余图的最小度为 $k$ 时，剩余图本身就是 k 核。