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

Reacubeth 2021-02-23 13:56:07
Python 实现 近似 vnge 近似计算


简介

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

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

H v n ( G ) = − ∑ i = 1 n ( λ i v o l ( G ) log ⁡ λ i v o l ( G ) ) H_{vn}(G)=-\sum \limits_{i=1}^{n}(\frac{\lambda_i}{vol(G)}\log\frac{\lambda_i}{vol(G)}) Hvn(G)=i=1n(vol(G)λilogvol(G)λi)

图的容量为 v o l ( G ) = ∑ i = 1 n λ i = t r a c e ( L ) vol(G)=\sum_{i=1}^{n}\lambda_i=trace(L) vol(G)=i=1nλi=trace(L)。时间复杂度较高,是 O ( n 3 ) O(n^3) O(n3)

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

VNGE和FINGER的代码如下。

代码

# Name: VNGE
# Author: Reacubeth
# Time: 2021/1/25 16:01
# Mail: noverfitting@gmail.com
# Site: www.omegaxyz.com
# *_*coding:utf-8 *_*
import time
import numpy as np
from scipy.sparse.linalg.eigen.arpack import eigsh
def normalized_laplacian(adj_matrix):
nodes_degree = np.sum(adj_matrix, axis=1)
nodes_degree_sqrt = 1/np.sqrt(nodes_degree)
degree_matrix = np.diag(nodes_degree_sqrt)
eye_matrix = np.eye(adj_matrix.shape[0])
return eye_matrix - degree_matrix * adj_matrix * degree_matrix
def unnormalized_laplacian(adj_matrix):
nodes_degree = np.sum(adj_matrix, axis=1)
degree_matrix = np.diag(nodes_degree)
return degree_matrix - adj_matrix
def VNGE_exact(adj_matrix):
start = time.time()
nodes_degree = np.sum(adj_matrix, axis=1)
c = 1.0 / np.sum(nodes_degree)
laplacian_matrix = c * unnormalized_laplacian(adj_matrix)
eigenvalues, _ = np.linalg.eig(laplacian_matrix)
eigenvalues[eigenvalues < 0] = 0
pos = eigenvalues > 0
H_vn = - np.sum(eigenvalues[pos] * np.log2(eigenvalues[pos]))
print('H_vn exact:', H_vn)
print('Time:', time.time() - start)
def VNGE_FINGER(adj_matrix):
start = time.time()
nodes_degree = np.sum(adj_matrix, axis=1)
c = 1.0 / np.sum(nodes_degree)
edge_weights = 1.0 * adj_matrix[np.nonzero(adj_matrix)]
approx = 1.0 - np.square(c) * (np.sum(np.square(nodes_degree)) + np.sum(np.square(edge_weights)))
laplacian_matrix = unnormalized_laplacian(adj_matrix)
'''
eigenvalues, _ = np.linalg.eig(laplacian_matrix)
eig_max = c * max(eigenvalues)
'''
eig_max, _ = eigsh(laplacian_matrix, 1, which='LM')
eig_max = eig_max[0] * c
H_vn = - approx * np.log2(eig_max)
print('H_vn approx:', H_vn)
print('Time:', time.time() - start)
nodes_num = 3000
sparsity = 0.01
tmp_m = np.random.uniform(0, 1, (nodes_num, nodes_num))
pos1 = tmp_m > sparsity
pos2 = tmp_m <= sparsity
tmp_m[pos1] = 0
tmp_m[pos2] = 1
tmp_m = np.triu(tmp_m)
adj_m = tmp_m + np.transpose(tmp_m)
VNGE_exact(adj_m)
VNGE_FINGER(adj_m)

结果

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
网站所有代码采用Apache 2.0授权
网站文章采用知识共享许可协议BY-NC-SA4.0授权
2021 • OmegaXYZ-版权所有 转载请注明出处

版权声明
本文为[Reacubeth]所创,转载请带上原文链接,感谢
https://blog.csdn.net/xyisv/article/details/113177954

  1. Python notes: List
  2. Translation: practical Python Programming 02_ 03_ Formatting
  3. Python中的四种队列(queue)、堆(heap)
  4. Side effects of Python mutable types as default parameters of functions
  5. This is the best Python tutorial I've ever seen: ten minutes to get to know python
  6. 使用python编写量子线路打印的简单项目,并使用Sphinx自动化生成API文档
  7. Python happy enemy: crawler and anti crawler with a solution to give you New Year
  8. 使用python编写量子线路打印的简单项目,并使用Sphinx自动化生成API文档
  9. When writing python, you will encounter the following error: modulenotfounderror: no module named ' email.mime '; 'email' is not a package
  10. Python class call and private and public property method call
  11. Proprietary methods for Python classes
  12. Foundation of Python: number string and list
  13. Foundation of Python: number string and list
  14. Foundation of Python: number string and list
  15. 华为 Python网络自动化
  16. Python Cannot open E:\Python36\Scripts\pip-script.py
  17. Peeping into the future is not a dream, python data analysis is easy to achieve
  18. The practical skills summed up by Alibaba and Huawei Python engineers, only you haven't seen them yet?
  19. Sour! See the Python programmers on the tiktok get the pay slip...
  20. Foundation of Python: number string and list
  21. Python installation tutorial
  22. Python installation tutorial
  23. This article will familiarize you with the transformation process of Python - > Cafe - > om model
  24. Four kinds of queues and heaps in Python
  25. Using Python to write a simple project of quantum circuit printing, and using Sphinx to automatically generate API documents
  26. Using Python to write a simple project of quantum circuit printing, and using Sphinx to automatically generate API documents
  27. Huawei Python Network Automation
  28. Python Cannot open E:\Python36\Scripts\pip- script.py
  29. 找不到Python问题解决
  30. PHP和Python哪个更有市场前景?我学的是PHP
  31. Python problem resolution not found
  32. Which has more market prospects, PHP or Python? I studied PHP
  33. Foundation of Python: number string and list
  34. python 编码问题之终极解决
  35. The ultimate solution to the problem of Python coding
  36. 能取值亦能赋值的Python切片
  37. Python slice with value and value
  38. 能取值亦能赋值的Python切片
  39. Python slice with value and value
  40. python 异常处理
  41. Python exception handling
  42. python 异常处理
  43. Python exception handling
  44. Orca: 基于DolphinDB的分布式pandas接口
  45. Orca: distributed panda interface based on dolphin DB
  46. 5个无聊Python程序,用Python整蛊你的朋友们吧
  47. Five boring Python programs, trick your friends with Python
  48. python进阶训练营
  49. Python advanced training camp
  50. 【免费】0基础也能轻松学的Python训练营来啦,限时抢位中!
  51. [free] Python training camp, which is easy to learn, is here. It's time to grab a place!
  52. 手把手教你把Python应用到实际开发 不再空谈语法
  53. 全面系统Python3.8入门+进阶 (程序员必备第二语言)
  54. Hand in hand to teach you how to apply Python to practical development
  55. Comprehensive system introduction to Python 3.8 + Advanced
  56. Python语言的排序算法有哪些?Python学习班!
  57. Python language sorting algorithm what? Python classes!
  58. Java、JavaScript、C、C++、PHP、Python都是用来开发什么?
  59. 为什么学习Python?什么途径学习Python合适?
  60. What are Java, JavaScript, C, C + +, PHP and python used to develop?