請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88240完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 顏嗣鈞 | zh_TW |
| dc.contributor.advisor | Hsu-Chun Yen | en |
| dc.contributor.author | 黃翊哲 | zh_TW |
| dc.contributor.author | I-Che Huang | en |
| dc.date.accessioned | 2023-08-09T16:09:47Z | - |
| dc.date.available | 2023-11-09 | - |
| dc.date.copyright | 2023-08-09 | - |
| dc.date.issued | 2023 | - |
| dc.date.submitted | 2023-07-21 | - |
| dc.identifier.citation | [1] D. Archambault, H. Purchase, and B. Pinaud, “Animation, small multiples, and the effect of mental map preservation in dynamic graphs,” IEEE transactions on visualization and computer graphics, vol. 17, no. 4, pp. 539–552, 2010.
[2] D. Archambault and H. C. Purchase, “Can animation support the visualisation of dynamic graphs?” Information Sciences, vol. 330, pp. 495–509, 2016. [3] P. Simonetto, D. Archambault, and S. Kobourov, “Event-based dynamic graph visualisation,” IEEE Transactions on Visualization and Computer Graphics, vol. 26, no. 7, pp. 2373–2386, 2018. [4] T. M. Fruchterman and E. M. Reingold, “Graph drawing by force-directed placement,” Software: Practice and experience, vol. 21, no. 11, pp. 1129–1164, 1991. [5] D. Rafiei, “Effectively visualizing large networks through sampling,” in VIS5. IEEE Visualization, 2005. IEEE, 2005, pp. 375–382. [6] C. Walshaw, “A multilevel algorithm for force-directed graph drawing,” in Graph Drawing: 8th International Symposium, GD 2000 Colonial Williamsburg, VA, USA, September 20–23, 2000 Proceedings 8. Springer, 2001, pp. 171–182. [7] W. T. Tutte, “How to draw a graph,” Proceedings of the London Mathematical Society, vol. 3, no. 1, pp. 743–767, 1963. [8] Y. Wu, N. Cao, D. Archambault, Q. Shen, H. Qu, and W. Cui, “Evaluation of graph sampling: A visualization perspective,” IEEE transactions on visualization and computer graphics, vol. 23, no. 1, pp. 401–410, 2016. [9] T. Wang, Y. Chen, Z. Zhang, T. Xu, L. Jin, P. Hui, B. Deng, and X. Li, “Understanding graph sampling algorithms for social network analysis,” in 2011 31st international conference on distributed computing systems workshops. IEEE, 2011, pp. 123–128. [10] J. Leskovec and C. Faloutsos, “Sampling from large graphs,” in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006, pp. 631–636. [11] L. Lov´asz, “Random walks on graphs,” Combinatorics, Paul erdos is eighty, vol. 2, no. 1-46, p. 4, 1993. [12] S. Hachul and M. J¨unger, “Drawing large graphs with a potential-field-based multilevel algorithm,” in Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers 12. Springer, 2005, pp. 285–295. [13] A. Arleo, S. Miksch, and D. Archambault, “A multilevel approach for eventbased dynamic graph drawing,” in Eurographics/IEEE VGTC Conference on Visualization: Short Papers, 2021, pp. 103–107. [14] B. Bach, P. Dragicevic, D. Archambault, C. Hurter, and S. Carpendale, “A descriptive framework for temporal data visualizations based on generalized space-time cubes,” in Computer graphics forum, vol. 36, no. 6. Wiley Online Library, 2017, pp. 36–61. [15] A. Meidiana, S.-H. Hong, and P. Eades, “New quality metrics for dynamic graph drawing,” in Graph Drawing and Network Visualization: 28th International Symposium, GD 2020, Vancouver, BC, Canada, September 16–18, 2020, Revised Selected Papers 28. Springer, 2020, pp. 450–465. [16] M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proceedings of the national academy of sciences, vol. 105, no. 4, pp. 1118–1123, 2008. [17] D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, 1952. [18] Q. H. Nguyen, S.-H. Hong, P. Eades, and A. Meidiana, “Proxy graph: Visual quality metrics of big graph sampling,” IEEE transactions on visualization and computer graphics, vol. 23, no. 6, pp. 1600–1611, 2017. [19] Y. Hu, “Efficient, high-quality force-directed graph drawing,” Mathematica journal, vol. 10, no. 1, pp. 37–71, 2005. [20] P. Gajer and S. G. Kobourov, “Grip: Graph drawing with intelligent placement,” in Graph Drawing: 8th International Symposium, GD 2000 Colonial Williamsburg, VA, USA, September 20–23, 2000 Proceedings. Springer, 2002, pp. 222–228. [21] P. J. Rousseeuw, “Silhouettes: a graphical aid to the interpretation and validation of cluster analysis,” Journal of computational and applied mathematics, vol. 20, pp. 53–65, 1987. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88240 | - |
| dc.description.abstract | 資料視覺化在現實世界中的重要性與日俱增，而圖形繪製在描述各種元素之間的連接方面起著至關重要的作用。雖然靜態圖的視覺化已經得到廣泛研究，可以有效率地繪製高品質圖形佈局，但對於動態圖的需求仍不斷增長，如社群媒體、串流服務的資料分析等，尚待進一步的探索。時間是視覺化動態圖的一個重要因素，一般大都將資料切割成不同時間片段來繪製圖形。然而，並非所有的複雜網路都能在時間切片內得到良好定義。基於事件的動態圖繪製通過捕捉圖形中發生的事件序列，從事件的角度產生圖形佈局。但是在面對大型的複雜網路時，基於事件的圖形繪製演算法仍面臨耗時過長的挑戰。為了解決上述問題，在這篇論文中，我們採用了一種基於隨機遊走的方法來繪製基於事件的動態圖。我們利用隨機遊走方法產生圖採樣來增加輸入資料集的擴展性，並加入了多階層方法來大幅加速繪製圖形佈局所需的時間。此外，我們引入了一種新的指標來評估我們的方法。實驗結果顯示，我們的方法在繪製時間和其他多個指標方面優於原始演算法，並且成功地用圖採樣方法捕捉了圖形結構。 | zh_TW |
| dc.description.abstract | The significance of data visualization is increasing in the real world, and graph drawing plays a crucial role in depicting connections among various elements. While static graph visualization has been extensively studied and is efficient in creating quality graph layouts, the growing demand for analyzing real-time and streaming data requires further investigation. Time is an important factor in visualizing dynamic graphs, and the technique of dividing data into time slices is commonly employed in drawing dynamic graphs. Nevertheless, not all complex networks can be well-defined in fixed intervals. An event-based model for dynamic graphs has been proposed to solve the above problem. By capturing the sequence of events that result in modifications in the graph, this approach produces graph layouts from event-based perspective. However, large and complex graphs still pose a challenge to event-based graph drawing for consuming too much time to create graph layouts. To tackle this problem, we apply a random walk-based approach for drawing event-based dynamic graphs. We utilize the random walk graph sampling method along with a multi-level framework to the event-based dynamic graph drawing algorithm to improve the scalability of input dataset and reduce the time complexity when computing the graph layout. Besides, we introduce a new quality metric for event-based dynamic graph drawing. In the experiment results, our approach outperforms the original algorithm in drawing time and several other metrics, and successfully captures the graph structure with the sampling method. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-08-09T16:09:47Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2023-08-09T16:09:47Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Abstract i
List of Figures iv List of Tables v 1 Introduction 1 2 Related Work 5 2.1 Dynamic Graph Drawing . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Force-directed Graph Drawing . . . . . . . . . . . . . . . . . . . 6 2.3 Graph Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Multi-Level Framework . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 Event-based Dynamic Graph Model . . . . . . . . . . . . . . . . 10 2.6 Dynamic Graph Quality Metric . . . . . . . . . . . . . . . . . . . 12 3 A Random Walk-based Approach for Event-based Dynamic Graph Drawing 17 3.1 Graph Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Infomap Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Random Walk-based Approach . . . . . . . . . . . . . . . . . . . 19 4 Experimental Results 25 4.1 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Graph Sampling Metrics . . . . . . . . . . . . . . . . . . . . . . 26 4.3 Graph Layout Metrics . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Conclusion 39 References 41 | - |
| dc.language.iso | en | - |
| dc.subject | 基於事件之資料集 | zh_TW |
| dc.subject | 多階層力導向佈局演算法 | zh_TW |
| dc.subject | 圖採樣 | zh_TW |
| dc.subject | 動態圖繪製 | zh_TW |
| dc.subject | Dynamic graph drawing | en |
| dc.subject | Graph sampling | en |
| dc.subject | Event-based data | en |
| dc.subject | Multilevel force-directed algorithm | en |
| dc.title | 隨機遊走方法應用在基於事件之動態圖繪製 | zh_TW |
| dc.title | Event-based Dynamic Graph Drawing via Random Walk Sampling | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 111-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 郭斯彥;雷欽隆;黃士嘉 | zh_TW |
| dc.contributor.oralexamcommittee | Sy-Yen Kuo;Chin-Laung Lei;Shih-Chia Huang | en |
| dc.subject.keyword | 圖採樣,動態圖繪製,多階層力導向佈局演算法,基於事件之資料集, | zh_TW |
| dc.subject.keyword | Graph sampling,Dynamic graph drawing,Event-based data,Multilevel force-directed algorithm, | en |
| dc.relation.page | 43 | - |
| dc.identifier.doi | 10.6342/NTU202301808 | - |
| dc.rights.note | 未授權 | - |
| dc.date.accepted | 2023-07-24 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 電機工程學系 | - |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-111-2.pdf 未授權公開取用 | 5.01 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。