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) , among 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) , Then its Laplacian matrix is L = D − A L=D-A . And the eigenvalues of the latter λ i \lambda_i It's called Laplacian spectrum . here , H v n ( G ) H_{vn}(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)})

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) . Time complexity is high , yes O ( n 3 ) O(n^3) .

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
nodes_degree_sqrt = 1/np.sqrt(nodes_degree)
degree_matrix = np.diag(nodes_degree_sqrt)
return eye_matrix - degree_matrix * adj_matrix * degree_matrix
degree_matrix = np.diag(nodes_degree)
start = time.time()
c = 1.0 / np.sum(nodes_degree)
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)
start = time.time()
c = 1.0 / np.sum(nodes_degree)
approx = 1.0 - np.square(c) * (np.sum(np.square(nodes_degree)) + np.sum(np.square(edge_weights)))
'''
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)


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

https://pythonmana.com/2021/02/20210223135548430Y.html