谱图与代数图论读书笔记6

这里进入到了该书的第三部分，即 Physical Metaphors ，图的物理意义，第十章是本部分的第一章，也是讲图谱理论与运动的部分结合的开始。

图上的随机游走

本章要研究的主要是图的特征值如何控制随机游走矩阵的收敛。

随机游走

通过邻接矩阵以及拉普拉斯矩阵的性质，我们也就很自然的想到，通过矩阵来表示一个点在图上的游走概率，并将其定义为一个有权无向图，表示为$ G = (V,E,w) $。一个随机游走开始于某点，在每一个时间步会到达另一个点，如果图没有权重，那么点随机到达他临近的带你，如果有权重，那么根据权重，根据权重的概率到达其临接点。

定义一个$ p_t = \mathbb{R}^V $作为在时间步t上的概率分布的向量，对于所有 $a \in V$，使$ \sum_a p(a) = 1$，初识分布我们设为 $ p_0$，那么对于开始节点a有$ p_0(a) = 1 $，也就是说，该向量是一个onehot向量，此次walk开始于a。为了得到在时间t下的分布，我们可以考虑这样一个问题，t时间的概率分布主要来源于t-1时刻，而以此类推我们可以得到一个递推公式：

$$ p_{t+1}(a) = \sum_{b:(a,b)\in E}\dfrac{w(a,b)}{d(b)} p_t(b) $$

前半部分其实就是b到a的概率，对每一个b具有一个概率在这里被计算，而后面的$ p_t(b)$是在时间步t上进入b的概率，很明显，对于之前提到过的懒散随机游走（lazy random walk ）同样有:

$$ p_{t+1}(a) = (1/2)p_t(a) + (1/2)\sum_{b:(a,b)\in E}\dfrac{w(a,b)}{d(b)} p_t(b) $$

我们将$ \sum_{b:(a,b)\in E}\dfrac{w(a,b)}{d(b)} $拿出来并成一个矩阵称之为随机游走矩阵：$ W = MD^{-1} $

即$ p_{t+1} = Wp_t $

随机游走矩阵的空间与稳定分布

根据随机游走矩阵的定义，其不一定是对称矩阵，我们对其归一化得到新的对称矩阵：

$$ A = D^{-1/2}WD^{1/2} = D^{-1/2}MD^{-1/2}$$

根据之前的知识可以一眼看出，如果$ D^{1/2}\psi $是W关于$w$的特征向量，那么对于A来说$\psi$是其关于w的特征向量。

根据CF定理，我们可以看到关于W的特征值的取值范围为-1到1，对于懒散W是0到1。

我们继续观察，还可以看到d是W关于1的特征向量，由于1是最大的特征值，即谱半径，d又称为Perron vector，针对A得到$ \psi = \dfrac{d^{1/2}}{||d^{1/2}||} $

当vector继续游走，在某个时间步可以产生一个稳定状态，类似于马尔科夫的稳态，我们定义其为$ \pi = d/(1^Td) $

使$ \psi_1,…,\psi_n $为A的关于$ 2\omega_1-1,…,2\omega_n-1 $的特征向量，也是$ \hat{W} $的关于$ \omega_1,…,\omega_n $的特征向量，对于初始分布$ p_0 $写作$ D^{-1/2}p_0 = \sum_ic_i\psi_i , \ where \ c_i = \psi_i^TD^{-1/2}p_0$

于是$ p_t $可以写作$ D^{1/2}c_1\psi_1 + D^{1/2}\sum_{i\geq2}\omega_i^tc_i\psi_i $，其前半段就是$ \pi $即稳定分布

收敛的比率（The rate of convergence）

虽然我们没有办法直接推出熟练的概率，但是我们根据观察可以看到对于一个懒散随机游走矩阵，到一个稳定结构的速率与$ \omega_2 $相关，其值越小，收敛的越快。对此我们可以假设本次walk从a点出发，到达b点的概率是$ p_t(b) $，稳定状态下$ \pi(b) $与时间点t之间的差值为:

$$ |p_t(b)-\pi(b)| = \sqrt{\dfrac{d(b)}{d(a)}}\omega_2^t $$

证明：

对于b点，$p_t(b) = \delta_b^Tp_t = \pi(b) + \delta_b^TD^{1/2}\sum_{i\geq2}\omega_i^tc_i\psi_i$，将$c_i = \psi_i^TD^{-1/2}\delta_a = \dfrac{1}{\sqrt{d(a)}}\psi_i^T\delta_a $带入可以得到：

$$ \delta_b^TD^{1/2}\sum_{i \geq 2}\omega_i^tc_i\psi_i = \sqrt{\dfrac{d(b)}{d(a)}}\delta_b^TD^{1/2}\sum_{i \geq 2}\omega_i^t\psi_i\psi_i^T\delta_a$$

经过两次放缩

得到原式。