請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/53647
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 顏嗣鈞 | |
dc.contributor.author | Yu-Jung Ko | en |
dc.contributor.author | 柯有容 | zh_TW |
dc.date.accessioned | 2021-06-16T02:26:56Z | - |
dc.date.available | 2015-08-12 | |
dc.date.copyright | 2015-08-12 | |
dc.date.issued | 2015 | |
dc.date.submitted | 2015-08-04 | |
dc.identifier.citation | [1] D. Archambault, T. Munzner, and D. Auber. Topolayout: Multilevel graph layout by topological features. Visualization and Computer Graphics, IEEE Transactions on, 13(2):305–317, 2007.
[2] U. Brandes and C. Pich. More flexible radial layout. J. Graph Algorithms Appl., 15(1):157–173, 2011. [3] A. Clauset, M. E. Newman, and C. Moore. Finding community structure in very large networks. Physical review E, 70(6):066111, 2004. [4] P. Eades. A heuristics for graph drawing. Congressus numerantium, 42:146–160, 1984. [5] A. Frick, A. Ludwig, and H. Mehldau. A fast adaptive layout algorithm for undi- rected graphs (extended abstract and system demonstration). In Graph Drawing, pages 388–403. Springer, 1995. [6] T.M.FruchtermanandE.M.Reingold.Graphdrawingbyforce-directedplacement. Softw., Pract. Exper., 21(11):1129–1164, 1991. [7] E. R. Gansner, Y. Hu, and S. North. A maxent-stress model for graph layout. Visu- alization and Computer Graphics, IEEE Transactions on, 19(6):927–940, 2013. [8] E. R. Gansner, Y. Koren, and S. North. Graph drawing by stress majorization. In Graph Drawing, pages 239–250. Springer, 2005. [9] G. Guennebaud, B. Jacob, et al. Eigen v3. http://eigen.tuxfamily.org, 2010. [10] D.HarelandY.Koren.Afastmulti-scalemethodfordrawinglargegraphs.InGraph drawing, pages 183–196. Springer, 2001. [11] D. Harel and Y. Koren. Drawing graphs with non-uniform vertices. In Proceedings of the Working Conference on Advanced Visual Interfaces, pages 157–166. ACM, 2002. [12] J. Ho and S.-H. Hong. Drawing clustered graphs in three dimensions. In Graph Drawing, pages 492–502. Springer, 2006. [13] Y. Hu. Efficient, high-quality force-directed graph drawing. Mathematica Journal, 10(1):37–71, 2005. [14] T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information processing letters, 31(1):7–15, 1989. [15] M. Khoury, Y. Hu, S. Krishnan, and C. Scheidegger. Drawing large graphs by low- rank stress majorization. In Computer Graphics Forum, volume 31, pages 975–984. Wiley Online Library, 2012. [16] M. E. Newman and M. Girvan. Finding and evaluating community structure in net- works. Physical review E, 69(2):026113, 2004. [17] A. Symeonidis and I. G. Tollis. Visualization of biological information with circular drawings. In Biological and Medical Data Analysis, pages 468–478. Springer, 2004. [18] C. Walshaw. A multilevel algorithm for force-directed graph drawing. In Graph Drawing, pages 171–182. Springer, 2001. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/53647 | - |
dc.description.abstract | 我們提出一個新的繪製具有群集的圖的演算法。其中以 stress model 表示單一群集圖內的點,以類似彈簧及靜電斥力的力模型來表示群集間的關係。擺放群集內的點及群集間的基本概念來自於對 stress model 做 majorization 以及參考模擬退火法的力導向演算法。我們的演算法加入由群集中心施予群集內點的力,將連外群集較多的點往群集邊界推,而連外較少的點往中心點靠。此外,在擺放群集的過程中,考慮力矩平衡來旋轉群集,以達成縮短群集間連結邊的長度來減少邊的交疊。在論文的末章展示我們演算法繪製一些例圖以及實際被記錄的資料的結果,並與 full stress majorization 進行邊交疊數目和複雜度比較。 | zh_TW |
dc.description.abstract | We propose a novel layout algorithm to draw clustered graphs. The algorithm views intra-cluster graphs as stress models and inter-cluster graphs as spring and electrical force models. The basic idea of placement is based on stress majorization and force-directed placement algorithms using simulating annealing. It integrates the force from the center to push and pull the intra- cluster vertices based on their outside connectivity, referred as outside constriants, to modify the original stress model. And it applies the idea of torque equilibrium, coupled with some heuristics, to realize our force-directed placement algorithm. We demonstrate some contrived and real-world data with our algorithm, and compare our results with that of full stress majorization with respect to the running time and the number of edge crossings. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T02:26:56Z (GMT). No. of bitstreams: 1 ntu-104-R02921078-1.pdf: 1863591 bytes, checksum: 5877104dea160ffbdbeb2136218187bf (MD5) Previous issue date: 2015 | en |
dc.description.tableofcontents | 口試委員會審定書 i
致謝 ii 中文摘要 iii Abstract iv Contents v List of Figures vii List of Tables ix 1 Introduction 1 2 Preliminaries 3 2.1 Force-directedAlgorithm.......................... 3 2.1.1 SpringSystemsandElectricalForces . . . . . . . . . . . . . . . 3 2.1.2 StressModelandMajorization................... 8 2.2 Clustering.................................. 10 2.2.1 HierarchicalClustering....................... 10 2.2.2 Modularity ............................. 11 3 Clustered Graph Drawing Algorithm 12 3.1 Intra-ClusterLayout............................. 13 3.2 Inter-ClusterLayout............................. 15 4 Experiments 23 4.1 ComputationalTime ............................ 23 4.2 EdgeCrossings ............................... 24 4.3 DrawingResults............................... 25 5 Conclusion and Future Work 38 Bibliography 40 | |
dc.language.iso | en | |
dc.title | 利用力模型畫群集圖 | zh_TW |
dc.title | Drawing Clustered Graphs Using a Force-directed Placement Algorithm | en |
dc.type | Thesis | |
dc.date.schoolyear | 103-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 雷欽隆,莊仁輝,黃秋煌 | |
dc.subject.keyword | 圖形繪製,力模型演算法,蓋應力函數極小化,旋轉直覺方法,具群集關係圖, | zh_TW |
dc.subject.keyword | graph drawing,force-directed algorithms,stress majorization,rotation heuristics,clustered graphs, | en |
dc.relation.page | 41 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2015-08-04 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-104-1.pdf 目前未授權公開取用 | 1.82 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。