臺灣博碩士論文加值系統

本篇論文主要在探討當給定一張佈局演算法不明的圖結構視覺化圖片，在缺乏其他繪製相同圖結構但不同佈局演算法的結果來一起比較時，為了判斷優劣，能以本篇所提之方法做圖形繪製風格判定，進而推估此張佈局演算法不明的圖片所具有之美學特性。圖形繪製是一項研究多時的領域，現有的圖形佈局演算法通常不能優化所需的所有美學特性，因此在對這些眾多演算法所繪製出的結果做評估時，除了一些既定的美學指標計算外，常做的就是所謂肉眼直接觀察的人工判讀。但通常都是在給定幾種圖形佈局方法後，從複數張給定圖片做優劣的選擇，如果只單單就一張圖形繪製結果來看的話便無從對其有任何的判讀。本論文中提出了一種基於深度學習的方法，將大量預挑選的圖形佈局演算法所繪製出的圖片用於卷積神經網路分類架構的訓練。根據訓練之後的分類器用於分類各式圖形佈局演算法或圖形佈局演算法不明的資料，經分類測試後所呈現之美學性質結果，可發現類似風格的圖形佈局演算法會有近似的美學性質表現，而佈局法不明的圖片經由被分類後所推估之美學性質會大致與直接計算的數值結果相符。總而言之，本論文所提之方法是利用相似的佈局風格會被神經網路歸類於一類的性質，並藉由觀察分類後結果各自算出之美學指標的數值便能得知各類演算法的特性，之後拿著佈局方法不明的圖片就能以神經網路分類並找到相似風格的圖形佈局演算法進而得出其所擁有的美學特性。

We propose a method to determine some aesthetic properties of an image which is drawn by using unknown graph layout algorithms. Graph drawing has been studied for decades. There is no layout algorithm which can satisfy all of the important aesthetic properties for graph layouts. Therefore, when evaluating any of these algorithms, user study is the way to determine the performance. When conducting user study, people need to choose the best layout image from the results generated by selected layout algorithms. It is hard for users to determine whether an image drawn by an unknown layout algorithm performs good or not if there is no other layout image to compare with it. In this thesis, we propose a deep learning based method which is a convolutional neural network classifier trained by images drawn in selected graph drawing algorithms. After testing the model by the dataset composed of images drawn by unknown layout algorithms, we find the graph layout algorithms of similar styles have similar aesthetic properties, and the estimated aesthetic properties of the images drawn by unknown layout methods will nearly be consistent with the directly calculated numerical results. In summary, the method proposed in this thesis is to use the tendency that similar layout style will be classified into the same class by the neural network, and the characteristics of various algorithms can be learned by observing the values of the aesthetic indicators of the classification results. Our study shows that, given an image drawn by unknown layout methods, we can use neural networks to classify it and find a similar style of a graph drawing algorithm to obtain its aesthetic properties.

1 緒論 1
1.1 研究背景 1
1.1.1 圖結構視覺化 1
1.1.2 圖結構視覺化之美學性質 2
1.2 研究動機與方向 2
1.3 相關研究 3
1.3.1 圖結構繪製之美學性質研究 3
1.3.2 機器學習於圖結構繪製領域 3
1.4 章節概述 4
2 背景知識 5
2.1 圖結構佈局 5
2.1.1 力學模擬演算法 5
2.1.2 降維演算法 7
2.1.3 光譜演算法 8
2.2 美學性質 9
2.2.1 邊交叉之數量 10
2.2.2 邊長度之變異程度 10
2.2.3 相鄰邊的夾角 10
2.2.4 形狀導向之美觀 11
2.3 卷積神經網路 12
3 基於風格分析的圖結構美學評估方法 14
3.1 問題描述 14
3.2 資料集生成 15
3.2.1 圖結構資訊的生成 15
3.2.2 佈局結果的生成 16
3.3 提出之方法架構 17
3.3.1 架構及流程 17
3.3.2 結果的判讀 20
4 實驗結果與討論 21
4.1 不同數量圖結構佈局演算法之分類結果 21
4.1.1 分類FR和HDE 21
4.1.2 分類FR、HDE和Spec 21
4.1.3 分類FR、HDE、Spec和FA2 23
4.1.4 討論 23
4.2 以不同測試資料集來觀察分類結果 23
4.2.1 不特定生成之圖結構佈局測試結果 24
4.2.2 討論 26
4.3 相同佈局演算法在不同的參數設定上之分類結果 27
5 結論與展望 29
5.1 結論 29
5.2 未來展望 29
References 30

Helen Gibson, Joe Faith, and Paul Vickers, “A survey of two-dimensional graph layout techniques for information visualization,”Information Visualization, vol. 12, no. 3-4, pp. 324–357, 2013.
Thomas M. J. Fruchterman, and Edward M. Reingold, “Graph drawing by force-directed placement,”Software - Practice and Experience, vol. 21, no. 11, pp. 1129–1164, 1991.
David Harel, and Yehuda Koren, “Graph Drawing by High-Dimensional Embedding,”Journal of Graph Algorithms and Applications, vol. 8(2), pp. 195–214, 2003.
Y.Koren, “Drawing Graphs by Eigenvectors: Theory and Practice,”Computers and Mathematics With Applications, vol. 49(11), pp. 1867–1888, 2005.
Chris Bennett, Jody Ryall, Leo Spalteholz, and Amy Gooch, “The aesthetics of graph visualization,”Computational Aesthetics: Proceedings Eurographics Conference on Computational Aesthetics in Graphics, Visualization and Imaging, pp. 57–64, 2007.
Oh-Hyun Kwon, Tarik Crnovrsanin, and Kwan-Liu Ma, “What would a graph look like in this layout? A machine learning approach to large graph visualization,”IEEE Transactions on Visualization and Computer Graphics, vol. 24, no. 1, pp. 478–488, 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton, “Imagenet classification with deep convolutional neural networks,”Advances in Neural Information Processing Systems, pp. 1097–1105, 2012.
Helen C. Purchase, Jo-Anne Allder, and David A. Carrington, “Graph Layout Aesthetics in UML Diagrams: User Preferences,”Journal of Graph Algorithms and Applications, vol. 6(3), pp. 255–279, 2001.
H. C. Purchase, C. Pilcher, and B. Plimmer, “Graph Drawing Aesthetics—Created by Users, Not Algorithms,”IEEE Transactions on Visualization and Computer Graphics, vol. 18(1), pp. 81–92, 2011.
Helen C. Purchase, Beryl Plimmer, Rosemary Baker, and Christopher Pilcher, “Graph drawing aesthetics in user-sketched graph layouts,”Australasian User Interface Conference, pp. 80–88, 2009.
K. Marriott, H. Purchase, M. Wybrow, and C. Goncu, “Memorability of Visual Features in Network Diagrams,”IEEE Transactions on Visualization and Computer Graphics, vol. 18(12), pp. 2477–2485, 2012.
Weidong Huang, “Establishing aesthetics based on human graph reading behavior:two eye tracking studies,”Ubiquitous Computing, vol. 17(1), pp. 93–105, 2012.
Chun-Cheng Lin, Weidong Huang, Wan-Yu Liu, and Wen-Lin Chen, “Evaluating aesthetics for user-sketched layouts of symmetric graphs,”Journal of Visual Languages and Computing, vol. 48, pp. 123–133, 2018.
Weidong Huang, Peter Eades, Seok-Hee Hong, and Chun-Cheng Lin, “Improving Force-Directed Graph Drawings by Making Compromises Between Aesthetics,”Symposium on Visual Languages and Human-Centric Computing, pp. 176–183, 2010.
W. Huang, P. Eades, S.-H. Hong, and C.-C. Lin, “Improving multiple aesthetics produces better graph drawings,”Journal of Visual Languages and Computing, vol.24(4), pp. 262–272, 2013.
Weidong Huang, Mao Lin Huang, and Chun-Cheng Lin, “Evaluating overall quality of graph visualizations based on aesthetics aggregation,”Information Sciences, vol.330, pp. 444–454, 2016.
Yong Wang, Zhihua Jin, Qianwen Wang, Weiwei Cui, Tengfei Ma, and Huamin Qu,“DeepDrawing : A Deep Learning Approach to Graph Drawing,”IEEE Transactions on Visualization and Computer Graphics, vol. 26(1), pp. 676–686, 2019.
Oh-Hyun Kwon, and Kwan-Liu Ma, “A Deep Generative Model for Graph Layout,”IEEE Transactions on Visualization and Computer Graphics, vol. 26(1), pp. 665–675, 2019.
Felice De Luca, Md. Iqbal Hossain, and Stephen G. Kobourov, “Symmetry Detection and Classification in Drawings of Graphs,”Graph Drawing, pp. 499–513, 2019.
Md. Khaledur Rahman, and Ariful Azad, “Evaluating the Community Structures from Network Images Using Neural Networks,”International Conference on Complex Networks and Their Applications, pp. 866–878, 2019.
Moritz Klammler, Tamara Mchedlidze, and Alexey Pak, “Aesthetic Discrimination of Graph Layouts,”Graph Drawing, pp. 169–184, 2018.
Hammad Haleem, Yong Wang, Abishek Puri, Sahil Wadhwa, and Huamin Qu,“Evaluating the Readability of Force Directed Graph Layouts: A Deep Learning Approach,”IEEE Computer Graphics and Applications, vol. 39(4), pp. 40–53, 2019.
Stephen G. Kobourov, “Force-Directed Drawing Algorithms,”Handbook of Graph Drawing and Visualization. CRC, pp. 383–408, 2013.
Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis, “GraphDrawing: Algorithms for the Visualization of Graphs,“1998.
T. von Landesberger, A. Kuijper, T. Schreck, J. Kohlhammer, J. van Wijk, J.-D.Fekete, and D. Fellner, “Visual Analysis of Large Graphs: State-of-the-Art and Future Research Challenges,”Computer Graphics Forum, vol. 30(6), no. 1, pp.1719–1749, 2011.
Jacomy M, Venturini T, Heymann S, and Bastian M, “ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software,”PLoS ONE, vol. 9(6), pp. 1–18, 2014.
Jie Hua, Mao Lin Huang, and Guohua Wang, “Graph Layout Performance Comparisons of Force-Directed Algorithms,”International journal of perform ability engineering, vol. 14(1), p. 67, 2017.
Helen C. Purchase, “Metrics for Graph Drawing Aesthetics,”Journal of Visual Languages and Computing, vol. 13(5), pp. 501–516, 2002.
Steve Kieffer, Tim Dwyer, Kim Marriott, and Michael Wybrow, “HOLA: Human-like Orthogonal Network Layout,”IEEE Transactions on Visualization and Computer Graphics, vol. 2(1), pp. 349–258, 2016.
Stefan Hachul and Michael Jünger, “Large-Graph Layout Algorithms at Work: An Experimental Study,”Journal of Graph Algorithms and Applications, vol. 11(2), pp.345–369, 2007.
Peter Eades, Seok-Hee Hong, An Nguyen, and Karsten Klein, “Shape-Based Quality Metrics for Large Graph Visualization,”Journal of Graph Algorithms and Applications, vol. 21(1), pp. 29–53, 2016.
K. Ruben Gabriel, and Robert R. Sokal, “A New Statistical Approach to Geographic Variation Analysis,”Systematic Biology, vol. 18(3), pp. 259–278, 1969.
A. Lancichinetti, S. Fortunato, and F. Radicchi, “Benchmark graphs for testing community detection algorithms,”Physical Review E, vol. 78(4), p. 46110, 2008.