Python implementation and approximate calculation of von Neumann graph entropy (vnge)

Reacubeth 2021-02-23 14:16:48
python implementation approximate calculation von


brief introduction

feng · Entropy of Neumann graph (VNGE) It is helpful to measure the information difference and distance between graphs in graph sequence .

Given the first undirected graph G = ( V , E , A ) G=(V, E, A) G=(V,E,A), among A A A It's a symmetric adjacency matrix . The degree matrix is defined as D = d i a g ( d 1 , . . . , d n ) D=diag(d_1,...,d_n) D=diag(d1,...,dn), Then its Laplacian matrix is L = D − A L=D-A L=DA. And the eigenvalues of the latter λ i \lambda_i λi It's called Laplacian spectrum . here , H v n ( G ) H_{vn}(G) Hvn(G) Entropy of von Neumann graph (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)

The capacity of the graph is 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). Time complexity is high , yes O ( n 3 ) O(n^3) O(n3).

I have provided. Python Version code to calculate VNGE. It should be noted that Chen et al FINGER [1] The approximate method of , This method will VNGE The cubic complexity of is reduced to the linear complexity of the number of nodes and edges .

VNGE and FINGER The code for is as follows .

Code

# 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)

result

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.

More content access omegaxyz.com
All code of the website adopts Apache 2.0 to grant authorization
The article of the website adopts the knowledge sharing license agreement BY-NC-SA4.0 to grant authorization
2021 • OmegaXYZ- copyright Reprint please indicate the source

版权声明
本文为[Reacubeth]所创,转载请带上原文链接,感谢
https://pythonmana.com/2021/02/20210223135548430Y.html

  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?