2018/11/12 by Hayoung Choi, Jinglian He, Choi, Hayoung +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Bioinformatics and Genomic Networks #Complex Network Analysis Techniques #Data Analysis #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Physical sciences #Information Theory (cs.IT) #Signal Processing (eess.SP) #Social and Information Networks (cs.SI) #Statistics and Probability (physics.data-an) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1811.11087
openalex publication_date 2018/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The von Neumann graph entropy (VNGE) can be used as a measure of graph complexity, which can be the measure of information divergence and distance between graphs. However, computing VNGE is extensively demanding for a large-scale graph. We propose novel quadratic approximations for fast computing VNGE. Various inequalities for error between the quadratic approximations and the exact VNGE are found. Our methods reduce the cubic complexity of VNGE to linear complexity. Computational simulations on random graph models and various real network datasets demonstrate superior performance.