无向图的拉普拉斯矩阵

Definition

定义无权重的无向图G=（V，E）。V是顶点集合，E是边集合。

根据G，可得到一系列定义：

1. adjacency matrix（邻接矩阵） 𝐴𝐺 ：

(1)𝐴𝐺(𝑖,𝑗)={1,(𝑖,𝑗)∈𝐸0,(𝑖,𝑗)∉𝐸

2. degree matrix 𝐷𝐺 ：

这是一个对角矩阵，对角线上每个元素：

(2)𝐷𝐺(𝑖,𝑖)=∑𝑗𝐴𝐺(𝑖,𝑗)

3. Laplacian matrix 𝐿𝐺 ：

(3)𝐿𝐺=𝐷𝐺−𝐴𝐺

下面举一个例子：

Example（4）：如果G有三个顶点1，2，3。有边（1，2）、（1，3）。

𝑉={1,2,3},𝐸={(1,2),(1,3)}

𝐴𝐺=[011100100]𝐷𝐺=[200010001]𝐿𝐺=[2−1−1−110−101]

对于 𝐿𝐺 ，还有一种更方便的定义，就是选择G中每条边，求一个L，然后对L求和，就能得到 𝐿𝐺 。

回到例子（4），总共有两条边，按照上面说的，对每条边求一个L，因此就是两个L：

𝐿𝐺1,2=[1−10−110000],𝐿𝐺1,3=[10−1000−101],

得到：𝐿𝐺=𝐿𝐺1,2+𝐿𝐺1,3

用数学语言的形式表达，得到另一个等价定义：

(5)𝐿𝐺=∑(𝑢,𝑣)∈𝐸𝐿𝐺𝑢,𝑣

我们在用（5）这个定义得到一个结论：

𝑥𝑇𝐿𝐺𝑥=𝑥𝑇[∑(𝑢,𝑣)∈𝐸𝐿𝐺𝑢,𝑣]𝑥=∑(𝑢,𝑣)∈𝐸𝑥𝑇𝐿𝐺𝑢,𝑣𝑥=∑(𝑢,𝑣)∈𝐸(𝑥𝑢−𝑥𝑣)2

即：

(6)𝑥𝑇𝐿𝐺𝑥=∑(𝑢,𝑣)∈𝐸(𝑥𝑢−𝑥𝑣)2

（6）是一个非常重要的性质。

我们根据（6）可以得到一个推论：

Corr 1. 𝐿𝐺 是半正定的。

Laplacian Eigenvalues

𝐿𝐺 是实对称矩阵，因此可以对角化。也就有n个特征向量和特征值（n是G的顶点个数）。我们对n个特征值，从小到大做一个排序：

𝜆1≤𝜆2≤...≤𝜆𝑛

根据Corr 1，𝐿𝐺 是半正定矩阵。因此特征值都大于等于0，也即：

0≤𝜆1≤𝜆2≤...≤𝜆𝑛

这n个特征值中， 、、𝜆1、𝜆2、𝜆𝑛 最重要： 𝜆1=0 ， 𝜆2 和图的连通性关系非常大， 𝜆𝑛 有很多下界的结论。

𝜆1 的结论

要证明 𝜆1 =0,等价于证明：

∃𝑥,𝑠.𝑡.𝐿𝐺𝑥=0

取 𝑥=1 ，就有 𝐿𝐺1=0 。

𝜆𝑛 的结论

(7)∀𝑥∈𝑅𝑛,𝑥≠0,𝜆𝑛≥𝑥𝑇𝐿𝐺𝑥𝑥𝑇𝑥

（7）是很容易看出来的（对x做个特征值分解），当然也可以利用The Courant-Fischer Theorem去证明。

Lemma 1. 𝐺=(𝑉,𝐸) ， 𝜔∈𝑉 的度数degree是d。那么 𝜆𝑛(𝐺)≥𝑑+1 。

下面利用（6）、（7）来证明Lemma 1：

取 𝑥(𝑢)={𝑑,𝑢=𝑤−1,𝑖𝑓(𝑢,𝑤)∈𝐸0,𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 ，则：

𝜆𝑛≥𝑥𝑇𝐿𝐺𝑥𝑥𝑇𝑥=∑(𝑢,𝑣)∈𝐸(𝑥𝑢−𝑥𝑣)2𝑥𝑇𝑥≥∑(𝑢,𝑤)∈𝐸(𝑥𝑢−𝑑)2𝑥𝑇𝑥=𝑑(𝑑+1)2𝑑2+𝑑=𝑑+1

Lemma 1对所有顶点都成立，因此有 𝜆𝑛≥𝑑𝑚𝑎𝑥+1 。

𝜆2 的结论

𝜆2 和图的连通性关系非常大，这个特征值被单独命名为the algebraic connectivity of the graph。

这个笔记仅仅给一个最简单的结论：

Lemma 2. 𝜆2>0 的充要条件是 𝐺 是全连通的。

读书笔记小结

这个笔记简单讨论了一下Laplacian矩阵的概念和特征值（谱）。Laplacian矩阵是度数矩阵减去邻接矩阵。同时Laplacian矩阵也等于每个边的Laplacian矩阵之和，这很自然的推导出  𝑥𝑇𝐿𝐺𝑥=∑(𝑢,𝑣)∈𝐸(𝑥𝑢−𝑥𝑣)2。而这个结论一方面说明了Laplacian矩阵的半正定性，又能够结合Courant-Fischer Theorem得到大量关于特征值bound的结论。

关于特征值bound，这里给了三个小结论（实际上有非常多的研究和结论）。分别是： 𝜆1=0 ， 𝜆2>0 充要条件是G全连通， 𝜆𝑛≥𝑑𝑚𝑎𝑥+1 。

相关资料

图论我是昨天看分布式控制的时候开始学的，有很多大部头书或者Review，比如：

Modern Graph Theory​link.springer.com/book/10.1007/978-1-4612-0619-4

Laplacian matrices of graphs: a survey​www.sciencedirect.com/science/article/pii/0024379594904863

这些论文和书籍诚然是非常好的，但是对于我这种初学者，看的很晕，这里推荐一下Yale的课程讲义，前面几个Lecture很友好：

Spectral Graph Theory and its Applications​www.cs.yale.edu/homes/spielman/eigs/

另附一个Courant-Fischer Theorem介绍：

The Courant-Fischer Theorem​seanthesanta.github.io/courant-fischer/