谱图论：Laplacian二次型和Markov转移算子

转载作者：我是一只小鸟更新时间：2023-09-27 07:01:59

以下部分是我学习 CMU 15-751: TCS Toolkit 的课堂笔记。由于只是个人笔记，因此许多地方在推导上可能不那么严谨，还望理论大佬多多包涵.

1 问题定义

1.1 无向图 $G$

在本文中，我们将研究对象限定在无向图（undirected graph） $G=(V, E)$ ，且满足:

有限（finite）；
允许重边和自环；
不允许度为0的顶点（即孤立，isolated顶点），但允许有多个连通分量；

此外，我们在某些情况下可能会假设 $G$ 是正则的.

正则图：指各顶点的度均相同的无向简单图.

1.2 顶点标签 $f$

定义设函数。

\[f: V\rightarrow \mathbb{R} \]

将图的每个顶点用一个实数值来进行标记，我们称其为顶点标签（vertex labelling）。在实际应用场景中， $f$ 可能是温度、电压、嵌入的坐标（推广到 $\mathbb{R}^d$ 时）或者 $S\subseteq V$ 的0-1示性函数.

在本文中，我们会将函数 $f$ 想成是一个如下所示的（列）向量:

\[\left(\begin{aligned} \bigg|\\ f\\ \bigg| \end{aligned}\right)\begin{aligned} \leftarrow &v_1\\ \leftarrow &v_2\\ &\vdots \\ \leftarrow &v_n \end{aligned} \]

回顾函数集合 $\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}$ 上带有加法和标量乘法:

加法： $f+g$ （逐点）；
标量乘法： $c\cdot f$ （ $c\in\mathbb{R}$ ）；

可以证明， $\mathcal{F}$ 是一个向量空间，且维度 $n=|V|$ 。后面我们还会在 $\mathcal{F}$ 上定义内积和范数.

2 Laplacian二次型

2.1 定义

接下来我们将要介绍的是谱图论（spectral graph theory）的关键，也就是 Laplacian二次型（Laplacian quadratic form），其定义如下:

\[\mathcal{E}\left[f\right] = \frac{1}{2}\cdot\mathbb{E}_{u\sim v}\left[ \left(f\left(u\right) - f\left(v\right)\right)^2\right] \]

（符号约定： $u\sim v$ 表示服从均匀分布的随机无向边 $(u, v)\in E$ ）。

直观地理解，Laplacian二次型刻画了图的“能量”（energy），这也是我们为什么用 $\mathcal{E}(f)$ 来表示它的原因。它在其它语境下，又被称为Dirichlet形式（Dirichlet form），局部方差（local variance），解析边界大小（analytic boundary size）.

2.2 性质

关于Laplacian二次型，我们有以下事实:

$\mathcal{E}\left[f\right]\geqslant 0$ ；。
$\mathcal{E}\left[c \cdot f\right] = c^2 \cdot \mathcal{E}\left[f\right]$ ；。
$\mathcal{E}\left[f + c \right] = \mathcal{E}\left[f\right]$ （ $c\in\mathbb{R}$ ）；。

直觉上， $\mathcal{E}\left[f\right]$ 的值越小，也就意味着 $f$ 更加“光滑”（smooth），即其值不会沿着边变化得太剧烈.

例设图顶点的子集 $S\subseteq V$ , 0-1示性函数 $f=\mathbb{I}_{S}$ 用于指示顶点是否在集合 $S$ 中，即:

\[f(u) = \left\{\begin{matrix} 1\quad\text{if}\quad u\in S\\ 0\quad\text{if}\quad u\notin S \end{matrix}\right. \]

则我们有:

\[\begin{aligned} \mathcal{E}\left[f\right] &= \frac{1}{2}\cdot\mathbb{E}_{u\sim v}\left[\left(\mathbb{I}_S(u) - \mathbb{I}_S(v)\right)^2\right] \\ &= \frac{1}{2} \cdot \mathbb{E}_{u\sim v}\left[\mathbb{I}_{(u, v) \text{ crosses the cut } (S, \bar{S})}\right]\\ &= \frac{1}{2}\left[\text{frac. of edges on the boundary of $S$}\right]\\ &= \text{Pr}_{u\sim v}\left[u\rightarrow v \text{ is stepping out of } S\right] \end{aligned} \]

注意上述式子中要乘以 $1/2$ 是因为我们考虑的是无向图，要避免有向边的重复计数（即“伸出”与“伸入” $S$ ），最后只需计算“伸出” $S$ 的边.

2.3 标准随机游走

为了选择一个随机顶点，我们可以:

均匀随机地选择一条边 $(u, v)$ ；
输出 $u$ （或 $v$ ）；

我们依据此采样方式得到的顶点分布记为 $\pi$ ， $\pi_i$ 表示顶点 $i$ 被抽中的概率。我们有以下事实:

事实 $\pi(u)$ 正比于 $\text{deg}(u)$ ，即。

\[\pi [u] = \frac{\text{deg}(u)}{2|E| }， \]

（注意这里用到了握手定理，即 $\sum_v \text{deg}(v)=2|E|$ ）。

直观地看， $\pi$ 为每个顶点给出了权重/重要性.

注：如果 $G$ 是正则的，那么 $\pi$ 是在 $V$ 上的均匀分布.

在此基础上，我们可以得到一些有用的结论.

事实下列步骤:

随机采 $u\sim \pi$ ；
再均匀随机地采 $u$ 的一个邻居 $v$ （记为 $v\sim u$ ）

实质上就等价于均匀随机地采样边 $(u, v)$ 。如果我们接着输出 $v$ ，则 $v$ 也服从分布 $\pi$ .

推论设 $t\in \mathbb{N}$ ，随机采 $u\sim \pi$ ，进行 $t$ 步的 “标准随机游走”（standard random walk，S.R.W.） :

\[\underbrace{u \rightarrow \cdot \rightarrow \cdot \rightarrow \cdots \rightarrow v}_{t} \]

则 $v$ 的分布也是 $\pi$ .

定义 $\pi$ 是不变（invariant）/ 平稳（stationary）分布 .

Q：现在假设 $u_0\in V$ 是非随机的，并从 $u_0 \overset{t}{\rightsquigarrow}v$ 。随着 $t\rightarrow \infin$ ， $v$ 的分布是否还会 $\rightarrow \pi$ ?

A：当 $G$ 非连通图时不是；当 $G$ 为二分图时也不是；而其它情况都是如此（我们后面会介绍原因）.

Q：那么需要多少步才能到达平稳分布呢（也即马尔可夫链的混合时间，mixing time）?

A：这需要考虑图 $G$ 的谱（特征值），具体我们会在下一讲中介绍。直观的例子比如图拥有较小的割集，那么在随机游走时就需要较长的时间来跨越 $S$ 和 $\bar{S}$ ；更极端的例子比如非连通图直接永远不会达到平稳分布。在 $2.2$ 中我们证明了若图的割集较小则其 $\mathcal{E}\left[\mathbb{I}_S\right]$ 就较小，而我们后面会看到快速收敛等价于 $\mathcal{E}\left[f\right]$ 永远不会小.

2.4 $f$ 的均值和方差

设 $f:V\rightarrow \mathbb{R}$ ，若 $u\sim \pi$ ，则 $f(u)$ 是一个实随机变量（我们这里简记为 $f$ ）。对于该随机变量，我们接下来讨论它的均值与方差.

均值（mean） $f$ 的均值定义为:

\[\mathbb{E}\left[f\right] = \mathbb{E}_{u\sim \pi}\left[f(u)\right] \]

例若 $S\subseteq V$ ， $f=\mathbb{I}_S$ ，则。

\[\mathbb{E}\left[ f \right] = \text{Pr}_{u\sim \pi}\left[u\in S\right] \]

直观上，这个概率表示 $S$ 的“权重”或“体积”.

方差（variance） $f$ 的方差定义为:

\[\begin{aligned} \text{Var}\left[f\right]=\text{Var}_{u\sim \pi}\left[f(u)\right]&\overset{(1)}{=}\mathbb{E}_{u\sim \pi}\left[\left(f\left(u\right) - \mu\right)^2\right] \\ &\overset{(2)}{=}\mathbb{E}_{u\sim\pi}\left[f(u)^2\right] -\mathbb{E}_{u\sim\pi}\left[f(u)\right]^2 \\ &\overset{(3)}{=} \frac{1}{2}\mathbb{E}_{\underset{\text{indep.}}{u, v \sim \pi}}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right] \end{aligned} \]

注意，上述式 $(3)$ 成立是由于:

\[\begin{aligned} &\mathbb{E}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right]\\ &=\mathbb{E}\left[f(u)^2 - 2f(u)f(v) + f(v)^2\right] \\ &=\underbrace{\mathbb{E}\left[f(u)^2\right] + \mathbb{E}\left[f(v)^2\right]} - \underbrace{2 \mathbb{E}\left[f(u)f(v)\right]}\\ &= 2\cdot \mathbb{E}\left[f(u)^2\right] - \underbrace{2\mathbb{E}\left[f(u)\right]\mathbb{E}\left[f(v)\right]}_{2\cdot\mathbb{E}\left[f(u)\right]^2} \end{aligned} \]

辨析这里要注意 $f$ 的方差 $\text{Var}(f)$ 和其能量 $\mathcal{E}(f)$ 的差异，它们俩的对比如下:

\[\begin{aligned} \text{Var}\left[f\right]&=\frac{1}{2}\mathbb{E}_{\underset{\text{indep.}}{u, v \sim \pi}}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right] \\ \mathcal{E}\left[f\right]&=\frac{1}{2}\mathbb{E}_{u \sim v}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right] \end{aligned} \]

可见方差 $\text{Var}[f]$ 是对图的顶点取期望（我们称其为关于 $f$ 的全局方差，global variance），而 $\mathcal{E}[f]$ 则是对图的边取期望（我们称其为关于 $f$ 的局部方差，local variance）.

3 Laplacian二次型的极值

3.1 $\mathcal{F}$ 上的的内积与范数

接下来我们讨论Laplacian二次型的极值，而这就需要我们先定义 $\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}$ 空间上的内积和范数.

定义设 $f, g: V\rightarrow\mathbb{R}$ ，则向量空间 $\mathcal{F}$ 上的加权内积（weighted inner product）可以定义为:

\[\langle f, g \rangle_{\pi} := \mathbb{E}_{u\sim \pi}[f(u)\cdot g(u)] \]

直观地，我们可以将其写做:

\[\langle \left(\begin{aligned} \bigg| \\ f\\ \bigg| \end{aligned}\right), \left(\begin{aligned} \bigg| \\ g\\ \bigg| \end{aligned}\right) \rangle_{\pi} \]

注：当 $G$ 是正则图时（此时 $\pi$ 为均匀分布），上式是经由 $\frac{1}{|V|}$ 缩放的“标准点积”（normal dot product）.

回顾实向量空间上的内积满足以下性质。

$\langle f, g\rangle_{\pi}=\langle g, f\rangle_{\pi}$ ；
$\langle c\cdot f + g, h\rangle_{\pi} = c\langle f, h\rangle_{\pi} + \langle g, h \rangle_{\pi}$ （ $c\in\mathbb{R}$ ）；
$\langle f, f\rangle_{\pi}=\mathbb{E}_{u\sim\pi}\left[f(u)^2\right]\geqslant 0\quad \text{with equality iff } f\equiv 0$ ；

定义对于 $f\in\mathcal{F}$ ，我们可以由内积诱导出 $f$ 的 $2$ -范数:

\[\lVert f \rVert_2 := \sqrt{\langle f, f\rangle_{\pi}} = \sqrt{\mathbb{E}_{u\sim\pi}\left[f(u)^2\right]}。 \]

处理2-范数的平方通常比直接处理它更容易，故我们常常使用 $ \lVert f \rVert^2_2:=\langle f, f\rangle_{\pi}=\mathbb{E}_{u\sim\pi}\left[f(u)^2\right] $ .

此外，我们还可以定义 $f$ 的 $1$ -范数:

\[\lVert f \rVert_1 := \mathbb{E}_{u\sim \pi}\left[|f(u)|\right] \]

例设 $S\subseteq V$ ， $f=\mathbb{I}_S$ ，则。

\[\begin{aligned} \lVert f\rVert_1 &:= \mathbb{E}_{u\sim\pi}\left[|f(u)|\right] =\mathbb{E}_{u\sim\pi}\left[f(u)\right] \\ &= \text{Pr}_{u\sim\pi}\left[u\in S\right] = \text{Volume}(S) \end{aligned} \]

且我们有。

\[\begin{aligned} \lVert f\rVert_2^2 := \mathbb{E}_{u\sim\pi}\left[f(u)^2\right] = \mathbb{E}_{u\sim\pi}\left[f(u)\right] = \lVert f\rVert_1 & \end{aligned} \]

3.2 最小化/最大化 $\mathcal{E}\left[f\right]$

我们在 2.3 中提到随机游走快速收敛等价于 $\mathcal{E}\left[f\right]$ 永远不会小，那么 $\mathcal{E}\left[f\right]$ 能够有多小呢?

最小化现在我们来考虑最小化 $\mathcal{E}\left[f\right]$ ，即求解:

\[\min \mathcal{E}[f] \]

我们已知 $\mathcal{E}[f]\geqslant0$ ，故我们接下来讨论什么样的 $f$ 可以使 $\mathcal{E}[f]=0$ .

首先对于 $f\equiv 0$ （即将图的每个顶点都映射到 $0$ ）这一trival的情况， $\mathcal{E}\left[f\right]=0$ ；。

接下来考虑non-trival的情况。我们注意到 $f\equiv 1$ （或任何其它常数）时，。

\[\mathcal{E}[ f ]=\frac{1}{2} \mathbb{E}_{u\sim v}\left[\left(f(u) - f(v)\right)^2\right] = 0 \]

事实上，由于图的不同连通分量之间是不存在边的，因此只要保证 $f$ 在图 $G$ 的每个连通分量上是常数就行.

命题 $\mathcal{E}[f]=0$ 当且仅当 $f$ 在 $G$ 的每个连通分量上是常数。此时:

\[\text{\# connected components of } G = \text{\# lin. indep } f \text{ with } \mathcal{E}[f]=0 \]

即当图的连通分量为 $S_1,\cdots, S_l$ 时, $\mathbb{I}_{S_1}, \mathbb{I}_{S_2}, \cdots, \mathbb{I}_{S_l}$ 是线性无关的（linearly independent）（并满足 $\mathcal{E}\left[f\right]=0$ 约束）。所谓线性无关，直观上即如下所示的关系:

\[\begin{aligned} S_1\bigg\{ \\ \\ \\ \\ \end{aligned} \left(\begin{aligned}1\\1\\1\\0\\\vdots\\0\end{aligned}\right) \begin{aligned} \\ \\ \\ \\ S_2 \bigg\{\\ \\ \end{aligned}\left(\begin{aligned}0\\0\\0\\1\\\vdots\\1\end{aligned}\right) \]

更一般地说，集合 $\{f: \mathcal{E}[f]=0\}$ 事实上就是 $\mathbb{I}_{S_1}, \mathbb{I}_{S_2}\cdots, \mathbb{I}_{S_l}$ 的张成空间 $\{\sum^l_{i=1}c_i\mathbb{I}_{S_i}: c_1,\cdots, c_l\in \mathbb{R}\}$ .

最大化接下来我们来考虑最大化 $\mathcal{E}\left[f\right]$ ，即求解。

\[\begin{aligned} &\text{max } \mathcal{E}[f]\quad \\ \text{s.t.}\quad &\text{Var}[f]=1(\leqslant 1) \end{aligned} \]

（这里需要注意由于 $\mathcal{E}[c\cdot f]=c^2\mathcal{E}[f]$ ，故我们要添加关于 $\text{Var}\left[f\right]$ 的约束项以控制常数缩放因子的影响）。

事实上，上述优化问题即等价于:

\[\begin{aligned} &\text{max } \mathcal{E}[f]\quad \\ \text{s.t.}\quad &\lVert f \rVert^2_2=\mathbb{E}\left[ f^2 \right]=1 (\leqslant1) \end{aligned} \]

这是因为:

\[\begin{aligned} \text{Var}[f] &= \mathbb{E}[f^2] - \mathbb{E}[f]^2\\ \Rightarrow\mathbb{E}[f^2] &= \text{Var}[f] + \underbrace{\mathbb{E}[f]^2}_0 \end{aligned} \]

直觉上，该优化问题是在寻找一个好的嵌入 $V\rightarrow \mathbb{R}$ ，使得边的两个端点在嵌入空间中能够尽可能“远”。那么，什么样的 $G$ 才能最成功呢？答案是二分图.

如果 $G$ 是二分图， $V=(V_1, V_2)$ 。设。

\[f = \mathbb{I}_{V_1} - \mathbb{I}_{V_2} \]

也即。

\[f(u) = \left\{\begin{aligned} +1, \quad \text{if } u \in V_1 \\ -1, \quad \text{if } u \in V_2 \end{aligned}\right.， \]

于是我们有 $\lVert f \rVert^2_2=\mathbb{E}[f^2]=\mathbb{E}\left[1\right]=1$ ，且 $\mathcal{E}[f]=2$ （由于 $\frac{1}{2}\mathbb{E}_{u\sim v}[(f(u) - f(v))^2]$ 中 $f(u)$ 和 $f(v)$ 都为 $\pm1$ ）。

命题 $\mathcal{E}[f] \leqslant 2 \lVert f \rVert^2_2$ （即 $2\mathbb{E}[f^2]$ ）。

证明如下:

\[\begin{aligned} \mathcal{E}[f] &= \frac{1}{2}\mathbb{E}_{u\sim v}\left[(f(u)-f(v))^2\right]\\ &= \frac{1}{2} \mathbb{E}_{\underbrace{u\sim v}_{u\sim\pi}}[f(u)^2] + \frac{1}{2}\mathbb{E}_{\underbrace{u\sim v}_{v\sim\pi}}[f(v)^2] - \mathbb{E}_{u\sim v}[f(u)f(v)]\\ & \leqslant \mathbb{E}[f^2] + \underbrace{\sqrt{\mathbb{E}_{u\sim v}[f(u)^2]}}_{\mathbb{E}\left[f^2\right]}\underbrace{\sqrt{\mathbb{E}_{u\sim v}[f(v)^2]}}_{\mathbb{E}\left[f^2\right]} \quad (\text{Cauchy Schwarz})\\ &=2 \mathbb{E}[f^2] \end{aligned} \]

例等式 $\mathcal{E}[f] = 2 \lVert f\rVert^2_2$ 当且仅当 $G$ 为二分图的时候成立.

4 Markov转移算子

4.1 定义

根据我们前面在 3.2 中的的叙述，我们已经知道。

$\mathcal{E}[f]=\text{arithm}= \lVert f\rVert^2_2 - \mathbb{E}_{u\sim v}[f(u)\cdot f(v)] $ 。

这里。

\[\mathbb{E}_{u\sim v}[f(u)\cdot f(v)]=\mathbb{E}_{u\sim\pi}\mathbb{E}_{v\sim u}[f(u)f(v)] = \mathbb{E}_{u\sim\pi}\left[f(u)\cdot \underbrace{\mathbb{E}_{v\sim u}\left[f(v)\right]}_*\right] \]

注意上图中的带 $*$ 表达式 $\mathbb{E}_{v\sim u}\left[f(v)\right]$ 刻画的是顶点 $u$ 邻居集合 $\{v\}$ 的 $f$ 标签平均值。而这个表达式实际上描述了一个将顶点 $u$ 映射到其邻居标签平均值的函数，接下来我们就来进一步研究这个函数.

定义我们定义函数 $Kf: V\rightarrow\mathbb{R}$ 满足。

\[ \quad (Kf)(u)= \mathbb{E}_{v\sim u}\left[f(v)\right] \]

由于我们是离散状态空间，故上式可以写为 $(Kf)(u)=\sum_v f(v)\text{Pr}\left[v\rightarrow u\mid v\right]$ ，这里 $\text{Pr}[v\rightarrow u\mid v]$ 表示邻居顶点 $v$ 到当前顶点$ u $的状态转移概率。直观地理解，函数$ Kf $使得顶点$ u $被赋予其邻居集合的$ f$标签平均值.

这里 $K$ 为定义在函数空间 $\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}$ 上的线性算子，它将函数 $f\in\mathcal{F}$ 映射到 $Kf\in\mathcal{F}$ ，并满足:

\[\begin{aligned} &K(f + g) = Kf + Kg \\ &K(c\cdot f) = c\cdot\left( Kf\right)\quad (c\in \mathbb{R}) \end{aligned} \]

定义我们将上述的算子 $K$ 称为图 $G$ 的 Markov转移算子（Markov transition operator）/归一化邻接矩阵（normalized adjacency matrix） .

我们可以将算子 $K$ 表示成一个矩阵，该矩阵以如下方式作用:

\[\begin{aligned} u\rightarrow\\ \\ \end{aligned}\left( \begin{matrix} & \cdots & \\ & K & \\ & & \end{matrix}\right)\left(\begin{matrix} \bigg| \\ f \\ \bigg| \end{matrix}\right)\begin{aligned} \leftarrow &v_1\\ &\vdots\\ \leftarrow &v_n \end{aligned} =\left(\begin{aligned} \bigg|\\ K&f \\ \bigg| \end{aligned}\right) \begin{aligned} \leftarrow u \\ \\ \\ \end{aligned} \]

且满足。

\[K[u, v]=\left\{ \begin{aligned} & \frac{1}{\text{deg}(v)}, f(v, u)\in E \\ & 0 \end{aligned} \right\}=\text{Pr}_{\text{S.R.W.}}[v\rightarrow u\mid v] \]

所以 $K$ 是归一化后的邻接矩阵 $A$ 的转置（当然这里由于我们关注无向图， $A^T=A$ ），其每一列的和为 $1$ （代表一个概率分布）。这样的矩阵被称为随机矩阵（stochastic marix） .

4.2 自伴性质

如果图 $G$ 是 $d$ -正则的（即所有顶点的度都为 $d$ ），那么我们有:

\[K = \frac{1}{d} A \quad \& \quad K\text{ is symmtric, } K^T= K \]

那么对于非正则图呢？此时 $K$ 的矩阵表示（在非规范正交基下）尽管可能不再是对称阵，但是算子 $K$ 仍然满足自伴的性质。我们有以下事实：事实对于 $f, g: V\rightarrow \mathbb{R}$ ，。

\[\langle f, Kg\rangle=\mathbb{E}_{u\sim v}\left[f(u)\cdot g(v)\right]=\mathbb{E}_{v\sim u}\left[f(v)\cdot g(u)\right] \]

证明。

\[\begin{aligned} \langle f, Kg\rangle &=\mathbb{E}_{u\sim \pi}\left[f(u)\cdot (Kg)(u) \right]\\ &=\mathbb{E}_{u\sim\pi}\left[f(u)\cdot \mathbb{E}_{v\sim u}\left[g(v)\right]\right] \\ &= \underbrace{\mathbb{E}_{u\sim \pi}\mathbb{E}_{v\sim u}}_{(u, v)\text{ rand edge}}\left[f(u)\cdot g(v)\right]\\ &= \mathbb{E}_{u\sim v}\left[f(u)\cdot g(v)\right]\\ &= \mathbb{E}_{v\sim u}\left[f(v)\cdot g(u)\right]\\ \end{aligned} \]

基于此，我们有下列推论：推论。

\[\langle Kf, g \rangle = \langle f, Kg \rangle \]

也即 $K$ 是自伴的（self-adjoint）。而这在图 $G$ 是正则图的情况下就等价于 $K$ 是对称的.

接下来再来看我们熟悉的那个示性函数例子.

例设 $S, T\subseteq V$ （ $S\cap T=\emptyset$ ）， $f=\mathbb{I}_S$ ， $g=\mathbb{I}_T$ ，则:

\[\begin{aligned} \langle f, Kg\rangle &=\mathbb{E}_{u\sim v}\left[\mathbb{I}_S(u) \cdot \mathbb{I}_T(v)\right] \\ &= \text{Pr}_{u\sim v}\left[u\in S, v\in T\right] \end{aligned} \]

4.3 Markov链

概率分布转移设 $p$ 为在顶点 $V$ 上的概率分布，即。

\[p = \left(\begin{aligned} p_1\\ p_2\\ \vdots\\ p_n \end{aligned}\right)\begin{aligned} \leftarrow v_1 \\ \\ \\ \leftarrow v_n \end{aligned} \]

我们进行如下步骤:

随机采一个顶点 $u\sim p$ 。
进行一步从 $u\rightarrow v$ 的随机游走，并设 $p^{\prime}$ 为 $v$ 的概率分布。

则我们有如下的概率分布转移关系:

\[ \left(\begin{aligned} \bigg|\\ p^{\prime}\\ \bigg| \end{aligned}\right)= \left( \begin{matrix} & & \\ & K & \\ & & \end{matrix}\right) \left(\begin{aligned} \bigg|\\ p\\ \bigg| \end{aligned}\right) \]

推论对于平稳概率分布 $\pi$ ，满足。

\[\pi K = \pi \]

接下来我们再展示一个例子说明概率转移具体是如何运作的.

引理对于算子$K^2 = K \circ K $，我们有:

\[(K^2 f)(u) = \mathbb{E}_{\begin{aligned} u\rightarrow w\\ 2 \text{ step} \end{aligned}}\left[f(w)\right] \]

证明给定 $f$ ，设 $g=Kf$ ，则。

\[K^2f = K(Kf) = Kg, \]

故。

\[（K^2f)(u) = (Kg)(u) = \mathbb{E}_{v\sim u}\left[g(v)\right] = \mathbb{E}_{v\sim u}\left[(Kf)(v)\right] = \mathbb{E}_{v\sim u}\left[\mathbb{E}_{w\sim v}\left[f(w)\right]\right] \quad\blacksquare \]

推论 $\forall t \in \mathbb{N}$ ， $(K^tf)(u)=\mathbb{E}_{u \overset{t\text{-step S.R.W}}{ \rightsquigarrow} w}\left[ f(w)\right]$ （甚至 $t=0$ 时，我们也有 $I f(u) = f(u)$ ）.

参考

[1] CMU 15-751: TCS Toolkit [2] Bilibili: CMU计算机科学理论(完结)—你值得拥有的数学和计算机课 ) [3] Spielman D. Spectral graph theory[J]. Combinatorial scientific computing, 2012, 18: 18. [4] Axler S. Linear algebra done right[M]. springer publication, 2015. 。

最后此篇关于谱图论：Laplacian二次型和Markov转移算子的文章就讲到这里了,如果你想了解更多关于谱图论：Laplacian二次型和Markov转移算子的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。