Sublinear Time Force Computation for Big Complex Network Visualization

Simple item page
dc.contributor.authorMeidiana, Amyraen_US
dc.contributor.authorHong, Seok-Heeen_US
dc.contributor.authorTorkel, Marnijatien_US
dc.contributor.authorCai, Shijunen_US
dc.contributor.authorEades, Peteren_US
dc.contributor.editorViola, Ivan and Gleicher, Michael and Landesberger von Antburg, Tatianaen_US
dc.date.accessioned2020-05-24T13:01:58Z
dc.date.available2020-05-24T13:01:58Z
dc.date.issued2020
dc.description.abstractIn 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.en_US
dc.description.number3
dc.description.sectionheadersGraphs and Charts
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume39
dc.identifier.doi10.1111/cgf.14003
dc.identifier.issn1467-8659
dc.identifier.pages579-591
dc.identifier.urihttps://doi.org/10.1111/cgf.14003
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf14003
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.rightsAttribution 4.0 International License
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/]
dc.titleSublinear Time Force Computation for Big Complex Network Visualizationen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
v39i3pp579-591.pdf
Size:
13.58 MB
Format:
Adobe Portable Document Format
Download
Collections
39-Issue 3