百科问答小站 logo
百科问答小站 font logo



一个无向图的邻接矩阵也是个实对称矩阵,它能否运用实对称矩阵的某些特有性质实现某些运用呢? 第1页

  

user avatar   weipeng-5-10 网友的相关建议: 
      

要说无向图对应的对称Laplace矩阵特有的性质的话,其实还真一时想不起来,毕竟基础领域里的人都特别热爱推广,无向图上的东西会推广到更一般的有向图上。而无向图也可以看作是特殊的双向连接的有向图。

限定在比较基础的知识上吧,比如最小生成树、谱聚类(无向图上的谱分解)之类的。当然不得不说的是这些都是存在有向图版本的,但在无向图上的应用多很多。

好,来到最小生成树,下面会介绍最小生成树的计数跟一个快速逼近的算法。再次声明最小生成树的计数有有向图版本,但快速逼近算法应该还没有人提。

对于一个无向图而言,其所谓的最小生成树就是一个连通了所有顶点的子图,而且是棵树。要得到一课最小生成树,那么可以考虑

  • Kruskal Algorithm
  • Prim Algorithm

最小生成树计数

但今天的问题不是这个,而是计算最小生成树总数。比如这个图:

一共有4种最小生成树,

这种简单还好枚举,更复杂的就需要点代数方法了。

还是以上面的图为例,构造邻接矩阵:

再构造度矩阵:

然后就得到了Laplace矩阵

观察得L是个半正定对称矩阵。然后就比较魔术了,选取任意的第行第列,比如,删除它们,得到子矩阵:

本来半正定的式子变成正定了,然后计算其行列式值

刚好是其最小生成树的总数。 这个就是 Kirchhoff’s Matrix Tree Theorem,对任意大的无向图,都有子矩阵行列式值跟最小生成树总数相等,更准确的表述请参考链接1。总之,一个组合计数问题转换成了一个线性代数问题。一个看起来比较麻烦的问题变成了一个可以简单硬算的问题。

快速算法

对于某些超大型的图,也被称作复杂网络,其最小生成树的总数可以作为连通性的一种指标,那么如果使用Kirchhoff’s Matrix Tree Theorem进行计算的话,就需要算矩阵的行列式。

如果是稠密矩阵,其计算量相当于一次LU分解,N个节点的图对应计算的时间复杂度就是

后来有人(参考链接3)意识到了下面这个算法(参考链接2)刚好可以干这个事情

Han, Insu, Dmitry Malioutov, and Jinwoo Shin. "Large-scale log-determinant computation through stochastic Chebyshev expansions." International Conference on Machine Learning. PMLR, 2015.

用了一种有趣的随机算法对进行逼近。对于任何一个正定矩阵,假设其最大特征值的一个任意上界为吗,先做变换,平移下特征值到 区间上,

那么有

其中 是N阶的正交多项式投影,也就是正交多项式展开逼近。另一方面,把矩阵放在多项式里计算也是挺费事的,幸运的是最后也只需要计算trace

更准确地讲,是

其中u是归一化的高斯随机向量或者Rademacher随机向量,这里的B得是个对称矩阵

然后只要采几个样进行逼近,矩阵跟矩阵的乘法也不用算了。剩下再用三项递推公式来继续减少计算量,总计算量就是几个矩阵向量乘法跟向量求和平均了,时间复杂度大概在:

不知道上面这个算不算利用了Laplace矩阵的对称性质,逼近算法本身倒是跟混沌多项式的思想挺像的:

参考链接:

[1] Kirchhoff’s Matrix Tree Theorem en.wikipedia.org/wiki/K

[2] 原算法 proceedings.mlr.press/v

[3] 在图上的应用 sciencedirect.com/scien




  

相关话题

  极小多项式有什么几何含义,怎么形象的理解这个概念? 
  [代数学]矩阵的概念最多可以推广到什么代数结构上? 
  设A,B,C均为n阶半正定实对称矩阵,使得ABC是对称阵.证明:ABC也是半正定阵.请问该怎么证明? 
  如何看待南昌大学2020线性代数期末考试,出卷人明知疫情期间学习效率低,仍故意极大提高试卷难度? 
  一个矩阵的逆矩阵是唯一的吗? 
  学习数论图论有必要先学抽代和高代吗? 
  如果高育良不看《万历十五年》而是《高等数学》或者《线性代数》,那赵瑞龙会怎样拿下他? 
  为什么初学量子力学一个矩阵都没有看到,却说线性代数是量子力学的数学语言? 
  如何从几何的角度说明对称矩阵的不同特征值对应的特征向量必定是两两正交的? 
  矩阵的指数函数到底说的是个啥? 

前一个讨论
高中男生陷入容貌焦虑怎么办?如何克服容貌焦虑?
下一个讨论
如何看待统计局:2021年全国人口增加48万人?





© 2024-11-21 - tinynew.org. All Rights Reserved.
© 2024-11-21 - tinynew.org. 保留所有权利