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)$, among $A$ It's a symmetric adjacency matrix . The degree matrix is defined as $D=diag(d_1,...,d_n)$, Then its Laplacian matrix is $L=D-A$. And the eigenvalues of the latter ${\lambda }_i$ It's called Laplacian spectrum . here ,$H_{vn}(G)$ Entropy of von Neumann graph （von Neumann graph entropy）.

$$H_{vn}(G)=-\sum _{i=1}^n(\frac{{\lambda }_i}{vol(G)}\log \frac{{\lambda }_i}{vol(G)})$$

The capacity of the graph is $vol(G)={\sum }_{i=1}^n{\lambda }_i=trace(L)$. Time complexity is high , yes $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
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