Matrix as Graph：连接、流量与状态转移

一张图可以对应不同的矩阵

交通图关心车流是否守恒，网页图关心一次跳转能到哪里。两者都有节点和有向边，却不能不加区分地使用同一种矩阵。

本章先建立图与矩阵之间的对应，再用交通流和网页跳转说明：换一个问题，同一张网络就可能需要另一种矩阵表示[1][1] X. Yang, “ENG1005 Week 2: Traffic Flow, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W2.tex, [2][2] X. Yang, “ENG1005 Week 4: Webpage Transitions, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W4.tex。需要先熟悉矩阵乘法和线性系统。

在写矩阵之前固定图的含义

有限有向图由节点集合 $V$ 和边集合 $E$ 构成。一条边 $u\to v$ 有出发点与到达点，方向不能省略。本章的邻接例子不允许同一有序节点对之间出现平行边，但允许根据场景保留自环。若允许平行边，矩阵元素需要记录边数或边权总和，不能继续只写 $0$ 或 $1$。

一条游走依次经过相接的边，可以重复节点和边；简单路径不重复节点。长度表示经过的边数。长度为零的游走停在原节点，这与矩阵零次幂 $A^0=I$ 一致。

无向边没有指定方向，表示成邻接矩阵时，对应两个对称位置。无向无自环图的邻接矩阵因此对称且对角线为零。相反，有向图即使两个方向都存在边，也不代表两个方向的权重相等。

权重的含义由问题决定：可以是道路流量、连接强度、距离或转移概率。同一套乘法不会自动理解单位。路径距离通常应沿途相加并在候选路径中取最小值，不能把普通矩阵乘法对边权的乘积误称为最短路长度。

邻接矩阵记录一步连接

固定节点顺序，并约定列表示出发节点，行表示到达节点。对于无权有向图，定义

$$A_{ij}=\begin{cases} 1,&\text{存在边 }j\to i,\\ 0,&\text{否则}. \end{cases}$$

这个约定适合让状态列向量左乘矩阵：第 $j$ 列告诉我们从节点 $j$ 出发的一步去向。有些教材使用相反约定，计算前需要先确认。

例如，节点依次为 $A,B,C$，边为 $A\to B,A\to C,B\to C$，则

$$A=\begin{pmatrix}0&0&0\\1&0&0\\1&1&0\end{pmatrix},\qquad A^2=\begin{pmatrix}0&0&0\\0&0&0\\1&0&0\end{pmatrix}.$$

第二个矩阵说明：从 $A$ 到 $C$ 有一条长度为二的游走，经由 $B$。

命题矩阵幂计算游走数量

在上述约定下，$(A^k)_{ij}$ 是从节点 $j$ 到节点 $i$、长度恰为 $k$ 的游走数量。游走允许重复节点和边；它不一定是简单路径。

证明

$k=1$ 正是邻接矩阵的定义。若结论对 $k$ 成立，则

$$(A^{k+1})_{ij}=\sum_\ell A_{i\ell}(A^k)_{\ell j}.$$

每个长度为 $k+1$ 的游走都有唯一的倒数第二个节点 $\ell$。先从 $j$ 走 $k$ 步到 $\ell$，再沿一条边到 $i$；对所有 $\ell$ 求和，既不遗漏也不重复计数。

对带权邻接矩阵，矩阵幂相应地累加每条游走上边权的乘积，不再只是条数。

度数、权重与概率不能混用

在“列出发、行到达”的约定下，无权邻接矩阵第 $j$ 列之和是节点 $j$ 的出度，第 $i$ 行之和是节点 $i$ 的入度。一个自环对入度与出度各贡献一次。

对于带权图，同样的求和给出总出边权与总入边权，常称为强度，而不一定是边的数量。一个节点有两条边、权重分别为 $100$ 与 $200$，出度是 $2$，总出边权是 $300$。

若权重是概率，每个出发节点的出边权总和必须为一。若权重是当前车流，各列一般既不归一化，也不需要相等。因此，看到一个非负矩阵并不能立刻把它当作转移矩阵。

转置、重新编号和图同构

保持同一个方向约定时，$A^{\mathsf T}$ 反转每一条有向边。反转后的图不一定与原图同构。

一个小反例是两条边 $A\to B,A\to C$。原图有一个出度为二的节点，反向图没有，所以无法只靠重命名节点得到反向图。

重编号则使用置换矩阵。若旧坐标 $\mathbf x$ 在新顺序下记作 $\mathbf x'=P\mathbf x$，那么

$$A'=PAP^{-1}=PAP^{\mathsf T}.$$

这是因为 $P(A\mathbf x)=A'\mathbf x'$。重编号必须对行列作配套置换，保留同一条边的两个端点关系。另一种情况是，同一张图从“行表示出发”改用“列表示出发”：这也会转置存储的数组，但图没有变，因为解释规则同时改变了。不能把这三件事混在一起。

一个重编号的具体例子

把前面三节点图的顺序由 $(A,B,C)$ 改为 $(B,A,C)$，置换矩阵为

$$P=\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}.$$

原来的边 $A\to B$ 在新顺序中是第二个节点到第一个节点；其他边也同步重标。得到

$$PAP^{\mathsf T}=\begin{pmatrix}0&1&0\\0&0&0\\1&1&0\end{pmatrix}.$$

图上的连接没有改变，只有节点在数组中的位置变了。若只交换行，就只改变到达节点的标签，而没有对出发节点做相同调整，通常会得到另一张图。

关联矩阵记录每条边的收支

回到四路口交通图。按节点 $A,B,C,D$ 排列各行，按道路 $x_1,\ldots,x_5$ 排列各列。每条有向边在出发节点记 $-1$，到达节点记 $+1$，其余节点记 $0$，得到关联矩阵

$$B=\begin{pmatrix} 0&-1&1&0&0\\ 1&1&0&0&-1\\ 0&0&-1&-1&1\\ -1&0&0&1&0 \end{pmatrix}.$$

邻接矩阵的两条轴都是节点；关联矩阵的一条轴是节点，另一条轴是边。乘积 $B\mathbf x$ 给出每个节点的“内部流入减内部流出”。它必须等于外部净流出，因此交通方程为

$$B\mathbf x=\begin{pmatrix}-10\\45\\-45\\10\end{pmatrix}.$$

这与线性系统章的方程相同，只是调整了行顺序和部分行的符号。

每列恰有一个 $+1$ 和一个 $-1$，所以

$$\mathbf1^{\mathsf T}B=0.$$

于是右端分量之和必须为零。一个区域的内部道路不能凭空制造净流入。

为什么四个路口只有三个独立守恒条件

若 $\mathbf z^{\mathsf T}B=0$，则对每条边，终点对应的 $z$ 值等于起点对应的值。如果忽略箭头后的图是连通的，这些等式迫使所有节点的 $z$ 值相同。所以行之间的依赖只有常数倍的求和关系，四行的秩为三。

一般地，具有 $n$ 个节点、$c$ 个连通分量的图，其关联矩阵秩为 $n-c$，因为 $z$ 可以在每个连通分量上独立取一个常数。这里的连通性始终指忽略边方向后的连通性。

零空间中的方向是循环流

交通解的两个自由方向为

$$\mathbf v_1=(1,-1,-1,1,0)^{\mathsf T},\qquad \mathbf v_2=(0,1,1,0,1)^{\mathsf T}.$$

第二个方向沿 $A\to B\to C\to A$ 增加同样流量，每个节点的增加量相互抵消。第一个方向也满足守恒，但有负分量，表示相对于道路箭头减少流量。因此零空间描述的是带符号的循环变化，不能把每个方向都当作可直接实施的非负车流。

本例有五条边、四个节点且连通，循环变化的维数为 $5-(4-1)=2$，正好对应消元得到的两个自由参数。

网页跳转：从边权到转移概率

考虑三个网页之间的随机跳转，其一步转移矩阵为：

$$P=\frac1{10}\begin{pmatrix}2&1&3\\4&5&3\\4&4&4\end{pmatrix}.$$

仍然使用“列出发、行到达”。例如第一列表示：从网页一出发，下次停留在网页一、二、三的概率分别是 $0.2,0.4,0.4$。每列元素非负且和为一。

若 $\mathbf x_n$ 记录第 $n$ 步各网页上的期望人数，则

$$\mathbf x_{n+1}=P\mathbf x_n,\qquad \mathbf x_n=P^n\mathbf x_0.$$

对于随机跳转的有限人群，实际人数会波动；矩阵给出期望值。若把状态归一化为概率分布，同样的公式仍成立。

总量守恒来自列和条件：

$$\mathbf1^{\mathsf T}P=\mathbf1^{\mathsf T} \quad\Longrightarrow\quad \mathbf1^{\mathsf T}\mathbf x_{n+1}=\mathbf1^{\mathsf T}\mathbf x_n.$$

取 $\mathbf x_0=(1000,1000,1000)^{\mathsf T}$，一步后得到 $(600,1200,1200)^{\mathsf T}$，三步后得到 $(600,1200,1200)^{\mathsf T}$。

不变的概率分布满足

$$P\boldsymbol\pi=\boldsymbol\pi,\qquad \mathbf1^{\mathsf T}\boldsymbol\pi=1.$$

本例的解为

$$\boldsymbol\pi=\frac15(1,2,2)^{\mathsf T}.$$

直接相乘即可验证。这是特征值 $1$ 对应的特征向量，但存在稳态并不自动证明任意初始状态都收敛到它。例如两节点每步互换的矩阵具有稳态 $(1/2,1/2)^{\mathsf T}$，从 $(1,0)^{\mathsf T}$ 出发却一直振荡。下面直接利用当前矩阵的结构证明这个模型的收敛。

怎样把非负边权转成概率

若带权邻接矩阵 $W$ 的第 $j$ 列总和为 $s_j>0$，可以按出发节点归一化：

$$P_{ij}=\frac{W_{ij}}{s_j}.$$

这表示“按边权比例选择下一条边”，是一个额外的建模决定。例如，权重表示道路长度时，这种规则会偏向更长的道路，未必符合实际。

若某一列全零，该节点没有给定的去向，不能除以零。必须先决定模型怎样处理它，例如留在原节点，或按某个指定分布重新出发。采用哪条规则，会改变最终转移矩阵。

为什么期望人数按矩阵相乘

假设当前网页 $j$ 有 $x_j$ 人，每人下一步到网页 $i$ 的概率是 $P_{ij}$，那么来自网页 $j$ 的期望贡献为 $P_{ij}x_j$。对所有出发网页相加，便得到

$$\mathbb E[X_{n+1,i}\mid\mathbf X_n=\mathbf x] =\sum_jP_{ij}x_j.$$

这里首先是在给定当前人数时计算条件期望。若当前人数也随机，且使用同一个固定转移规则，再取期望即可得到 $\mathbb E[\mathbf X_{n+1}]=P\mathbb E[\mathbf X_n]$。期望的可加性不要求不同人的跳转互相独立；独立性会影响波动和方差，但不是这条期望公式的必要条件。

在这个例子里直接证明收敛

设总人数为 $N$，第 $n$ 步三个网页的期望人数分别为 $g_n,h_n,m_n$。矩阵第三行给出

$$m_{n+1}=0.4(g_n+h_n+m_n)=0.4N.$$

因此从第一步起，第三个分量已经固定。将 $h_n=N-g_n-m_n$ 代入第一行，对 $n\ge1$ 得

$$\begin{aligned} g_{n+1}&=0.2g_n+0.1h_n+0.3m_n\\ &=0.1g_n+0.1N+0.2m_n\\ &=0.1g_n+0.18N. \end{aligned}$$

固定值应满足 $g_*=0.1g_*+0.18N$，所以 $g_*=0.2N$。更关键的是，减去这个固定值后有

$$g_{n+1}-0.2N=0.1(g_n-0.2N).$$

对 $n\ge1$，归纳得到

$$g_n-0.2N=0.1^{n-1}(g_1-0.2N).$$

右侧趋于零，剩余分量由总量守恒确定，因此任意初始人数分布都收敛到 $N(0.2,0.4,0.4)^{\mathsf T}$。

例如初始状态为 $(0,3000,0)^{\mathsf T}$，前两步依次为 $(300,1500,1200)^{\mathsf T}$ 与 $(570,1230,1200)^{\mathsf T}$；第一分量相对稳态 $600$ 的偏差从 $-300$ 缩小到 $-30$。而从三个网页各 $1000$ 人出发，第一步就恰好落到稳态，这是初始状态的特殊性，不代表所有模型都一步收敛。

这份证明利用了当前矩阵第三行的特殊结构。一般转移矩阵未必允许如此简化，也不能仅凭“列和为一”就声称收敛。

同一套乘法，回答三种不同问题

表示	列的含义	乘法在计算什么
邻接矩阵	从一个节点出发的边	一步连接与多步游走
关联矩阵	一条边对端点的收支	流量守恒与循环变化
转移矩阵	从一个节点出发的概率分布	随机状态的演化

选矩阵之前，先确定状态放在哪里、每个元素表示什么，以及方向约定。图与矩阵之间的翻译就不会只剩下记公式。

练习

练习转移概率不必对称

在本章网页模型中，从网页一到网页二，与从网页二到网页一的概率分别是多少？为什么不要求相等？

解答

分别是 $P_{21}=0.4$ 和 $P_{12}=0.1$。两个方向对应不同出发条件；每列和为一不要求矩阵对称。

练习验证循环变化

直接计算 $B\mathbf v_2$。若在一组可行交通流上加上 $t\mathbf v_2$，对任意实数 $t$ 都仍是可行车流吗？

解答

乘积为零，所以等式始终成立。但负的 $t$ 可能让道路流量小于零，物理可行性还要逐分量检查。

练习计数的是游走

两节点之间两个方向各有一条边，且没有自环。给出长度为二的游走数量，并说明为何不应称为简单路径。

解答

邻接矩阵交换两个坐标，其平方为单位矩阵。因此每个节点都有一条两步返回自己的游走，两个不同节点之间没有两步游走。返回起点重复了节点，不是简单路径。

练习从偏差公式预测下一步

三网页模型中，第一步状态为 $(300,1500,1200)^{\mathsf T}$。不用完整矩阵乘法，求第三步状态。

解答

总量为 $3000$。第一分量相对 $600$ 的偏差每步乘 $0.1$，第三步偏差为 $-3$，所以第一分量为 $597$。第三分量保持 $1200$，第二分量由守恒得到 $1203$。

参考文献

1. [1] X. Yang, “ENG1005 Week 2: Traffic Flow, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W2.tex ↩
2. [2] X. Yang, “ENG1005 Week 4: Webpage Transitions, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W4.tex ↩