Sublinear Time Force Computation for Big Complex Network Visualization

Loading...
Thumbnail Image
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and John Wiley & Sons Ltd.
Abstract
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.
Description

        
@article{
10.1111:cgf.14003
, journal = {Computer Graphics Forum}, title = {{
Sublinear Time Force Computation for Big Complex Network Visualization
}}, author = {
Meidiana, Amyra
and
Hong, Seok-Hee
and
Torkel, Marnijati
and
Cai, Shijun
and
Eades, Peter
}, year = {
2020
}, publisher = {
The Eurographics Association and John Wiley & Sons Ltd.
}, ISSN = {
1467-8659
}, DOI = {
10.1111/cgf.14003
} }
Citation
Collections