New Quality Metrics for Connectivity-faithful Sampling and Drawing of Dynamic Graphs

We present new metrics and algorithms for connectivity-faithful visualization for dynamic graphs. We first present the SCQ (Sampling Change Quality) framework to evaluate dynamic graph sampling, based on the popular sampling quality metrics for the sampling of static graphs. We introduce the $S C Q_{C L O S E}$ metric as a specific instance of the framework, based on closeness centrality. We next introduce the PCQ (Proxy Change Quality) framework for evaluating the proxy distance change faithfulness of the visualization of dynamic graph sampling. More specifically, we introduce the PDCQ (Proxy Distance Change Quality) metric for proxy distance change faithfulness, i.e., how faithfully the ground-truth change in the shortest path distances of the original dynamic graphs is displayed as the geometric change in Euclidean distances in the drawing of the dynamic graph samples. Finally, we present a dynamic graph sampling algorithm for preserving the connectivity structures of the original dynamic graphs, called DCFNI (Dynamic Connectivity-Faithful NI), based on the well-known NI (Nagamochi-Ibaraki) algorithm for computing a connectivity-faithful sparsification. Extensive experiments on DCFNI, through comparison with the state-of-the-art DSS (Dynamic Spectral Sparsification) which outperforms random sampling methods, demonstrate the effectiveness of DCFNI over DSS: $53 \%$ higher $S C Q_{C L O S E}$ and $13 \%$ higher PDCQ on average, and better preserving the global connectivity of dynamic graphs on visual comparison.