請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88238
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 顏嗣鈞 | zh_TW |
dc.contributor.advisor | Hsu-Chun Yen | en |
dc.contributor.author | 鄭皓宇 | zh_TW |
dc.contributor.author | Hao-Yu Zheng | en |
dc.date.accessioned | 2023-08-09T16:09:12Z | - |
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 | [Bar82] Brian Andrew Barsky. The beta-spline: A local representation based on shape parameters and fundamental geometric measures. 1982.
[BBDW17] Fabian Beck, Michael Burch, Stephan Diehl, and Daniel Weiskopf. A taxonomy and survey of dynamic graph visualization. In Computer graphics forum, volume 36, pages 133–159. Wiley Online Library, 2017. [BM11] Ulrik Brandes and Martin Mader. A quantitative comparison of stress-minimization approaches for offline dynamic graph drawing. In International Symposium on Graph Drawing, pages 99–110. Springer, 2011. [CT65] James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):297–301, 1965. [CZQ+08] Weiwei Cui, Hong Zhou, Huamin Qu, Pak Chung Wong, and Xiaoming Li. Geometry-based edge clustering for graph visualization. IEEE transactions on visualization and computer graphics, 14(6):1277–1284, 2008. [EHP+11] Ozan Ersoy, Christophe Hurter, Fernando Paulovich, Gabriel Cantareiro, and Alex Telea. Skeleton-based edge bundling for graph visualization. IEEE transactions on visualization and computer graphics, 17(12):2364–2373, 2011. [Fie88] David A Field. Laplacian smoothing and delaunay triangulations. Communications in applied numerical methods, 4(6):709–712, 1988. [GHNS11] Emden R. Gansner, Yifan Hu, Stephen North, and Carlos Scheidegger. Multilevel agglomerative edge bundling for visualizing large graphs. In 2011 IEEE Pacific Visualization Symposium, pages 187–194, 2011. [HEF+13] Christophe Hurter, Ozan Ersoy, Sara Irina Fabrikant, Tijmen R Klein, and Alexandru C Telea. Bundled visualization of dynamic graph and trail data. IEEE transactions on visualization and computer graphics, 20(8):1141–1157, 2013. [HET12] Christophe Hurter, Ozan Ersoy, and Alexandru Telea. Graph bundling by kernel density estimation. In Computer graphics forum, volume 31, pages 865–874. Wiley Online Library, 2012. [HET13] Christophe Hurter, Ozan Ersoy, and Alexandru Telea. Smooth bundling of large streaming and sequence graphs. In 2013 IEEE Pacific Visualization Symposium (PacificVis), pages 41–48. IEEE, 2013. [Hol06] Danny Holten. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Transactions on visualization and computer graphics, 12(5):741–748, 2006. [HVW09] Danny Holten and Jarke J Van Wijk. Force-directed edge bundling for graph visualization. In Computer graphics forum, volume 28, pages 983–990. Wiley Online Library, 2009. [KWSS12] Wolfgang Kienreich, Ralph Wozelka, Vedran Sabol, and Christin Seifert. Graph visualization using hierarchical edge routing and bundling. In EuroVA@ EuroVis, 2012. [LBA10] Antoine Lambert, Romain Bourqui, and David Auber. Winding roads: Routing edges into bundles. In Computer graphics forum, volume 29, pages 853–862. Wiley Online Library, 2010. [LHT17a] Antoine Lhuillier, Christophe Hurter, and Alexandru Telea. Ffteb: Edge bundling of huge graphs by the fast fourier transform. In 2017 IEEE Pacific visualization symposium (PacificVis), pages 190–199. IEEE, 2017. [LHT17b] Antoine Lhuillier, Christophe Hurter, and Alexandru Telea. State of the art in edge and trail bundling techniques. In Computer Graphics Forum, volume 36, pages 619–645. Wiley Online Library, 2017. [NEH12a] Quan Nguyen, Peter Eades, and Seok-Hee Hong. On the faithfulness of graph visualizations. In International Symposium on Graph Drawing, pages 566–568. Springer, 2012. [NEH12b] Quan Nguyen, Peter Eades, and Seok-Hee Hong. Streameb: Stream edge bundling. In International Symposium on Graph Drawing, pages 400–413. Springer, 2012. [NHE11] Quan Nguyen, Seok-Hee Hong, and Peter Eades. Tgi-eb: A new framework for edge bundling integrating topology, geometry and importance. In International Symposium on Graph Drawing, pages 123–135. Springer, 2011. [PPP10] Helen C Purchase, Christopher Pilcher, and Beryl Plimmer. Graph drawing aesthetics—created by users, not algorithms. IEEE Transactions on Visualization and Computer Graphics, 18(1):81–92, 2010. [Pur97] Helen Purchase. Which aesthetic has the greatest effect on human understanding? In International Symposium on Graph Drawing, pages 248–261. Springer, 1997. [Pur02] Helen C Purchase. Metrics for graph drawing aesthetics. Journal of Visual Languages & Computing, 13(5):501–516, 2002. [Sag18] Ryosuke Saga. Validation of quantitative measures for edge bundling by comparing with human feeling. In EuroVis (Posters), pages 25–27, 2018. [Sta20] Stathis Kamperis. A gentle introduction to kernel density estimation, 2020. [Online; accessed Sep 27, 2022]. [Us08] Data Expo 2009: Airline on time data, 2008. [VDZCT16] Matthew Van Der Zwan, Valeriu Codreanu, and Alexandru Telea. Cubu: Universal real-time bundling for large graphs. IEEE transactions on visualization and computer graphics, 22(12):2550–2563, 2016. [WZLY18] Jieting Wu, Feiyu Zhu, Xin Liu, and Hongfeng Yu. An information-theoretic framework for evaluating edge bundling visualization. Entropy, 20(9):625, 2018. [WZZY17] Jieting Wu, Jianping Zeng, Feiyu Zhu, and Hongfeng Yu. Mlseb: Edge bundling using moving least squares approximation. In International Symposium on Graph Drawing and Network Visualization, pages 379–393. Springer, 2017. [YS17] Takafumi Yamashita and Ryosuke Saga. Cluster-based edge bundling based on a line graph. In International Conference on Information Visualization Theory and Applications, volume 4, pages 311–316. SCITEPRESS, 2017. [ZWHK16] Daniel Zielasko, Benjamin Weyers, Bernd Hentschel, and Torsten W Kuhlen. Interactive 3d force-directed edge bundling. In Computer graphics forum, volume 35, pages 51–60. Wiley Online Library, 2016. [ZYC+08] Hong Zhou, Xiaoru Yuan, Weiwei Cui, Huamin Qu, and Baoquan Chen. Energy-based hierarchical edge clustering of graphs. In 2008 ieee pacific visualization symposium, pages 55–61. IEEE, 2008. | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88238 | - |
dc.description.abstract | 束邊演算法是一種資料視覺化的技術,讓圖可以在不失去結構性意義的前提下增加圖的可讀性。束邊演算法作用的對象是由點與邊組成的網絡圖,且他達到上述所提到的目標的方法在於將圖上雜亂且無序的邊集合形成一個視覺上綑綁起來的邊束。
這篇論文提出了一個作用於動態圖上的束邊演算法,作用於動態圖與靜態圖本質上的區別在於動態圖在不同時間點的圖之間可能會差異過大,這導致作用後的結果可能會導致觀看者的疑惑或是矛盾。我們所提出的方法是基於更早提出的“核密度估計束邊演算法”,這個方法主要是在計算圖上邊的密度分佈,我們的方法則利用快速傅立葉轉換這個理論上消耗較少時間的演算法來取代它。 在測量階段,我們利用幾個標準去衡量我們與前面方法的品質差異,其中一個是我們從一個 dynamic layout 的衡量改編而來,測量的重點在於保留心智地圖(mental map)的程度與圖形變形程度和減少亂邊的轉換效率。 | zh_TW |
dc.description.abstract | Edge bundling is a visualization technique used to enhance the readability of node-link diagrams by grouping together edges that are visually close to each other while preserving the underlying structure of the graph. This technique is particularly useful for reducing visual clutter in complex graphs.
In this thesis, we present an algorithm for edge bundling in dynamic graphs. Unlike static graphs, dynamic graphs can undergo significant changes over different timestamps, which introduces additional challenges in maintaining the integrity of the bundled edges. Our method builds upon previous work that employed Kernel Density Estimation (KDE) to calculate the density distribution of edges in graphs. To improve the efficiency of KDE, we leverage Fast Fourier Transform (FFT) and modify the existing approach to achieve better results. To evaluate the effectiveness of our method, we employ various metrics that assess the quality of the bundled graphs compared to the previous approach. In a novel metric proposed in this work, we focus on preserving the mental map of the graph while considering the trade-off between clutter reduction and distortion. | en |
dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-08-09T16:09:12Z No. of bitstreams: 0 | en |
dc.description.provenance | Made available in DSpace on 2023-08-09T16:09:12Z (GMT). No. of bitstreams: 0 | en |
dc.description.tableofcontents | 1 Introduction -1
2 Related Work -4 2.1 Dynamic Graph -4 2.2 Edge Bundling -5 3 Background -8 3.1 Kernel Density Estimation -8 3.2 Smooth Bundling -11 3.2.1 Kernel Density Estimation Edge Bundling -11 3.2.2 Dynamic Graph Handling -13 3.3 Fast Fourier Transform on Edge Bundling -15 3.3.1 Fourier Transform Process -15 3.3.2 Analysis -17 4 Our FFT-based Algorithm -20 4.1 Method -20 4.1.1 Resampling -23 4.1.2 Smoothing -24 4.2 Complexity Analysis -24 5 Experiment Evaluation -26 5.1 Dataset Used in the Experiment -26 5.2 Metrics Used in the Experiment -26 5.3 Experimental Results -28 6 Conclusion -34 | - |
dc.language.iso | en | - |
dc.title | 基於快速傅立葉轉換之核密度估計動態圖束邊演算法 | zh_TW |
dc.title | Edge Bundling on Dynamic Graphs by FFT-based Kernel Density Estimation | en |
dc.type | Thesis | - |
dc.date.schoolyear | 111-2 | - |
dc.description.degree | 碩士 | - |
dc.contributor.oralexamcommittee | 郭斯彥;雷欽隆;黃士嘉 | zh_TW |
dc.contributor.oralexamcommittee | Sih-Yan Guo;Cin-Long Lei;Shih-Jia Huang | en |
dc.subject.keyword | 束邊演算法,資料視覺化,快速傅立葉轉換,核密度估計, | zh_TW |
dc.subject.keyword | Edge Bundling,Data Visualization,Fast Fourier Transform,Kernel Density Estimation, | en |
dc.relation.page | 39 | - |
dc.identifier.doi | 10.6342/NTU202301802 | - |
dc.rights.note | 未授權 | - |
dc.date.accepted | 2023-07-24 | - |
dc.contributor.author-college | 電機資訊學院 | - |
dc.contributor.author-dept | 電機工程學系 | - |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-2.pdf 目前未授權公開取用 | 3.82 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。