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

doi:10.1016/j.laa.2019.09.031

	Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations
	Choi, Hayoung 1; He, Jinglian2 ; Hu, Hang2 ; Shi, Yuanming2
	2020-01-15
发表期刊	LINEAR ALGEBRA AND ITS APPLICATIONS
ISSN	0024-3795
卷号	585 页码:127-146
发表状态	已发表
DOI	10.1016/j.laa.2019.09.031
摘要	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. © 2019 Elsevier Inc.
URL	查看原文
收录类别	EI ; SCIE ; SCI
资助项目	National Research Foundation of Korea[2019H1D3A1A01102728] ; National Natural Science Foundation of China[61601290]
出版者	Elsevier Inc.
EI入藏号	20194107518379
EI主题词	Complex networks ; Graph theory ; Quantum theory
EI分类号	Thermodynamics:641.1 ; Computer Systems and Equipment:722 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Quantum Theory; Quantum Mechanics:931.4
原始文献类型	Journal article (JA)
引用统计
文献类型	期刊论文
条目标识符	https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/87021
专题	信息科学与技术学院_硕士生信息科学与技术学院_PI研究组_石远明组信息科学与技术学院_本科生信息科学与技术学院_博士生
通讯作者	Choi, Hayoung
作者单位	1.Research Institute of Mathematics, Seoul National University, Korea, Republic of 2.School of Information Science and Technology, ShanghaiTech University, China
推荐引用方式 GB/T 7714	Choi, Hayoung,He, Jinglian,Hu, Hang,et al. Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations[J]. LINEAR ALGEBRA AND ITS APPLICATIONS,2020,585:127-146.
APA	Choi, Hayoung,He, Jinglian,Hu, Hang,&Shi, Yuanming.(2020).Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations.LINEAR ALGEBRA AND ITS APPLICATIONS,585,127-146.
MLA	Choi, Hayoung,et al."Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations".LINEAR ALGEBRA AND ITS APPLICATIONS 585(2020):127-146.