要说无向图对应的对称Laplace矩阵特有的性质的话,其实还真一时想不起来,毕竟基础领域里的人都特别热爱推广,无向图上的东西会推广到更一般的有向图上。而无向图也可以看作是特殊的双向连接的有向图。
限定在比较基础的知识上吧,比如最小生成树、谱聚类(无向图上的谱分解)之类的。当然不得不说的是这些都是存在有向图版本的,但在无向图上的应用多很多。
好,来到最小生成树,下面会介绍最小生成树的计数跟一个快速逼近的算法。再次声明最小生成树的计数有有向图版本,但快速逼近算法应该还没有人提。
对于一个无向图而言,其所谓的最小生成树就是一个连通了所有顶点的子图,而且是棵树。要得到一课最小生成树,那么可以考虑
但今天的问题不是这个,而是计算最小生成树总数。比如这个图:
一共有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 https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem
[2] 原算法 http://proceedings.mlr.press/v37/hana15.html
[3] 在图上的应用 https://www.sciencedirect.com/science/article/abs/pii/S0898122117307010