目标:
1)创建图的表征矩阵
2)分解:计算矩阵的特征值和特征向量;基于一个或多个特征值,将每个点表示成低维的表征
3)分组:基于新的表征,进行聚类
团间的连接性与每个团的密度相关
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231052890-1710281178.png)
spectral graph partitioning 谱图分割
无向图G的邻接矩阵A
x是n维的特征向量,可认为是G中每个节点的label或者value
那么Ax等到的结果的意义是?
yi是节点i的邻居节点的label的和
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231053275-730984707.png)
通过yi生成新的x value
谱图理论:
分析G的表征矩阵的spectrum
spectrum的意义:图的特征向量xi,(由特征值大小排序而得)
一个例子:假设G中的所有节点的度都有d,G是连通的。那么,G的特征值和特征向量是?
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231054216-443431195.png)
d是A的最大特征值
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231054706-1523024896.png)
若G不是完全连通的
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231055106-1090638385.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231055469-130044414.png)
矩阵表征
邻接矩阵:对称矩阵,有n个特征值,特征向量是实数且是正交的
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231055831-928473585.png)
度矩阵:![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231056141-1376999423.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231056141-1376999423.png)
拉普拉斯矩阵:L=D-A
对称矩阵
λ=λ1=0 ??
特征值为非负实数
特征向量是实数且永远正交
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231056478-776238988.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231056860-1569281881.png)
对于对称矩阵M,λ2的值由一公式可定 为xi--xj的平方和
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231057193-361055833.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231057578-706449223.png)
找到最优的x
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231057939-1820881528.png)
发现最优的割法
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231058350-769440963.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231100103-943512314.png)
谱聚类算法:
1)图的表征矩阵
2)矩阵的特征值和特征向量;基于特征向量生成每个店的低维向量
3)分组
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231100409-72497375.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231100746-1040639888.png)
例子
k-way spectral clustering k聚类
1)迭代的二分类
2)对eigenvector多聚类
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231101421-799842056.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231101779-477979401.png)
如何选择最优k——从特征值中,挑选间隔最大的两个相邻值
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231102161-500535630.png)
基于motif的谱聚类
基于连接模式进行聚类~![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231102485-2007833843.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231102485-2007833843.png)
主题1:发现motif的模块
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231102802-999385540.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231103108-1797030448.png)
定义motif conductance
找到节点集S使motif conductance最小, 但找到s较难
解决方案:通过谱的方法
步骤:
1)生成权重矩阵,值为该边参与生成motif的次数
2)谱聚类的方法
3)分组
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231104800-1283651124.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231105889-438587361.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231106484-491333413.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231106795-1291279396.png)
两个例子:食物链中未知的motif; 通信网络中已知的motif
未知的——每个motif跑一遍,找最小的
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231107623-1792296321.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231107899-516925098.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231108232-1756754671.png)
基因管理网络
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231109555-1684334247.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231109967-1605373417.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231110661-1545265862.png)