Graph Layout Performance Comparisons of Force-Directed Algorithms

doi:10.23940/ijpe.18.01.p8.6776

Abstract

Abstract:

Due to force-directed 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’ pre-setting parameters. In addition, most aesthetics criteria of graph drawing conflict with each other. This study evaluated the performance measurements of four force-directed 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 force-directed algorithms selection based on users’ specific requirements.

Submitted on October 14, 2017; Revised on December 5, 2017; Accepted on December 20, 2017
References: 23

Jie Hua, Mao Lin Huang, and Guohua Wang. Graph Layout Performance Comparisons of Force-Directed Algorithms [J]. Int J Performability Eng, 2018, 14(1): 67-76.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References 0

	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 Force-Directed 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 Force-Directed 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 Force-Directed Placement,” Software Practice and Experience., vol. 21, no. 11, pp. 1129–1164, 1991.
	10. E. R. Gansner and S. C. North, “Improved Force-directed 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, 24-27 November 2017. iOS press. In Press.
	12. M. L. Huang, P. Eades, and J. Wang, “On-Line 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 Force-Directed 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 Force-Directed Graph Drawings by Making Compromises Between Aesthetics,” Proc. - 2010 IEEE Symp. Vis. Lang. Human-Centric 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 Force-Directed 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, “Force-directed 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.