臺灣博碩士論文加值系統

在這篇論文中，我們提出一個基於力導向演算法的多解析度的視覺化方式，並用圖形與階層化來表示動態的資料集合。考慮到人類視覺感官系統的侷限，抽取出最重要的資料、或是使用者設定的資料來表現出資訊是很合理的。為了能提升使用者辨識效率，限制物件的數量也是非常重要的。為了更平滑地表示動態graph的動畫效果，我們採用了類似果凍狀的元球的技術來模擬graph。在我們的系統中，將上千筆節點(資料)以及連結(關係)透過群組化與圖像化來顯示，好讓使用者更容易地辨認。我們的系統除了可以透過互動式2D/3D圖形介面並動態地顯示資訊的多階層結構以及資訊的趨勢，同時也可以顯示資料的細節以及摘要。更甚者，應用3D立體的技巧，如透視、陰影、聚焦的方法，可以提升使用者理解資料的效率。
在實驗中，我們展示了使用了我們的系統來瀏覽Google Plus所提供的網路言論。使用者可以透過隨著時間推移的動態圖以及互動式介面，來輕易的理解被公開的言論趨勢以及之間的關係。

In this paper, we propose a multi-resolution visualization approach based on a force-directed algorithm to graphically and hierarchically represent dynamic data sets. Considering the limitations of the human visual cognitive system, it is reasonable to extract the most important or user-specified information for representation. Furthermore, in order to improve the efficiency of human recognition, it is important to restrict the number of objects in a graph. To smoothly animate changes of a dynamic graph, we adopt a jelly-like metaball technique. Our system clusters and graphically represents thousands of nodes (data) and links (relationships) in a novel way that allows a user to recognize the information visually. Our system displays information in a hierarchical format and evolving trends are dynamically visualized through an interactive 2D/3D graphical interface while simultaneously summarizing and displaying data detail. Furthermore, user perception can be enhanced by adopting human 3D stereopsis skills such as perspective, chiaroscuro, and focusing methods.
Our system is demonstrated by exploring internet comments from Google Plus. Users can easily utilize the time-varying graph of public comments trends and their interrelationships over time through the interface.

TABLE OF CONTENTS
論文摘要 I
Abstract II
Table of Contents III
List of Figures IV
List of Tables VI
Introduction 1
1.1 Motivation 1
1.2 Research Goal 3
1.3 Dissertation organization 4
Related Works 5
2.1 Planar Graph 5
2.2 Visual Perception 6
2.3 Graph Clustering and Filtering Strategies 6
2.4 Hierarchical Structure 7
2.5 Metaballs 9
2.6 Dynamic Graph 10
2.7 Force-Directed Strategies 11
System Configuration 14
3.1 Data Analysis 14
3.2 Graph Construction 15
3.3 Visualization based on Metaballs 18
3.4 Common Interface 22
Implementation 24
Conclusions 45
References 47
Appendix Questionnaire 52
 
LIST OF FIGURES
Fig. 1.1. 6012 nodes and 39946 edges are in this graph. (bottom) a partial detail of this graph 2
Fig. 2.1. The complete bipartite graphK3, 3 and the complete graph K5 5
Fig. 2.2. Multiple data attributes on graph vertices using heat maps and multiple views 7
Fig. 2.3. The conceptual hierarchy of a social bookmarking system 8
Fig. 2.4. Clustered Graph 10
Fig. 2.5. Representation of the transformation from node-link graph to matrix 10
Fig. 2.6. The binary-stress model for drawing graphs 12
Fig. 3.1. System configuration 14
Fig. 3.2. Metaball graph. (60 nodes) 15
Fig. 3.3. Algorithm of clustering nodes into hierarchical structure 16
Fig. 3.4. Algorithm of allocating edges for internal nodes 17
Fig. 3.5. Metaballs splitting and merging 18
Fig. 3.6. The graph shows 7 balls of different colors. The left image shows the graph without a filter. The right image shows that unrelated groups are masked. 20
Fig. 3.7. Input keywords to highlight the related groups 20
Fig. 3.8. The graph shows 7 balls of different colors. The left image shows the graph without a filter. The middle image shows a graph using a red filter. The right image use pink filters. 21
Fig. 3.9. The image on the left shows a random graph without a filter. The image on the right uses a blue filter. 21
Fig. 3.10. Shadows represent the relative object placement in 3D space 22
Fig. 3.11. The HTML5 version, which can also be presented on tablet computers 23
Fig. 4.1. The graph shows the structure and relationships of a BBS thread. (1) shows the initial status of the graphs; (2) shows that more groups growth; (3) shows the final status of the graphs and related edges of the dark blue groups; (4) shows the final status without edges for display clarity. 25
Fig. 4.2. The top left shows the highest level of data, while the top right shows the second level. The bottom right is the most detailed level of grouping, and the bottom left shows the target node with all of its connected neighbors 27
Fig. 4.3. An abstract of a whole infograph. The thresholdV is 20 28
Fig. 4.4. Information detail at the lowest level 29
Fig. 4.5. Extend list item 2 to see more details of the comment 29
Fig. 4.6. Another result showing the abstract of the whole infograph, with a thresholdV of 8. The larger subgroup contains more nodes 30
Fig. 4.7. System displays of the relativity between different threads, along with their comments and groupings. Each group displays the number of nodes contained within 33
Fig. 4.8. System displays graph with cold-to-warm color map 34
Fig. 4.9. The viewpoint moves around the groups 35
Fig. 4.10. The links of the selected group 36
Fig. 4.11. Change the order of keywords by dragging 37
Fig. 4.12. The search interface in HTML5. Users can input the desired keywords into the search bar at the top. After searching through the comments, the graph shows relevant groups on the left and the contents of the groups on the right 38
Fig. 4.13.While the user presses and holds a circle, the relevant hints for organizing the keywords will be shown in the groups. The black outline around the circle means that it is currently selected 39
Fig. 4.14. Result graph. The black edge indicates abroad match with the two terms. The metaball link represents a phrase match with the two terms in (3) 40
Fig. 4.15. The search result of keywords “your copyright” SOPA 41
Fig. 4.16. Groups and searches kept sequentially. (1) Results for the search term "Google"; (2) The group "Google" is linked to the group “maps” by dragging; (3), Unnecessary groups are collapsed by clicking the “set” button; (4) The next result with the kept groups are shown. Note that the color and position of the kept groups are maintained 42
Fig. 4.17. The text-only system. The results do not contain any clue keywords 43
4.18. Average time taken to find the related answer in each system 44
 
LIST OF TABLES
Table 1. Gray circle functions 38
Table 2. Search questions and answers 43

1.G. Parker, G. Franck, and C. Ware, “Visualization of Large Nested Graphs in 3D: Navigation and Interaction,” J. Visual Languages and Computing, 1998, pp. 299-317.
2.M. L. Huang, “Information visualization of attributed relational data,” Proc. of the 2001 Asia-Pacific symposium on Information visualization, Vol. 9, 2001, pp. 143-149.
3.T. M. J. Fruchterman and E. M. Reingold, “Graph Drawing by Force-directed Placement”, Software-Practice & Experience, Vol. 21, No. 11, 1991, pp. 1129-1164.
4.Y. Koren and A. C¸ ivril, “The Binary Stress Model for Graph Drawing,” Proc. of the 16th International Symposium in Graph Drawing (GD’08), Vol. 5417, 2009, pp. 193-205.
5.H. Omote and K. Sugiyama, “Method for drawing intersecting clustered graphs and its application to web ontology language,” Proc. of the 2006 Asia-Pacific Symposium on Information Visualisation, Vol. 60, 2006, pp. 89-92.
6.A. Quigley and P. Eades, “FADE: Graph drawing, clustering and visual abstraction,” Proc. of the 8th International Symposium on Graph Drawing (GD ’00), 2001, pp. 197-210.
7.C. Walshaw, “A Multilevel Algorithm for Force-Directed Graph Drawing,” Springer-Verlag, 2003, pp. 171-182.
8.C. Muelder and K.-L. Ma, “A Treemap Based Method for Rapid Layout of Large Graphs,” PacificVis'08, 2008, pp. 231-238.
9.M. Balzer and O. Deussen, “Level-of-Detail Visualization of Clustered Graph Layouts,” 6th International Asia-Pacific Symposium (APVIS’ 07), 2007, pp. 133-140.
10.Y.-H. Chan, K. Keeton, and K.-L. Ma, “Interactive Visual Analysis of Hierarchical Enterprise Data,” 12th IEEE International Conference on Commerce and Enterprise Computing, 2010, pp. 180-187.
11.J. Abello, F. v. Ham, and N. Krishnan, “ASK-GraphView: A Large Scale Graph Visualization System,” IEEE TVCG, Vol. 12, No. 5, 2006, pp. 669-676.
12.C. Friedrich and P. Eades, “Graph Drawing in Motion, Journal Graph Algorithms and Applications,” Vol. 6, No. 3, 2002, pp. 353-370.
13.C. Friedrich and M. E. Houle, “Graph Drawing in Motion II, Lecture Notes in Computer Science,” Vol. 2265, 2002, pp. 122-125.
14.C. Erten, P. J. Harding, S. G. Kobourov, K. Wampler, and G. Yee, “GraphAEL: Graph Animations with Evolving Layouts”, 11th Symposium on Graph Drawing (GD), 2003, pp. 98-110.
15.B. Tversky, J. B. Morrison, and M. Betrancourt, “Animation: can it facilitate?,” International journal of human-computer studies, Vol. 57, No. 4, 2002, pp. 247-262.
16.J. F. Blinn, “A Generalization of Algebraic Surface Drawing,” ACM Transactions on Graphics (TOG), Vol. 1, No. 3, 1982, pp. 235-256.
17.T. Nishita and E. Nakamae, “A Method for Displaying Metaballs by using Bzier Clipping,” Computer Graphics Forum, Vol. 13, 1994, pp. 271-280.
18.M.F. Porter, “Snowball: A language for stemming algorithms,” 2001. http://snowball.tartarus.org/texts/introduction.html
19.G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis, “Graph Drawing: Algorithms for the Visualization of Graphs,” Prentice Hall, 1998.
20.T. Nishizeki, N. Chiba, North-Holland, “Planar Graphs : Theory and Algorithms,” North-Holland, Amsterdam, 1988.
21.John M. Boyer and Wendy J. Myrvold, “On the Cutting Edge: Simplified O(n) Planarity by Edge Addition,” Journal of Graph Algorithms and Applications, Vol. 8, No. 3, 2004, pp. 241-273.
22.T. Kamada and S. Kawai, “An algorithm for drawing general undirected graphs,” Information Processing Letters archive, Vol. 31, No. 1, 1989, pp. 7-15.
23.D. Harel and Y. Koren, “A Fast Multi-Scale Method for Drawing Large Graphs,” Graph Drawing 2000, pp. 183-196.
24.Y. Hu, “Efficient, High-Quality Force-Directed Graph Drawing,” The Mathematica Journal 10, No. 1 (2006), pp. 37-71.
25.A. Noack, “Modularity clustering is force-directed layout,” presented at CoRR, 2008.
26.P. Saraiya, Peter Lee, and Chris North, “Visualization of Graphs with Associated Timeseries Data,” INFOVIS 2005, pp. 225-232.
27.H. Omote and K. Sugiyama, “Method for Drawing Intersecting Clustered Graphs and Its Application to Web Ontology Language,” Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation, Vol. 60, 2006, pp. 89-92.
28.Y. Jia, J. Hoberock, M. Garland, J. Hart, “On the Visualization of Social and other Scale-Free Networks,” IEEE Transactions on Visualization and Computer Graphics, Vol. 14, No. 6, 2008, pp. 1285-1292.
29.T. von Landesberger, A. Kuijper, T. Schreck, J. Kohlhammer, J.J. van Wijk, J.-D. Fekete, D.W. Fellner, “Visual Analysis of Large Graphs: State-of-the-Art and Future Research Challenges,” Computer Graphics Forum, Vol. 30, No. 6, 2011, pp. 1719-1749.
30.F. Reitz, M. Pohl, and S. Diehl, “Focused Animation of Dynamic Compound Graphs,” 13th International Conference Information Visualisation, 2009, pp. 679-684.
31.G. Kumar and M. Garland, “Visual Exploration of Complex Time-Varying Graphs,” IEEE Transactions on Visualization and Computer Graphics, Vol. 12, No. 5, 2006, pp. 805-812.
32.Y. Frishman and A. Tal “Dynamic Drawing of Clustered Graphs,” INFOVIS '04 Proceedings of the IEEE Symposium on Information Visualization, 2004, pp. 191-198.
33.P. Bourke, “Implicit surfaces,” http://paulbourke.net/geometry/implicitsurf/
34.D. Luebke, M. Reddy, J. Cohen, A. Varshney, B. Watson, and R. Huebner, “Level of Detail for 3D Graphics,” Morgan Kaufmann Publishers, 2002. ISBN: 1-55860-838-9.
35.T. K. Heok and D. Daman, “A review on level of detail,” in Proceedings of International Conference on Computer Graphics, Imaging and Visualization, 2004, pp. 70-75.
36.George A. Miller, “The Magic Number Seven, Plus or Minus Two: Some Limits on our Capacity for Processing Information,” Psychological Review, Vol. 63, No. 2, 1956, pp. 81-97.
37.C. Ware, “Information Visualization: Perception for Design,” Morgan Kaufmann Publishers, 2004. ISBN: 1558608192.
38.N. Henry, J.-D. Fekete, and M. J. McGuffin, “NodeTrix: A Hybrid Visualization of Social Networks,” IEEE Transactions on Visualization and Computer Graphics, Vol. 13, No. 6, 2007, pp. 1302-1309.
39.HTML5 differences from HTML4, http://www.w3.org/TR/2011/WD-html5-diff-20110405/
40.J. Abello and Y. Kotidis, “Hierarchical graph indexing,” Proceedings of the twelfth international conference on Information and knowledge management, 2003, pp. 453-460.
41.A. Clauset, C. Moore, and M. E. J. Newman, “Structural Inference of Hierarchies in Networks,” Proc. 23rd International Conference on Machine Learning (ICML), Workshop on Social Network Analysis, Pittsburgh PA, 2006.
42.A. Kohrs and B. Merialdo, “Clustering for Collaborative Filtering Applications,” In Computational Intelligence for Modelling, Control & Automation. IOS, 1999.
43.G. Busatto, H.-J. Kreowski, and S. Kuske, “Hierarchical Graph Transformation,” Journal of Computer and System Sciences, Vol. 64, No. 2, 2002, pp. 249-283.
44.G. Busatto, H.-J. Kreowski, and S. Kuske, “Abstract Hierarchical Graph Transformation,” Journal, Mathematical Structures in Computer Science archive ,Vol. 15, No. 4, 2005, pp. 773-819.
45.M. Grahl, A. Hotho, and G. Stumme, “Conceptual Clustering of Social Bookmarking Sites,” 7th International Conference on Knowledge Management, 2007, pp. 356-364.
46.A. Hotho, R. Jäschke, C. Schmitz, and G. Stumme, “FolkRank: A ranking algorithm for folksonomies,” Proc. of LWA. 2006, pp. 111-114.