冯诺依曼图熵(VNGE)Python实现及近似计算

本文共871个字,预计阅读时间需要3分钟。

简介

冯·诺依曼图熵(VNGE)有助于测量图序列中图之间的信息差异和距离。

给定第一个无向图 G=(V, E, A), 其中 A 是对称的邻接矩阵。 度矩阵定义为 D=diag(d_1,...,d_n),则它的拉普拉斯矩阵为 L=D-A。其中后者的特征值 \lambda_i 被称为拉普拉斯谱。 这里,H_{vn}(G) 为冯诺依曼图熵(von Neumann graph entropy)。

    \[ H_{vn}(G)=-\sum \limits_{i=1}^{n}(\frac{\lambda_i}{vol(G)}\log\frac{\lambda_i}{vol(G)}) \]

图的容量为 vol(G)=\sum_{i=1}^{n}\lambda_i=trace(L)。时间复杂度较高,是 O(n^3)

我提供了Python版本代码来计算VNGE。应该注意的是陈等人给出了一种称为FINGER [1]的近似方法,该方法将VNGE的三次复杂度降低为节点和边的数量的线性复杂度。

VNGE和FINGER的代码如下。

代码

结果

H_vn exact: 11.496599468152386
Time: 13.172455072402954
H_vn approx: 10.63029083591871
Time: 0.23734617233276367

 

[1] Chen, Pin-Yu, et al. “Fast incremental von neumann graph entropy computation: Theory, algorithm, and applications.” International Conference on Machine Learning. PMLR, 2019.

更多内容访问 [omegaxyz.com](https://www.omegaxyz.com/)
网站所有代码采用Apache 2.0授权
网站文章采用知识共享许可协议BY-NC-SA4.0授权
© 2021 • OmegaXYZ-版权所有 转载请注明出处

评论