Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations

Hayoung Choi; Jinglian He; Hang Hu; Yuanming Shi

doi:10.1016/j.laa.2019.09.031

Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations

Hayoung Choi, Jinglian He, Hang Hu, Yuanming Shi

ShanghaiTech University

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	127-146
Number of pages	20
Journal	Linear Algebra and Its Applications
Volume	585
DOIs	https://doi.org/10.1016/j.laa.2019.09.031
State	Published - 15 Jan 2020

Keywords

Density matrix
Graph dissimilarity
Von Neumann entropy
Von Neumann graph entropy

Access to Document

10.1016/j.laa.2019.09.031

Cite this

@article{cc1c39740add451db64d07951b22121a,

title = "Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations",

abstract = "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.",

keywords = "Density matrix, Graph dissimilarity, Von Neumann entropy, Von Neumann graph entropy",

author = "Hayoung Choi and Jinglian He and Hang Hu and Yuanming Shi",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",

year = "2020",

month = jan,

day = "15",

doi = "10.1016/j.laa.2019.09.031",

language = "English",

volume = "585",

pages = "127--146",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations

AU - Choi, Hayoung

AU - He, Jinglian

AU - Hu, Hang

AU - Shi, Yuanming

PY - 2020/1/15

Y1 - 2020/1/15

N2 - 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.

AB - 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.

KW - Density matrix

KW - Graph dissimilarity

KW - Von Neumann entropy

KW - Von Neumann graph entropy

UR - http://www.scopus.com/inward/record.url?scp=85072987877&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2019.09.031

DO - 10.1016/j.laa.2019.09.031

M3 - Article

AN - SCOPUS:85072987877

SN - 0024-3795

VL - 585

SP - 127

EP - 146

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this