SNAP-tFDP: Massively Scalable Graph Layouts via Sparse Negative Sampling
Xin Chen, Shuowei Hou, Yifan Wang, Mingliang Xue, Zezheng Feng, Oliver Deussen, Weidong Huang, Yunhai Wang
Figure 1: Progressive community layouts of an Orkut network.
Abstract (Summary)
SNAP-tFDP accelerates force-directed graph drawing with sampled repulsion and degree-aware weighting. Bounded forces based on a t-distribution help distinguish tightly connected groups. Sampling around edges avoids expensive auxiliary structures, while a parallel update strategy reduces synchronization overhead. The evaluation compares layout quality, runtime, and memory use on large networks, including CPU and GPU implementations. The results demonstrate that sparse updates can retain useful neighborhood and community structure while handling graphs with millions of nodes.
Links
Figures
Figure 2: Comparing force models and weighting choices.
Figure 3: Balancing forces between nodes of different degrees.
Figure 4: Checking sampled optimization against the full objective.
Figure 5: How sampling frequency affects speed and quality.
Figure 6: Convergence and intermediate layouts during parallel execution.
Figure 7: Quality measurements across algorithms and datasets.
Figure 8: Aircraft-network layouts and execution times.
Figure 9: Quality and speed of parallel implementations.
Figure 10: Runtime comparisons including GPU implementations.
Figure 11: A layout of the large Friendster network.