On the von Neumann entropy of graphs

Minello，Giorgia1; Rossi，Luca2,3; Torsello，Andrea1

2019-08-01

10.1093/comnet/cny028

Journal of Complex Networks   影响因子和分区

2051-1310

2051-1329

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 article, 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; and (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.

Graph entropy

EI ; ESCI

英语

通讯

Mathematics

Mathematics, Interdisciplinary Applications

WOS:000481609800002

Oxford University Press

20200908240219

Complex networks ; Entropy ; Graph structures ; Laplace transforms ; Pattern recognition ; Quantum theory

Thermodynamics:641.1 ; Computer Systems and Equipment:722 ; Mathematical Transformations:921.3 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Quantum Theory; Quantum Mechanics:931.4

2-s2.0-85081096761

Scopus

1.Dipartimento di Scienze Ambientali,,Informatica e Statistica,Università Ca’ Foscari Venezia,Venezia Mestre,via Torino 155,30170,Italy
2.Department of Computer Science and Engineering,Southern University of Science and Technology,Nanshan District, Shenzhen,518055,China
3.School of Engineering and Applied Science,Aston University,Birmingham,Aston Triangle,B4 7ET,United Kingdom

Minello，Giorgia,Rossi，Luca,Torsello，Andrea. On the von Neumann entropy of graphs[J]. Journal of Complex Networks,2019,7(4):491-514.

Minello，Giorgia,Rossi，Luca,&Torsello，Andrea.(2019).On the von Neumann entropy of graphs.Journal of Complex Networks,7(4),491-514.

Minello，Giorgia,et al."On the von Neumann entropy of graphs".Journal of Complex Networks 7.4(2019):491-514.