百科问答小站 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




  

相关话题

  迹的几何意义是什么? 
  在AHP方法中,如果构造判断矩阵?依据是什么? 
  BERT中,multi-head 768*64*12与直接使用768*768矩阵统一计算,有什么区别? 
  迹的几何意义是什么? 
  只有三维向量有向量积吗? 
  设A,B,C均为n阶半正定实对称矩阵,使得ABC是对称阵.证明:ABC也是半正定阵.请问该怎么证明? 
  如何证明对任意给定的正数e,存在M上的矩阵范数||A||,满足不等式||A||<=谱半径+e? 
  若零向量没有方向,那它还是向量吗? 
  哈密尔顿-凯莱定理的本质是什么? 
  如何证明下面的矩阵秩的问题? 

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





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