拉普拉斯矩阵和代数连通度

拉普拉斯矩阵

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

image-20180623194254598

然后我们将这个关联矩阵可以写成：
$$
C=\begin{bmatrix}e_0^T\\ e_1^T\\ \vdots\\ e_{m-1}^T\end{bmatrix}
$$
其中，$e_k$是一个边向量，表达了从节点i到节点j的一条边$[\cdots, \underbrace{1}_i, \cdots, \underbrace{-1}_j, \cdots]$，其余位置都为0。所以：
$$
C^TC=\sum_{k=0}^{m-1}e_k \cdot e_k^T
$$
image-20180623195155250

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

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

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

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

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

弹簧模型

image-20180623222642725

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

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

image-20180623223323008

将所有滑块在时刻$t$的位置写成向量形式：
$$
\vec{x}(t)=\begin{bmatrix}x_0(t)\\ x_2(t)\\ \vdots\\ x_{n-1}(t) \end{bmatrix}
$$
那么，拉力可以被写成：
$$
-k\begin{bmatrix}
1 & -1 \\
-1 & 2 & -1 \\
& -1 & 2 & -1 \\
& & & \ddots \\
& & & -1 & 2 & -1 \\
& & & & -1 & 1
\end{bmatrix}\cdot \vec{x}
$$
该矩阵是一个$t \times n$列的矩阵，该矩阵就可以被看做一个$n$个点互相连接的单链条的图的拉普拉斯矩阵：

image-20180623232712358

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

代数连通性

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

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

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

  3. 如果$G$有$k$个连通子图，当且仅当：
    $$
    \lambda_{n-1} = \lambda_{n-2} = \cdots = \lambda_0 = 0
    $$
    （这一点也说明了，拉普拉斯矩阵的特征值和图的连通性有一定关联）

  4. 对于一个有$n$个点的图$G$，将该图分成正负两部分。
    image-20180624000634025
    记：
    $$
    \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}
    $$
    那么，连通+-两部分的那些切割边的数量，则可以用$\frac{1}{4} x^TL(G)x​$表示。

Courant minimax principle

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

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

那么，使得$\frac{1}{4} x^TL(G)x$最小的$y$满足以下条件：
$$
\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
$$

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

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

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

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

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

  3. 用该特征向量的正负来表达$x$，就能得到想要的分割方式。也即：
    $$
    x(i) \leftarrow sign(\vec{q}_1(i))
    $$