Spectrum-preserving sparsification for visualization of big graphs

Martin Imre, Jun Tao, Yongyu Wang, Zhiqiang Zhao, Zhuo Feng, Chaoli Wang

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)89-102
Number of pages14
JournalComputers and Graphics (Pergamon)
Volume87
DOIs
StatePublished - Apr 2020

Keywords

  • Big graph visualization
  • Edge bundling
  • Node reduction
  • Spectral clustering
  • Spectral graph sparsification

Fingerprint

Dive into the research topics of 'Spectrum-preserving sparsification for visualization of big graphs'. Together they form a unique fingerprint.

Cite this