## 冯诺依曼图熵（VNGE）Python实现及近似计算

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

## 简介

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

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


## 结果

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.

2021 • OmegaXYZ-版权所有 转载请注明出处

https://blog.csdn.net/xyisv/article/details/113177954