von Neumann Graph Entropy: Python Implementation

Introduction

The von Neumann graph entropy (VNGE) facilitates measurement of information divergence and distance between graphs in a graph sequence.

Given an undirected graph $G=(V, E, A)$, where $A$ is the symmetric weight matrix. The degree matrix is defined as $D=diag(d_1,...,d_n)$ and the Laplacian matrix is defined as $L=D-A$, its eigenvalues $\lambda_i$ are called Laplacian spectrum. Here, $H_{vn}(G)$ is called von Neumann graph entropy.

where the volume of a graph is $vol(G)=\sum_{i=1}^{n}\lambda_i=trace(L)$. The time complexity of calculating von Neumann graph entropy is $O(n^3)$.

I provide a Python version code to calculate VNGE. It should be noted that Chen. et al give an approximate method called FINGER[1] which reduces the cubic complexity of VNGE to linear complexity in the number of nodes and edges.

TheCodes of VNGE and FINGER are as follows.

Results

[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