Optimization of force-directed graph drawing for large data visualization : methods for reducing the convergence time, and improving the readability on force-directed graph drawing
- Publication Type:
- Thesis
- Issue Date:
- 2014
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 01front.pdf | contents and abstract | 1.06 MB | ||
| 02whole.pdf | thesis | 13.66 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
NO FULL TEXT AVAILABLE. This thesis contains 3rd party copyright material. ----- Force-directed graph drawing is a class of algorithms for drawing graphs in an aesthetically pleasing way. It is commonly used for relational data visualization; this method produces very good layout for graphs of medium size (normally within 100 vertices). However, the main disadvantage of this method is its high running time. A typical force-directed algorithm is in general considered to have a running time equivalent to O(n³), where n is the number of nodes of an input graph. This is related to the energy convergence problem in physics. Therefore, the traditional force-directed graph drawing algorithms are not suitable to deal with the large data visualization.
In this thesis, we proposed an optimized force-directed graph drawing method that can greatly reduce the convergence time in dealing with large data visualization. Particularly, we create a dummy clustered structure over the graph. We then divide the whole convergence process into two parts: 1) Interior convergence with clusters, 2) Exterior convergence of forces among clusters. It has been shown that the proposed combined process is faster in general than the traditional convergence process. Besides the reduction of convergence time, our algorithms also improve the readability (or quality) of force-directed graph layout simultaneously.
In our hybrid method, we applied a clustering concept which was from the data mining field, to help us to achieve the goals described in the paragraph above. As cluster analysis serves as a tool in data mining to gain insight into the distribution of data to observe characteristics of each cluster, and it has been adopted in our experiments, the final layouts may contribute in the large data visual analytics area.
We had conducted evaluations by comparing the performance of our new method with the traditional Force-directed algorithm. The results have proven our hypothesis that the new methods are more efficient than traditional methods and they are better in dealing with large graph drawings.
Please use this identifier to cite or link to this item: