数学推导与算法 · 生物医学网络科学

握手定理：度之和等于两倍边数

无向简单图中， $k_i=\sum_j A_{ij}$ ，于是 $\sum_i k_i=\sum_{i}\sum_{j}A_{ij}=\sum_{(i,j):\,A_{ij}=1}1 .$ 每条无向边 $\{i,j\}$ 在矩阵中出现两次（ $A_{ij}=A_{ji}=1$ ），所以右端恰为 $2M$ 。一个直接推论是：奇数度节点的个数必为偶数（偶数个奇数相加才能得到偶数 $2M$ ）。有向图中每条边 $i\to j$ 只出现一次，相应地 $\sum_i k_i^{\text{out}}=\sum_i k_i^{\text{in}}=M$ 。用关联矩阵也可以一行证明： $B$ 的每一列恰有两个 1，所以 $B$ 全部元素之和既等于 $2M$ （按列加），也等于 $\sum_i k_i$ （按行加）。

Euler 判据

一条“每条边恰好经过一次”的路线称为欧拉路径（Eulerian path）；起点与终点相同时称为欧拉回路。沿路线行走时，除起点和终点外，每经过一个节点都是“进一次、出一次”，消耗该节点的两条边，因此中间节点的度必须为偶数；只有起点和终点可以是奇数度。于是连通（多重）图存在欧拉路径的必要条件是：奇数度节点数为 0（此时存在欧拉回路）或 2。可以证明，这一条件对连通图也是充分的。七桥图 4 个节点的度为 5、3、3、3，奇数度节点有 4 个，因此不存在欧拉路径；若再加一座连接两个奇数度陆地的桥，奇数度节点数降为 2，欧拉路径即存在（见代码示例）。

充分性（Hierholzer 的构造）。设连通图所有节点度为偶数。从任一节点出发沿未用过的边随意行走：每进入一个节点就消耗它的一条边，由于度为偶数，除非回到起点，总有未用的边可以离开，所以行走必然在起点结束，得到一个回路 $C$ 。若 $C$ 未用完所有边，由连通性， $C$ 上必有某个节点 $v$ 还连着未用的边；从 $v$ 出发重复同样的过程得到另一个回路，并把它在 $v$ 处“拼接”进 $C$ 。剩余边构成的子图中每个节点度仍为偶数，因此可以一直重复，直到所有边用完。若恰有两个奇数度节点 $u,w$ ，临时加一条边 $u$ – $w$ 后得到欧拉回路，再删去这条边即得欧拉路径。

算法 2  Hierholzer 算法（欧拉回路）
输入：所有节点度为偶数的连通图 G；输出：欧拉回路（节点序列）
1. stack ← [任一有边的节点]；circuit ← []
2. while stack 非空:
3.     v ← stack 顶部
4.     if v 还有未用的边 (v, u):
5.         标记该边已用；把 u 压入 stack
6.     else:
7.         弹出 v，追加到 circuit
8. return circuit 的逆序

每条边只被标记一次，每个节点进出栈的次数与其度成正比，复杂度为 $O(N+M)$ 。NetworkX 中对应 nx.eulerian_circuit 与 nx.eulerian_path。

游走计数： $A^r$ 的组合意义

对 $r$ 归纳。 $r=1$ 时 $A_{ij}$ 是长度 1 的游走数。设结论对 $r$ 成立，则 $(A^{r+1})_{ij}=\sum_{l}(A^{r})_{il}A_{lj}:$ 每条从 $i$ 到 $j$ 、长度 $r+1$ 的游走都唯一地分解为“从 $i$ 到某个 $l$ 的长度 $r$ 游走”加上“边 $l\to j$ ”，对所有可能的倒数第二个节点 $l$ 求和即得。三角形 $i$ – $j$ – $l$ – $i$ 作为闭游走会被每个顶点作为起点计一次、每个方向计一次，共计 $3\times2=6$ 次，所以三角形数为 $\operatorname{tr}(A^3)/6$ 。

拉普拉斯矩阵的性质

(1) $L=\nabla\nabla^\top$ 。 $(\nabla\nabla^\top)_{ij}=\sum_e\nabla_{ie}\nabla_{je}$ 。 $i=j$ 时每条与 $i$ 相关的边贡献 $(\pm1)^2=1$ ，合计 $k_i$ ； $i\ne j$ 时只有连接 $i,j$ 的那条边贡献 $(+1)(-1)=-1$ 。这与边方向的选取无关。同理，无定向关联矩阵满足 $BB^\top=D+A$ 。

(2) 二次型。由 (1)， $\mathbf x^\top L\mathbf x=\big\|\nabla^\top\mathbf x\big\|^2=\sum_{e=(u\to v)}(x_u-x_v)^2\ \ge 0 .$ 因此 $L$ 半正定，特征值非负。

(3) 零特征值的重数等于连通分支数。若 $L\mathbf x=0$ ，则 $\mathbf x^\top L\mathbf x=0$ ，即每条边两端 $x_u=x_v$ ，于是 $\mathbf x$ 在每个连通分支内是常数。反之，每个分支的指示向量都满足 $L\mathbf x=0$ 。所以零空间恰由 $c$ 个分支的指示向量张成，维数为 $c$ 。

(4) 迹。 $\sum_i\mu_i=\operatorname{tr}L=\sum_i k_i=2M$ 。

从边列表构造邻接矩阵

算法 1  边列表 → 邻接矩阵（无向图）
输入：节点列表 V（固定顺序），边列表 E；输出：N×N 矩阵 A
1. idx ← 节点到行号的映射；A ← N×N 零矩阵
2. for (u, v) in E:
3.     A[idx[u], idx[v]] ← 1；A[idx[v], idx[u]] ← 1     # 有向图只写前一项
4. return A

稠密邻接矩阵需要 $O(N^2)$ 存储，边列表或稀疏矩阵只需要 $O(M)$ 。对 $M \ll N^2$ 的稀疏网络，计算度（行和）的代价也从 $O(N^2)$ 降到 $O(M)$ 。

从边列表构造 CSR 稀疏矩阵

算法 3  边列表 → CSR（有向图；无向图把每条边按两个方向各写一次）
输入：已编号的边 (u_e, v_e)，e = 1..M；输出：indptr（长 N+1）、indices（长 M）
1. count[i] ← 以 i 为起点的边数（一次遍历边列表）
2. indptr[0] ← 0；indptr[i+1] ← indptr[i] + count[i]        # 前缀和
3. pos ← indptr 的副本
4. for e = 1..M:  indices[pos[u_e]] ← v_e；pos[u_e] ← pos[u_e] + 1
5. return indptr, indices

两次遍历，时间与空间都是 $O(N+M)$ 。节点 $i$ 的度就是 indptr[i+1] - indptr[i]，无需再扫描。

二分图的加权投影

设药物–靶点二分图的关联矩阵为 $B$ （ $B_{dt}=1$ 表示药物 $d$ 作用于靶点 $t$ ）。则 $P = B B^\top,\qquad P_{dd'}=\sum_t B_{dt}B_{d't}$ 的非对角元正是药物 $d$ 与 $d'$ 共享的靶点数，可作为投影后药物–药物网络的边权；对角元 $P_{dd}$ 是药物 $d$ 的靶点数。投影到靶点一侧则取 $B^\top B$ 。投影会丢失信息：不同的二分图可能投影出同一张单模网络。

投影网络的边数可以远大于二分网络：一个连接 $k_t$ 个药物的靶点会在药物投影中贡献 $k_t(k_t-1)/2$ 对共享关系，所以投影的总“共享对”数为 $\sum_t k_t(k_t-1)/2$ ，由靶点度的二阶矩主导。少数被大量药物作用的靶点（高 $k_t$ ）会让投影网络变得很稠密。