- 學位論文
利用多層次力導向演算法繪製大型叢集圖形
Drawing Large Clustered Graphs Using a Multilevel Force-Directed Algorithm
摘要
對於圖形繪製演算法而言，結合了多層次技巧以及力導向演算法的概念可以用來處理大型圖形。 然而對於原始大型圖形來說，由於頂點過多，所以必須要將頂點分群以便於了解。而分群不僅僅是讓使用者能輕易地對圖形了解，更是將圖形還原成原始要探討的問題時所重視的。因為對於原始問題而言，如果能夠將這些具有相同特性的實體聚集起來，可以讓使用者面對這些實體時，能一目瞭然，而簡化成易於處理的問題。 結合多層次技巧以及力導向演算法的方法雖然可以處理大型圖形，但是無法表達嵌入式叢集的概念，因為對於直線畫法而言，重視的是能快速的畫出圖形、以及較美觀的圖形。 所以在這裡提出了一個做法能夠在直線畫法中表現出嵌入式叢集的概念；而這個方法是架構在結合多層次技巧以及力導向演算法之上。由於多層次技巧的兩個步驟中，皆是為了便於力導向演算法的實作，故在其兩個步驟中，分別採用不同的做法以求達到可以利用力導向演算法在原始圖形中畫出具有嵌入式叢集的美感。利用我們提出的改良式多層次力導向演算法 ，可以在直線畫法中用來繪製大型叢集圖形。
並列摘要
To draw large clustered graphs, a force-directed method combine with the multilevel technique is presented. As a large graph containing a huge number of vertices, a key step in drawing such a graph is to group those entities which have attributes in common to reduce the original problem size. Although the force-directed method which combines the multilevel technique can handle large graphs, it cannot express embedded clustered graphs very well. That is because straight-line drawing only cares about drawing graphs faster and nicer. We describe a method that can use straight-line drawing to show embedded clustered graphs. We alter the multilevel algorithm mentioned above to achieve the goal of aesthetic. As our experimental results indicate improved multilevel algorithm allows large clustered graphs to be drawn nicely.