On the von Neumann entropy of graphs
From MaRDI portal
Abstract: The von Neumann entropy of a graph is a spectral complexity measure that has recently found applications in complex networks analysis and pattern recognition. Two variants of the von Neumann entropy exist based on the graph Laplacian and normalized graph Laplacian, respectively. Due to its computational complexity, previous works have proposed to approximate the von Neumann entropy, effectively reducing it to the computation of simple node degree statistics. Unfortunately, a number of issues surrounding the von Neumann entropy remain unsolved to date, including the interpretation of this spectral measure in terms of structural patterns, understanding the relation between its two variants, and evaluating the quality of the corresponding approximations. In this paper we aim to answer these questions by first analysing and comparing the quadratic approximations of the two variants and then performing an extensive set of experiments on both synthetic and real-world graphs. We find that 1) the two entropies lead to the emergence of similar structures, but with some significant differences; 2) the correlation between them ranges from weakly positive to strongly negative, depending on the topology of the underlying graph; 3) the quadratic approximations fail to capture the presence of non-trivial structural patterns that seem to influence the value of the exact entropies; 4) the quality of the approximations, as well as which variant of the von Neumann entropy is better approximated, depends on the topology of the underlying graph.
Recommendations
- Entropy versus heterogeneity for graphs
- Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations
- On the von Neumann entropy of a graph
- Approximations for the von Neumann and Rényi entropies of graphs with circulant type Laplacians
- Approximations for von Neumann and Rényi entropies of graphs using the Euler-Maclaurin formula
Cited in
(27)- Approximations for von Neumann and Rényi entropies of graphs using the Euler-Maclaurin formula
- On the von Neumann entropy of a graph
- Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs
- Allometric scaling of von Neumann entropy in animal connectomes and its evolutionary aspect
- Notes on the values of volume entropy of graphs
- Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations
- Approximations for the von Neumann and Rényi entropies of graphs with circulant type Laplacians
- Perfection, imperfection, and graph entropy
- Entropy versus heterogeneity for graphs
- Graphs that Split Entropies
- The von Neumann Theil index: characterizing graph centralization using the von Neumann index
- scientific article; zbMATH DE number 1092008 (Why is no real title available?)
- Recovering Set Systems and Graph Entropy
- On the possible values of the entropy of undirected graphs
- Graph properties, graph limits, and entropy
- Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
- scientific article; zbMATH DE number 891075 (Why is no real title available?)
- Entropy of Digraphs and Infinite Networks
- Quasi-graphs, zero entropy and measures with discrete spectrum
- scientific article; zbMATH DE number 7410277 (Why is no real title available?)
- scientific article; zbMATH DE number 7410337 (Why is no real title available?)
- On the Shannon entropy of the number of vertices with zero in-degree in randomly oriented hypergraphs
- Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
- A note on the von Neumann entropy of random graphs
- Complex quantum networks: a topical review
- Laplacian spectral metrics of some graph operations
- An entropic proof of cutoff on Ramanujan graphs
This page was built for publication: On the von Neumann entropy of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958767)
