Graph Layout Performance Comparisons of ForceDirected Algorithms
Volume 14, Number 1, January 2018, pp. 6776 DOI: 10.23940/ijpe.18.01.p8.6776
Jie Hua^{a}, Mao Lin Huang^{a}, Guohua Wang^{b}
^{a}University of Technology Sydney, Sydney, 2007, Australia ^{b}South China University of Technology, Guangzhou, 510641, China
(Submitted on October 14, 2017; Revised on December 5, 2017; Accepted on December 20, 2017)
Abstract:
Due to forcedirected algorithms’ capabilities of producing aesthetically pleasing graph layouts, which follow metrics for graph drawing aesthetics, these layouts have become the most common methods in the practical data visualization area. However, evaluating the performance of relevant algorithms remains a challenge, since graph layout quality is largely relying on aspects such as human intuition, personal judgment and methods’ presetting parameters. In addition, most aesthetics criteria of graph drawing conflict with each other. This study evaluated the performance measurements of four forcedirected algorithms in terms of seven commonly applied aesthetic criteria based on practical raw data collected, and demonstrated the experimental framework. The early outcomes compared twenty final graph layouts and gave empirical evidences; the study may assist with future detailed forcedirected algorithms selection based on users’ specific requirements.
References: 23
1. E. N. Argyriou, M. A. Bekos, and A. Symvonis, “Maximizing the Total Resolution of Graphs,” Comput. J., vol. 56, no. 7, pp. 887–900, 2013. 2. F.J. Brandenburg, M. Himsolt, and C. Rohrer, “An Experimental Comparison of ForceDirected and Randomized Graph Drawing Algorithms,” Proc. Symp. Graph Draw. (GD 1995), pp. 76–87, 1996. 3. G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, “Algorithms for Drawing Graphs an Annotated Bibliography,” Comput. Geom. Theory Appl., vol. 4, pp. 235–282, 1994. 4. G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, “Graph Drawing: Algorithms for the Visualization of Graphs,” 1999. 5. G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu, “An Experimental Comparison of Four Graph Drawing Algorithms,” Comput. Geom., vol. 7, no. 5–6, pp. 303–325, 1997. 6. M. Bastian, S. Heymann, and M. Jacomy, (2009) “Gephi: An Open Source Software for Exploring and Manipulating Networks,” Third International AAAI Conference on Weblogs and Social Media. doi: 10.1136/qshc.2004.010033. 7. U. Brandes, M. Eiglsperger, I. Herman, M. Himsolt, and M. S. Marshall. “GraphML Progress Report: Structural Layer Proposal,” Proc. 9th Intl. Symp. Graph Drawing (GD ’01), LNCS 2265:501–512. Springer, 2001. 8. B. Finkel and R. Tamassia, “Curvilinear Graph Drawing Using the ForceDirected Method,” in the 12th International Symposium on Graph Drawing (GD’04), 2004, pp. 448–453. 9. T. M. J. Fruchterman and E. M. Reingold, “Graph Drawing by ForceDirected Placement,” Software Practice and Experience., vol. 21, no. 11, pp. 1129–1164, 1991. 10. E. R. Gansner and S. C. North, “Improved Forcedirected Layouts,” in Proceedings of Graph Drawing 98, 1998, pp. 364–373. 11. J. Hua, M.L. Huang, M. Zreika, and G.H. Wang, (2017). “Applying Data Visualization Techniques for Stock Relationship Analysis,” In The 3rd International Conference on Fuzzy Systems and Data Mining. Hualien, Taiwan, 2427 November 2017. iOS press. In Press. 12. M. L. Huang, P. Eades, and J. Wang, “OnLine Animated Visualization of Huge Graphs Using a Modified Spring Algorithm,” J. Vis. Lang. Comput., vol. 9, no. 6, pp. 623–645, 1998. 13. M. Huang, W. Huang, and C. Lin, “Evaluating ForceDirected Algorithms with a New Framework,” in the 27th ACM Symposium on Applied Computing (SAC’12), 2012, pp. 1030–1032. 14. S. Hachul and M. Jünge, “An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs,” in Proc. 13th Int’l Symp. Graph Drawing (GD ’05), 2005, pp. 235–250. 15. W. Huang, P. Eades, S. H. Hong, and C. C. Lin, “Improving ForceDirected Graph Drawings by Making Compromises Between Aesthetics,” Proc.  2010 IEEE Symp. Vis. Lang. HumanCentric Compute. VL/HCC 2010, pp. 176–183, 2010. 16. W. Huang, and M. Huang, “Exploring the Relative Importance of Number of Edge Crossings and Size of Crossing Angles: A Quantitative Perspective,” Int. J. Adv. Intell., vol. 3, no. 1, pp. 25–42, 2011. 17. Y. Hu, “Efficient and High Quality ForceDirected Graph Drawing,” Math. J., vol. 10, no. 1, pp. 37–71, 2005. 18. M. Jacomy, S. Heymann, T. Venturini, and M. Bastian, “Force Atlas 2, A Graph Layout Algorithm for Handy Network Visualization,” … Http//www. Medialab. Sci. Fr/ …, pp. 1–21, 2011. 19. S. G. Kobourov, “Forcedirected Drawing Algorithms,” Handb. Graph Draw. Vis. (Discrete Math. Its Appl., pp. 383–408, 2013. 20. S. G. Kobourov, S. Pupyrev, and B. Saket, “Are Crossings Important for Drawing Large Graphs?” Graph Draw., pp. 234–245, 2014. 21. A. Noack, “An Energy Model for Visual Graph Clustering,” Proc. 11th Int. Symp. Graph Draw. (GD 2003), LNCS 2912, pp. 425–436, 2003. 22. A. Noack, “Energy Models for Graph Clustering,” J. Graph Algorithms Appl. JGAA, vol. 11, no. 112, pp. 453–480, 2007. 23. M. Zreika, J. Hua, and G.H. Wang, “Applying Data Processing Method for Relationship Discovery in the Stock Market,” in the International Conference on Data Science and Business Analytics (ICDSBA 2017), 2017, Springer. In Press.
Please note : You will need Adobe Acrobat viewer to view the full articles.
