谱图理论（spectrum theory）实操

大家好，欢迎来到IT知识分享网。

前言

知乎上的这篇文章比较详细的探讨了谱图理论并提供了参考文献，其中提及了比较有趣的两点：
1、拉普拉斯矩阵的特征值为0的个数就是连通区域的个数。
2、在真实场景中可能不存在特征值为0的孤岛（因为每个人或多或少都会跟人有联系），但是当特征值很小的时候，也能反应出某种“孤岛”，或者称为，bottleneck，这种bottleneck显然是由第二小的特征值决定的（因为特征值为0就是真正孤岛，但第二小就是有一点点边，但还是连通的），因此，很多发现社交社群的算法都会或多或少利用利用这一点，因为不同的社群肯定是内部大量边，但是社群之间的边很少，从而形成bottleneck。
本文通过简单的例子探索以上两点。

例子一

图的结构如上图所示，一共有两个连通区域，我们看下拉普拉斯矩阵的计算结果。

import numpy as np from numpy.linalg import eig, inv #adjacent matrix a=np.array([[0,1,0,1,0,0,0], [1,0,1,0,0,0,0], [0,1,0,1,0,0,0], [1,0,1,0,0,0,0], [0,0,0,0,0,1,1], [0,0,0,0,1,0,1], [0,0,0,0,1,1,0]]) #degree matrix d=np.array([[2,0,0,0,0,0,0], [0,2,0,0,0,0,0], [0, 0, 2, 0, 0, 0, 0], [0, 0, 0, 2, 0, 0, 0], [0, 0, 0, 0, 2, 0, 0], [0, 0, 0, 0, 0, 2, 0], [0, 0, 0, 0, 0, 0, 2] ]) #standard laplace matrix _d=np.sqrt(inv(d)) L=np.identity(7)-np.matmul(np.matmul(_d,a),_d) #compute eigenvalues and corresponding feature vectors eigenvalue,featurevector=np.linalg.eig(L) #show feature vectors, sort by eigenvalues res=list(zip(eigenvalue,featurevector.T)) res.sort()

每个特征向量对应了一种图的分割方式，即哪些点是一组。我们看下结果：

Eigenvalue: -3.54696e-16 Feature vector: [ 0. 0. 0. 0. -0. -0. -0.] Eigenvalue: -1.99342e-17 Feature vector: [-0.5 -0.5 -0.5 -0.5 0. 0. 0. ] Eigenvalue: 0.99999 Feature vector: [ 7.0e-01 3.e-16 -7.0e-01 5.e-17 0.00000000e+00 0.00000000e+00 0.00000000e+00] Eigenvalue: 1.0 Feature vector: [ 0.00000000e+00 -7.0e-01 -3.e-16 7.0e-01 0.00000000e+00 0.00000000e+00 0.00000000e+00] Eigenvalue: 1.5 Feature vector: [ 0. 0. 0. 0. 0. -0. -0.] Eigenvalue: 1.00002 Feature vector: [ 0. 0. 0. 0. 0. -0. 0.] Eigenvalue: 2.0000000000000018 Feature vector: [-0.5 0.5 -0.5 0.5 0. 0. 0. ]

第一、二个特征值为0，这与我们的图结构一致。零特征值对应的特征向量将A、B、C、D划为一组，E、F、G划为一组。下面再看一个更加复杂的例子，验证bottleneck。

例子二

#adjacent matrix a=np.array([ [0,1,1,0,0,0,0,0,0,0], [1,0,1,0,0,0,0,0,0,0], [1,1,0,1,0,0,0,0,0,0], [0,0,1,0,0,1,0,1,0,0], [0,0,0,0,0,1,1,0,0,0], [0,0,0,1,1,0,1,0,0,0], [0,0,0,0,1,1,0,0,0,0], [0,0,0,1,0,0,0,0,1,1], [0,0,0,0,0,0,0,1,0,1], [0,0,0,0,0,0,0,1,1,0] ]) #degree matrix d=np.diag([2,2,3,3,2,3,2,3,2,2]) #standard laplace matrix _d=np.sqrt(inv(d)) L=np.identity(a.shape[0])-np.matmul(np.matmul(_d,a),_d) #compute eigenvalues and corresponding feature vectors eigenvalue,featurevector=np.linalg.eig(L) #show feature vectors, sort by eigenvalues res=list(zip(eigenvalue,featurevector.T)) res.sort()

结果如下：

Eigenvalue: 2.28914e-17 Feature vector: [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.] Eigenvalue: 0. Feature vector: [-6.e-02 -6.e-02 -6.e-02 -1.e-16 -3.e-01 -3.e-01 -3.e-01 4.e-01 4.e-01 4.e-01] Eigenvalue: 0.41044 Feature vector: [ 4.e-01 4.e-01 4.e-01 3.e-16 -2.e-01 -2.e-01 -2.e-01 -2.e-01 -2.e-01 -2.e-01] Eigenvalue: 0.18317 Feature vector: [ 0. 0. -0. -0. 0. -0. 0. -0. 0. 0.] Eigenvalue: 1.5895 Feature vector: [-3.e-01 -3.e-01 6.e-01 2.e-16 1.e-01 -3.e-01 1.e-01 -3.e-01 1.e-01 1.e-01] Eigenvalue: 1.58961 Feature vector: [ 1.e-02 1.e-02 -3.e-02 -5.e-17 2.e-01 -5.e-01 2.e-01 6.0e-01 -2.e-01 -2.e-01] Eigenvalue: 1.99998 Feature vector: [ 4.e-02 -4.e-02 4.e-16 -3.e-16 7.0e-01 2.e-15 -7.0e-01 -2.e-15 1.e-15 1.e-15] Eigenvalue: 1.5 Feature vector: [ 7.0e-01 -7.0e-01 -3.e-16 1.e-15 3.e-16 -1.e-15 5.e-16 -1.e-15 6.e-16 6.e-16] Eigenvalue: 1.00004 Feature vector: [ 1.e-19 -7.e-18 8.e-18 -4.e-18 -6.e-17 4.e-17 -5.e-17 -4.e-17 -7.0e-01 7.0e-01] Eigenvalue: 1.817 Feature vector: [-0. -0. 0. -0. -0. 0. -0. 0. -0. -0.]

从结果中我们可以看到，零特征值只有一个，也就是说只有一个连通分支。第二小的特征值对应的特征向量将原图划分为ABC、D、EFG、HIJ，如下图所示：

特征值刻画了分割方式经过的边数多少，特征值越小，经过的边越少，零特征值对应一个连通分支，所以分割不经过任何边，因为所有点都在这一个连通分支中。上面的分割方式切割三条边。我们看下最大特征值对应的分割方式需要切割几条边。

最大特征值的切割方式是，ABEGJI是一组，CFH一组，D一组，一共切割7条边。

总结

本文以实际例子讨论了谱图理论的若干有趣的结论。给定一个图，计算连通分支的个数是一个很经典的问题，可以使用UnionFind求解，是一个纯计算机的解法。而计算Laplace矩阵的零特征值个数求解这个问题，就属于纯数学的方法了。同一个问题既可以使用计算机方法解决，也可以使用纯数学方法解决，真的是非常奇妙啊。