Jiacheng's Library

杂谈：拉普拉斯矩阵和代数连通度 ​

拉普拉斯矩阵 ​

首先考虑图的关联矩阵（incidence matrix），C=C(G)C=C(G)。其中每一列表示的是图的节点，每一行表示的图的一条边。

image-20180623194254598

然后我们将这个关联矩阵可以写成：

C=[e0T e1T ⋮ em−1T]C=\begin{bmatrix}e_0^T\\\ e_1^T\\\ \vdots\\\ e_{m-1}^T\end{bmatrix}

其中，eke_k是一个边向量，表达了从节点 i 到节点 j 的一条边[⋯ ,1⏟i,⋯ ,−1⏟j,⋯ ][\cdots, \underbrace{1}_i, \cdots, \underbrace{-1}_j, \cdots]，其余位置都为 0。所以：

CTC=∑k=0m−1ek⋅ekTC^TC=\sum_{k=0}^{m-1}e_k \cdot e_k^T

image-20180623195155250

考虑上方这个矩阵，我们会发现它的对角线上，iiii这个位置和jjjj这个位置，会都为 1，其实表达了在该图中，节点 i 和 j 位置的度数为 1。而其余两个位置ijij和jiji则表达了该位置存在一条边。此时，该矩阵损失了方向信息。

当对这一系列矩阵求和，我们就得到了图的拉普拉斯矩阵，对角线表达了节点的度数，而非对角线部分则是边的信息。

当然，在有权图中，上面的关联矩阵，就不应该表示成 1 和-1，而应该是边的权重的平方根。

那么，拉普拉斯矩阵就可以定义成：

假设一个无向正权图G=(V,E)G=(V,E)，其邻接矩阵表示成AA，每个元素代表边的权重。其度矩阵表示成DD，是一个对角矩阵，对角线的元素则是每个节点所带的连接边的权重和（dij=∑kwikd_{ij}=\sum_kw_{ik}），这里不考虑自环。那么拉普拉斯矩阵（Laplacian）就是L=D−AL=D-A。

弹簧模型 ​

image-20180623222642725

首先，假设一组固定的杆子，他们上面套上了一些可以滑动的滑块，这些滑块的质量都是mm，滑块之间互相用弹簧链接。

当某个滑块ii上升到xix_i的位置时，该滑块受到的弹簧拉力应该是：−k(xi−xi−1)−k(xi−xi+1)=−k(−xi−1+2xi−xi+1)-k(x_i-x_{i-1})-k(x_i-x_{i+1})=-k(-x_{i-1}+2x_i-x_{i+1})。根据牛顿第一定律，滑块受到的拉力又应该是miai=mid2dt2xi(t)m_ia_i=m_i\frac{d^2}{dt^2}x_i(t)

image-20180623223323008

将所有滑块在时刻tt的位置写成向量形式：

x⃗(t)=[x0(t) x2(t) ⋮ xn−1(t)]\vec{x}(t)=\begin{bmatrix}x_0(t)\\\ x_2(t)\\\ \vdots\\\ x_{n-1}(t) \end{bmatrix}

那么，拉力可以被写成：

−k[1−1 −12−1 −12−1 ⋱ −12−1 −11]⋅x⃗-k\begin{bmatrix} 1 & -1 \\\ -1 & 2 & -1 \\\ & -1 & 2 & -1 \\\ & & & \ddots \\\ & & & -1 & 2 & -1 \\\ & & & & -1 & 1 \end{bmatrix}\cdot \vec{x}

该矩阵是一个t×nt \times n列的矩阵，该矩阵就可以被看做一个nn个点互相连接的单链条的图的拉普拉斯矩阵：

image-20180623232712358

最终每个点的位置，会呈现出一种正弦波的变化趋势，事实上，这个变化趋势是由多个正弦或者余弦波的叠加组成，也就是可以通过傅里叶变化，转换为频域上的模式，每一种模式和该拉普拉斯矩阵的特征向量所给定。

代数连通性 ​

首先介绍一些拉普拉斯矩阵的特性：

  1. 拉普拉斯矩阵是对称的。

  2. 拉普拉斯矩阵的特征值都是实数并且非负的，而且对应的特征向量都是实数并且正交的。按照惯例，会对这些特征值进行排序：λn−1≥λn−2≥⋯≥λ0≥0\lambda_{n-1} \geq \lambda_{n-2} \geq \cdots \geq \lambda_0 \geq 0

  3. 如果GG有kk个连通子图，当且仅当：

    λn−1=λn−2=⋯=λ0=0\lambda_{n-1} = \lambda_{n-2} = \cdots = \lambda_0 = 0

    （这一点也说明了，拉普拉斯矩阵的特征值和图的连通性有一定关联）

  4. 对于一个有nn个点的图GG，将该图分成正负两部分。 image-20180624000634025 记：

    v+={vertices in +} v−={vertices in −} x⃗=[x0 x1 ⋮ xn−1]s.t.xi={+1,if i ∈V+ −1,if i ∈V−\begin{align} v_+&=\{\text{vertices in }+\}\\\ v_-&=\{\text{vertices in }-\}\\\ \vec{x} &= \begin{bmatrix}x_0\\\ x_1\\\ \vdots\\\ x_{n-1} \end{bmatrix} s.t. x_i=\begin{cases} &+1, &\text{if i $\in V_+$} \\\ &-1, &\text{if i $\in V_-$} \end{cases} \end{align}

    那么，连通+-两部分的那些切割边的数量，则可以用14xTL(G)x​\frac{1}{4} x^TL(G)x​表示。

Courant minimax principle ​

承接上一节，假如需要最小化正负两部分的切割边，则我们需要min14xTL(G)xmin \frac{1}{4} x^TL(G)x

定理：给定任意实向量y⃗\vec{y}，对yy进行标准化，使得yTy=ny^Ty=n，且∑iyi=0\sum_iy_i=0

那么，使得14xTL(G)x\frac{1}{4} x^TL(G)x最小的yy满足以下条件：

14yTL(G)y=14nq⃗1TL(G)q⃗1=14nλ1\frac{1}{4} y^TL(G)y = \frac{1}{4} n \vec{q}_1^TL(G)\vec{q}_1=\frac{1}{4}n\lambda_1

其中，q⃗1\vec{q}_1和λ1\lambda_1是拉普拉斯矩阵的第二个特征向量和对应的特征值。

于是，GG的任意一种二分切割方法，最小只能切割出14nλ1\frac{1}{4}n\lambda_1条切割边。

假如，我们要找到，拥有最小切割边的分割方式，我们可以：

  1. 创建GG的拉普拉斯矩阵L(G)L(G)

  2. 计算该矩阵的第二个特征向量(λ1,q⃗1)(\lambda_1, \vec{q}_1)

  3. 用该特征向量的正负来表达xx，就能得到想要的分割方式。也即：

    x(i)←sign(q⃗1(i))x(i) \leftarrow sign(\vec{q}_1(i))