DSS: Drawing Dynamic Graphs with Spectral Sparsification
Loading...
Date
2022
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
This paper presents DSS (Dynamic Spectral Sparsification), a sampling approach for drawing large and complex dynamic graphs which can preserve important structural properties of the original graph. Specifically, we present two variants: DSSI (Independent) which performs spectral sparsification independently on each dynamic graph time slice; and DSS-U (Union) which performs spectral sparsification on the union graph of all time slices. Moreover, for evaluation of dynamic graph drawing using sampling approach, we introduce two new metrics: DSQ (Dynamic Sampling Quality) to measure how faithfully the samples represent the ground truth change in the dynamic graph, and DSDQ (Dynamic Sampling Drawing Quality) to measure how faithfully the drawings of the sample represent the ground truth change. Experiments demonstrate that DSS significantly outperform random sampling on quality metrics and visual comparison. On average, DSS obtains over 80% (resp., 30%) better DSQ (resp., DSDQ) than random sampling, and visually better preserves the ground truth changes in dynamic graphs.
Description
@inproceedings{10.2312:evs.20221093,
booktitle = {EuroVis 2022 - Short Papers},
editor = {Agus, Marco and Aigner, Wolfgang and Hoellt, Thomas},
title = {{DSS: Drawing Dynamic Graphs with Spectral Sparsification}},
author = {Meidiana, Amyra and Hong, Seok-Hee and Pu, Yanyi and Lee, Justin and Eades, Peter and Seo, Jinwook},
year = {2022},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-184-7},
DOI = {10.2312/evs.20221093}
}