Clustering-based force-directed algorithms for 3D graph visualization
- PDF / 10,061,507 Bytes
- 62 Pages / 439.37 x 666.142 pts Page_size
- 6 Downloads / 201 Views
Clustering‑based force‑directed algorithms for 3D graph visualization Jiawei Lu1 · Yain‑Whar Si1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Force-directed algorithm is one of the most commonly used methods for visualization of 2D graphs. These algorithms can be applied to a plethora of applications such as data visualization, social network analysis, crypto-currency transactions, and wireless sensor networks. Due to their effectiveness in visualization of topological data, various force-directed algorithms for 2D graphs were proposed in recent years. Although force-directed algorithms for 2D graphs were extensively investigated in research community, the algorithms for 3D graph visualization were rarely reported in the literature. In this paper, we propose four novel clustering-based force-directed (CFD) algorithms for visualization of 3D graphs. By using clustering algorithms, we divide a large graph into many smaller graphs so that they can be effectively processed by force-directed algorithms. In addition, weights are also introduced to further enhance the calculation for clusters. The proposed CFD algorithms are tested on 3 datasets with varying numbers of nodes. The experimental results show that proposed algorithms can significantly reduce edge crossings in visualization of large 3D graphs. The results also reveal that CFD algorithms can also reduce Kamada and Kawai energy and standardized variance of edge lengths in 3D graph visualization. Keywords 3D graphs · Visualization · Clustering algorithm · Force-directed algorithm
* Yain‑Whar Si [email protected] Jiawei Lu [email protected] 1
Department of Computer and Information Science, University of Macau, Avenida da Universidade, Taipa, Macau, China
13
Vol.:(0123456789)
J. Lu, Y.-W. Si
1 Introduction With the advancement of Internet and social media, development of efficient methods for analyzing large-scale networks become increasingly important in data analytics and visualization community. In recent years, various types of algorithms related to visualization of social networks were proposed in the literature [1]. Among these algorithms, force-directed placement (FDP) algorithms have been widely used in visualization of networks [2]. In addition, FDP algorithms are also used in a plethora of applications such as data visualization, social network analysis, crypto-currency transactions, and wireless sensor networks. FDP algorithms evolve from the idea of “spring embedding” force-directed placement in which nodes can repel or attract other nodes that are connected to them by edges, effectively acting as springs [3]. Some of the well-known FDP algorithms include Fruchterman and Reingold (FR) [4] (which is based on the work of Eades [5]) and Kamada and Kawai (KK) [6]. However, due to the high computational cost, majority of these algorithms do not perform well when dealing with graphs that have more than 2000 vertices. Although force-directed algorithms for 2D graphs were extensively investigated in research co
Data Loading...
