Fast and Faithful Edge Bundling for Large and Complex Networks

Keywords

Edge bundling, Spectral sparsification, Faithfulness metrics

Abstract

Edge bundling reduces the visual complexity of drawings of dense graphs by clustering compatible edges. However, existing edge bundling methods often have high computational complexity, leading to scalability issues. This paper presents a new framework for fast edge bundling and faithfulness metrics for large and complex graphs using spectral sparsification, which sparsifies a graph G into a subgraph G' with O(nlogn) edges, preserving the spectrum of G. We first present a general framework, FEB (Fast Edge Bundling), utilizing spectral sparsification to improve the efficiency of existing bundling methods while maintaining a similar quality of bundling. We then present the FBQ (Fast Bundling Quality) framework for proxy bundle faithfulness metrics, to measure how FEB faithfully preserves the ground truth structure in the original edge bundling, with two variants, FBQ_JS (utilizing Jaccard Similarity) and FBQ_SQ (utilizing sampling quality metrics). Extensive experiments using various real-world networks demonstrate the efficiency of the FEB framework, with 61% runtime improvement over the original edge bundling methods without sparsification, while maintaining a similar quality by FBQ quality metrics and visual comparison.