Sublinear Time Force Computation for Big Complex Network Visualization

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,...

Full description

Saved in:
Bibliographic Details
Published in:Computer graphics forum 2020-06, Vol.39 (3), p.579-591
Main Authors: Meidiana, Amyra, Hong, Seok‐Hee, Torkel, Marnijati, Cai, Shijun, Eades, Peter
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Attraction
Combinatorial analysis
Computing time
Graph theory
Graphs
Random sampling
Visualization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0167-7055
1467-8659
DOI:10.1111/cgf.14003