Drawing Big Graphs using Spectral Sparsification

2017/08/29 by Eades, Peter, Nguyen, Quan, Hong, Seok-Hee · 3 citations
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)

paper · doi:10.48550/arxiv.1708.08659

Abstract

Spectral sparsification is a general technique developed by Spielman et al. to reduce the number of edges in a graph while retaining its structural properties. We investigate the use of spectral sparsification to produce good visual representations of big graphs. We evaluate spectral sparsification approaches on real-world and synthetic graphs. We show that spectral sparsifiers are more effective than random edge sampling. Our results lead to guidelines for using spectral sparsification in big graph visualization.

Cited by

• Graph Drawing Stress Model with Resistance Distances
• SS-GUMAP, SL-GUMAP, SSSL-GUMAP: Fast UMAP Algorithms for Large Graph Drawing
• Planar Stories of Graph Drawings: Algorithms and Experiments

Related

• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization
• Spectral Sparsification of Graphs
• GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis
• Similarity-Aware Spectral Sparsification by Edge Filtering