TY - JOUR
T1 - Spectrum-preserving sparsification for visualization of big graphs
AU - Imre, Martin
AU - Tao, Jun
AU - Wang, Yongyu
AU - Zhao, Zhiqiang
AU - Feng, Zhuo
AU - Wang, Chaoli
N1 - Publisher Copyright:
© 2020 Elsevier Ltd
PY - 2020/4
Y1 - 2020/4
N2 - We present a novel spectrum-preserving sparsification algorithm for visualizing big graph data. Although spectral methods have many advantages, the high memory and computation costs due to the involved Laplacian eigenvalue problems could immediately hinder their applications in big graph analytics. In this paper, we introduce a practically efficient, nearly-linear time spectral sparsification algorithm for tackling real-world big graph data. Besides spectral sparsification, we further propose a node reduction scheme based on intrinsic spectral graph properties to allow more aggressive, level-of-detail simplification. To enable effective visual exploration of the resulting spectrally sparsified graphs, we implement spectral clustering and edge bundling. Our framework does not depend on a particular graph layout and can be integrated into different graph drawing algorithms. We experiment with publicly available graph data of different sizes and characteristics to demonstrate the efficiency and effectiveness of our approach. To further verify our solution, we quantitatively compare our method against different graph simplification solutions using a proxy quality metric and statistical properties of the graphs.
AB - We present a novel spectrum-preserving sparsification algorithm for visualizing big graph data. Although spectral methods have many advantages, the high memory and computation costs due to the involved Laplacian eigenvalue problems could immediately hinder their applications in big graph analytics. In this paper, we introduce a practically efficient, nearly-linear time spectral sparsification algorithm for tackling real-world big graph data. Besides spectral sparsification, we further propose a node reduction scheme based on intrinsic spectral graph properties to allow more aggressive, level-of-detail simplification. To enable effective visual exploration of the resulting spectrally sparsified graphs, we implement spectral clustering and edge bundling. Our framework does not depend on a particular graph layout and can be integrated into different graph drawing algorithms. We experiment with publicly available graph data of different sizes and characteristics to demonstrate the efficiency and effectiveness of our approach. To further verify our solution, we quantitatively compare our method against different graph simplification solutions using a proxy quality metric and statistical properties of the graphs.
KW - Big graph visualization
KW - Edge bundling
KW - Node reduction
KW - Spectral clustering
KW - Spectral graph sparsification
UR - http://www.scopus.com/inward/record.url?scp=85080888692&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85080888692&partnerID=8YFLogxK
U2 - 10.1016/j.cag.2020.02.004
DO - 10.1016/j.cag.2020.02.004
M3 - Article
AN - SCOPUS:85080888692
SN - 0097-8493
VL - 87
SP - 89
EP - 102
JO - Computers and Graphics (Pergamon)
JF - Computers and Graphics (Pergamon)
ER -