利用力模型畫群集圖

Abstract

我們提出一個新的繪製具有群集的圖的演算法。其中以 stress model 表示單一群集圖內的點，以類似彈簧及靜電斥力的力模型來表示群集間的關係。擺放群集內的點及群集間的基本概念來自於對 stress model 做 majorization 以及參考模擬退火法的力導向演算法。我們的演算法加入由群集中心施予群集內點的力，將連外群集較多的點往群集邊界推，而連外較少的點往中心點靠。此外，在擺放群集的過程中，考慮力矩平衡來旋轉群集，以達成縮短群集間連結邊的長度來減少邊的交疊。在論文的末章展示我們演算法繪製一些例圖以及實際被記錄的資料的結果，並與 full stress majorization 進行邊交疊數目和複雜度比較。

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.