Force-directed graph layouts revisited: a new force
based on the t-Distribution

Fahai Zhong1     Mingliang Xue1     Jian Zhang2    
Fan Zhang3     Rui Ban4     Oliver Deussen5     Yunhai Wang1    

1Shandong University     2CNIC     3Shandong Technology and Business University     4CITC     5University of Konstanz

Accepted by IEEE Transactions on Visualization and Computer Graphics

Figure 1: Fig. 1. Comparison of our technique (t-FDP) with standard force-directed placement (FDP) [1] and tsNET [2], a state-of-the-art neighborhood embedding-based approach on a labeled co-author network by summarizing the normalized Euclidean distances of graph nodes in layout space with violin plots shown in the bottom of (a,b,c). While FDP places nodes close by that have large graph distances (the red box on the violin plots in a), tsNET avoids this to some extent (the red box on the violin plots in b) but often keeps nodes with small graph distances far from each other (the pink box on the violin plots in b). t-FDP in (c) is able to reach both, short layout distances for nearby points in data space and large ones for distant data points. Therefore it separates all eight classes clearly, while the other methods mix them in part. Two example neighborhoods show this: in (a) the neighbours of V1 do not have connections to V1 and the graph neighbours of V2 are mostly far away. tsNET is better in keeping the local neighborhood of V1, but the neighborhood of V2 has large graph distances. Both cases have a better neighborhood preservation with t-FDP.

Abstract:

In this paper, we propose the t-FDP model, a force-directed placement method based on a novel bounded short-range force (t-force) defined by Student’s t-distribution. Our formulation is flexible, exerts limited repulsive forces for nearby nodes and can be adapted separately in its short- and long-range effects. Using such forces in force-directed graph layouts yields better neighborhood preservation than current methods, while maintaining low stress errors. Our efficient implementation using a Fast Fourier Transform is one order of magnitude faster than state-of-the-art methods and two orders faster on the GPU, enabling us to perform parameter tuning by globally and locally adjusting the t-force in real-time for complex graphs. We demonstrate the quality of our approach by numerical evaluation against state-of-the-art approaches and extensions for interactive exploration.

Online Demo: t-fdp.github.io




Source Code: github.com/Ideas-Laboratory/t-fdp




Video:

Results:





Figure 1: Computation time of five different implementations of our t-FDP model in comparison to five other methods, which can process all datasets.



Figure 2: Heatmaps with a color-blind friendly pink-to-green colormap are used to present the values of SE (a), NP1 (b), and NP2 (c) for layouts generated by ten layout methods on 50 datasets, where the empty cell indicates the graph is too large to be processed by the corresponding layout method. Each row represents a dataset, and each column a layout method. All rows are colored relatively with regard to best and worst value.



Figure 3: Layouts by seven methods for the four data sets: cluster (top row), bcspwr07 (second row), 3elt (third row), and eva(bottom row). t-FDP shows a good ability to highlight clusters, at the same time a good mixture between local and global structures for bcspwr07 and a good unfolding for 3elt.



Figure 4: Refining t-FDP graph layouts by applying a large repulsive force (a), and a repulsive force with shorter range (b), and locally changing attractive and repulsive forces (c). These result in uniform distributed local neighborhoods (a), major clusters (b), and fisheye views (c).



Materials:





1 1
Paper (19.8M) Supp. (54.1M)

Acknowledgements:

The authors like to thank the anonymous reviewers for their valuable input, this work was supported by the grants of the National Key Research & Development Plan of China (2019YFB1704201) and NSFC (62132017, 62141217), as well as by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - EXC 2117 - 422037984.