以節點為中心的關系邊聚類與可視化算法

作者：張政,華一新,張亞軍,曾夢熊,楊振凱

摘要：對象間的關聯關系可視化主要是通過圖的連邊進行表達的,但是對象間的關聯關系紛繁復雜,大量的連邊交錯會造成嚴重的視覺混亂,圖布局和邊捆綁都是解決復雜連邊造成的視覺混亂問題的有效途徑,然而某些節點的地理位置具有實際的含義,只能通過邊捆綁方法來減少幅面載負量,進而揭示圖的潛在關聯規律。以往的邊捆綁算法是在邊的兩端節點固定的前提下,調整邊的中間控制點的位置,這樣會使得大量邊被聚集在一起,不僅會造成二次視覺混亂,且難以在節點級別揭示圖的關聯趨勢。針對這一問題,本文提出了一種以節點為中心的關系邊聚類與可視化算法。首先使用方向聚類算法實現隸屬于同一個節點的連邊的聚類,本文提出的方向聚類方法速度約是K-means算法的13倍,約是DBSCAN算法的6倍,然后對各個連邊實現控制點的內插,在此基礎上使用FR模型使得控制點位移,并通過彎曲度控制防止"過度彎曲"情況的出現,最后調整邊的透明度,使得可視化的結果突出顯示邊靠近端點處的部分。實驗結果表明,本文NCEB算法的幅面載負量L和中點距離變化量△d的約為FDEB算法的二分之一,證明本文算法可以將捆綁位置從邊的中間部位移動到節點端,不僅解決了傳統邊捆綁算法造成的二次視覺混亂問題,而且使得節點周圍的連邊分布趨勢清晰可讀,且視覺負載大大降低,有效減少了視覺誤差和信息誤判。

發文機構：信息工程大學地理空間信息學院 蘇州中科藍迪軟件技術有限公司

關鍵詞：邊捆綁方向聚類力引導視覺混亂彎曲度控制關聯關系關系可視化全空間信息系統地圖載負量edge bundlingdirection clusteringforce-directedvisual confusioncurvature controlassociative relationrelation visualizationpan spatial information systemmap load

分類號： TP3[自動化與計算機技術—計算機科學與技術]