Premium
Sublinear Time Force Computation for Big Complex Network Visualization
Author(s) -
Meidiana Amyra,
Hong SeokHee,
Torkel Marnijati,
Cai Shijun,
Eades Peter
Publication year - 2020
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.14003
Subject(s) - sublinear function , computation , initialization , sampling (signal processing) , computer science , visualization , vertex (graph theory) , algorithm , spanning tree , theoretical computer science , mathematics , discrete mathematics , artificial intelligence , graph , computer vision , filter (signal processing) , programming language
In this paper, we present a new framework for sublinear time force computation for visualization of big complex graphs. Our algorithm is based on the sampling of vertices for computing repulsion forces and edge sparsification for attraction force computation. More specifically, for vertex sampling, we present three types of sampling algorithms, including random sampling, geometric sampling, and combinatorial sampling, to reduce the repulsion force computation to sublinear in the number of vertices. We utilize a spectral sparsification approach to reduce the number of attraction force computations to sublinear in the number of edges for dense graphs. We also present a smart initialization method based on radial tree drawing of the BFS spanning tree rooted at the center. Experiments show that our new sublinear time force computation algorithms run quite fast, while producing good visualization of large and complex networks, with significant improvements in quality metrics such as shape‐based and edge crossing metrics.