基于力導向算法優化的有向加權網絡數據的可視分析

摘? 要：復雜關系網絡數據的可視分析多采用有向加權的節點-連接圖布局。由于節點間的連接關系為多屬性數據，傳統的布局繪制算法難以完整地呈現數據間的組織結構。本文通過對力導向物理學模型進行優化設計，結合多通道視覺編碼設計，完成對復雜關系網絡數據可視化的繪制。相比較傳統的節點-連接圖布局，本算法在呈現多屬性網絡數據時具有更好的認知效能。

關鍵詞：可視分析;復雜關系網絡;力導向布局算法

中圖分類號：TN919.8? ? ? ?文獻標識碼：A 文章編號：2096-4706（2019）19-0088-05

Abstract：Visual analysis of complex relational network data mostly uses directed weighted node-join graph layout. Because the connection relationship between nodes is multi-attribute data，the traditional layout rendering algorithm is difficult to fully present the organizational structure of data. By optimizing the force-directed physical model and combining with the design of multi-channel visual coding，this paper completes the visualization of complex relational network data. Compared with the traditional node-connection graph layout，the algorithm has better cognitive performance in presenting multi-attribute network data.

Keywords：visual analytics;complex relational network;FDLA（Force-Directed Layout Algorithms）

0? 引? 言

在移動互聯網高度發達的今天，關系網絡數據是分析群體社交行為、組織結構模式、行業流程規劃等課題的重要手段。通過對多屬性關聯關系進行信息結構建模，同時結合可視化設計和數據挖掘等手段，可以幫助用戶快速提取出數據背后隱含的模式信息。

現有的可視化方法多采用節點-連接圖布局來繪制關系網絡數據，當節點間的連接關系包含多種屬性（如起止方向、權重）時，需要采用有向加權圖布局進行繪制。現有方法的基本思路是通過FR算法、KK算法等力學模型對關系網絡進行建模，求解整個關系網絡在力平衡或者能量平衡狀態下的分布，來完成圖布局的繪制。該方法在于面對大規模節點集合的網絡數據時，繪制效能和呈現效果會明顯下降;此外，簡單的力學模型無法解決連接線之間互相遮擋的問題，難以滿足多屬性關聯關系的繪制需求。

針對高維關系網絡數據可視化，本文對有向加權圖布局的力學模型進行了優化，以實現更加合理的、方便用戶視覺認知的布局效果，如圖1所示。

1? 基于多屬性關系數據的有向加權圖

關系網絡數據的復雜度主要表現在兩方面：節點數量與節點間連接數的相對比例、連接關系包含的屬性維度。前者取決于關系網絡的規模，對于網絡大數據而言，網絡規模的量級對節點-連接圖布局的繪制效率有直接影響，但對視覺認知有效性的影響并不明顯;當節點間關系為多屬性數據時，簡單的節點-連接圖布局難以完整地呈現數據結構信息，需要調動更多的視覺認知通道進行視覺編碼，同時協調各編碼通道之間的一致性，達到合理的有向加權圖繪制效果。以表1所示的全球貿易網絡數據為例，在一條交易關系記錄中，可能涵蓋了進/出口、貿易貨物量、交易周期、順差/逆差、交易價格、征稅情況等多種屬性，是典型的多屬性關系數據。這時，需采用有向加權圖的布局形式，綜合運用線寬、顏色、漸變、線型、透明度等多種視覺通道對貿易關系中的各項屬性進行視覺編碼，來完成可視化繪制。

2? 有向加權圖的力導向算法優化

力導向布局算法的核心思想，是將電場、能量場以及胡克定律等物理概念引入圖的布局空間，通過對繪制空間中各節點施加物理場作用，計算整個節點集合在場作用力平衡狀態下的分布，進而得到節點的布局結果。

力導向布局算法中較有代表性的如KK算法和FR算法，是將各節點視為在物理場中游離的點（例如原子，或小球），然后對其進行力學模擬（如電場力或者彈簧力）。由于電場中同性相斥的原理，所有的節點之間彼此存在排斥力，使得節點互相遠離對方;此外，如果節點之間有連接關系，則節點之間存在吸引力，趨于相互靠近;在此基礎上循環模擬力場作用下節點的運動，迭代計算出引力和斥力達到平衡的狀態下，各個節點的分布坐標。

在力導向布局模型中，假設有向加權圖G=（V，E），節點集合為V，有向邊集合為E。節點u，v∈V，則節點u，v之間的排斥力為：

其中，kt為節點u，v之間設置彈簧的自然長度。dist（u，v）為節點u，v之間的當前距離。節點之間的距離越近，則排斥力越強。

此外，如果節點u，v之間存在連接，則存在吸引力為：

其中，K=|D（u）-D（v）|-l，是節點u，v之間的引力調節因子。l為節點u，v之間的平衡距離。節點間距離越大，則相互吸引力越大。

對于集合V中的全部節點，通過算法循環依次計算排斥力Fr與吸引力Fa，驅動節點移動。

對整個節點集合，通過設置位移收斂的條件，使節點的運動逐漸趨于穩定狀態，整個有向加權圖達到能量均衡狀態，其條件定義為：

其中，Eattraction是節點集合V中各節點間的引力場能量值，Eresistance是各節點間斥力場的能量值，αc是集合內的布局距離調節因子，用于調整圖布局中節點的疏密程度。

這里，采用模擬退火算法cool（t），來保證物理場模擬的收斂，其模型為：

其中，p（E）指出點集合能量值狀態Eg的概率分布，作為溫度T和波茨曼常數k的因變量。在溫度不斷冷卻時，整個系統的能量狀態越來越低，直至溫度為0。

由上述分析可以看出，經過優化的力導向布局算法的邏輯框架為：

（1）數據的預處理;

（2）基于電場力計算節點間的排斥力作用;

（3）基于胡克定律計算關聯節點間的引力作用;

（4）迭代計算節點集合的能量值，回歸至能量平衡狀態。

整個布局繪制的流程如下：

Step1：對多屬性關系數據進行聚類預處理（K-means或者SOM方法）;

Step2：計算集合中各個節點與其余所有節點之間的排斥力，以及斥力作用下相互距離;

Step3：計算存在關聯的節點之間的吸引力，以及引力作用下的相對距離;

Step4：迭代更新各節點在引力和斥力作用下的位置坐標。引入模擬退火算法，每個節點在本次循環中的坐標能量值逐漸降低。

Step5：循環結束，得到節點集合在均衡狀態下的布局。

Step6：繪制節點和連線。

3? 視覺增強設計

3.1? 基于邊權重的線型調整

對于規模較大的關系網絡，由于節點數量多，當節點之間坐標相對接近時，密集的連接線可能會產生嚴重的遮擋，造成用戶難以有效地識別數據分布特征。一種改善的方法是將連接邊繪制為曲線，通過線條的彎曲拉開空間距離，提高視覺辨識度。

彎曲連接邊可能帶來的問題是對連接關系的誤讀。通過對用戶的視覺認知經驗進行研究發現，當線條表征兩個端點間的連接關系時，普通人傾向于沿連線切線的最大概率方向尋找兩個端點。也就是說，用戶習慣于在視覺上將曲線擬合成近似的直線，然后基于直線的方向延伸在復雜的網絡連接中去追蹤節點。換句話說，連接線曲率越大，用戶對節點之間連接關系視覺認知的準確性就越低。

對于多屬性連線圖來說，有向邊的權重可以作為繪制連線時視覺認知準確性的主要參考因素。本文的方法是在復雜的連接圖中，建立邊的權重與曲率之間的反向關聯，具體方法為：

首先，設置邊與邊之間的相容性系數Ce，作為控制有向邊曲率的變量。在總的相容性系數Ce中增加權重相容性系數Cw，其計算公式為：

Cw（P）=1-Wq/（Wp+Wq）

Cw（Q）=1-Wp/（Wp+Wq）

其中，Wp和Wq分別為邊P和邊Q的權重值，在本文中以該邊的流通量表示。

邊P和Q上相應控制點的計算公式為：

通過上述模型可以看出，邊的曲率受到相容性系數因子Ce的影響，而引力模型中的權重項Cw與曲率為反向關聯。當連接邊的權重值越高，則線條的曲率越小，反之則越大。由此繪制的圖布局中，權重較高的連接邊可以相對接近自身的直線形態，而權重低的邊則會出現較明顯的彎曲，這樣的設計在保證了邊之間的辨識度的同時，兼顧了集合中重要數據的視覺認知準確性。

3.2? 基于密度評估的透明度算法

除了繪制曲線的連接邊以外，還可以通過控制透明度來降低邊之間的遮擋干擾。實驗表明，當大量連線疊摞在一起時，繪制半透明的線條，可以有效降低相互遮擋的視覺干擾。本文算法基于邊密度對透明度進行計算，可實現連線密集區域的半透明效果繪制。

算法的基本思想是首先建立邊的相似度函數，通過計算集合中所有連接邊的分布密度，將圖劃分成多個不同密度等級的集合。在每個邊集中，根據邊的區域位置不同，可歸類為中心區域和跨邊界區域。建立區域透明度與邊密度的關聯函數，區域的邊密度越大，則該集合中心區域的連接線透明度越高，以有效減少視覺雜亂。

4? 有向加權圖的視覺編碼設計

在數據可視分析設計中，需要依據數據類型及呈現的需求來選擇視覺編碼的方法。按照常規的數據類型劃分，主要分為數值型、標稱型和有序型數據3類;視覺編碼通道通常劃分為：位置、幾何參數（長度、角度、面積等）、填充屬性（色調、飽和度、密度、紋理等）和形狀。視覺編碼通道對于不同數據類型的屬性表達效果是有所區別的。

針對不同的關系網絡數據集合，如何合理地對視覺編碼通道進行分配，需要基于認知規律進行分析評估。本文針對多屬性的節點-連接圖進行了用戶研究實驗：首先，在三種類型的數據進行視覺映射的排位優先級中，選擇排序相對靠前的通道（表明該通道基本適用于各種數據類型），對于多屬性的節點-連接圖來說，連接關系是以直線（或者曲線）表示，本文選擇了其中較為主要的5種編碼通道，分別是：連線的寬度、長度、填充顏色、線型和透明度等屬性，作為一致性約束分析的元素。基于一致性約束的模型，對數據屬性和映射方式進行分解，組合得到二十多種不同的情境，如表2所示。

針對每種具體的情境，分別按照符合一致性約束的原則和打破一致性約束的原則進行多視圖繪制，并由用戶進行繪制效果的合理性評估。第一種情況稱為“自發約束”，即用戶基于視覺認知自發地選擇了符合C1和C2的一致性約束條件;另一種情況下，為了確認“非一致性約束”條件存在的合理性，當用戶的評估認為多視圖繪制打破一致性約束條件更有利于視覺認知時，實驗會要求用戶進行二次確認，是否存在一種用戶認為可能繪制效果更好的視覺映射和編碼的方式。此時存在兩種可能：“提醒約束”和“例外”。“提醒約束”指雖然用戶的自發選擇打破了一致性約束的條件，但經系統提示后，用戶選擇了遵循原有的一致性約束條件;“例外”指受試者在系統提示的情況下，依然選擇打破一致性約束原則，并認為這樣更符合人的認知規律。基于上述方法完成測試并對結果進行統計分析，以得到符合用戶視覺認知規律的一致性約束模型作用條件。

可以看出：

（1）C1的確認與“例外”比C2更頻繁，這是因為C2一般可以自動得到遵守;

（2）關于XY比例尺的確認與“例外”比顏色比例尺更頻繁，可能是因為實驗中使用位置編碼比使用顏色編碼更頻繁;

（3）所有經過提醒的確認都屬于C1，其中約一半是關于編碼測量名稱的標稱型比例尺，且沒有關于測量名稱的例外，說明受試者傾向于認為測量名稱的一致性重要，但有時會忽視這一點。

全局的統計結果如圖3所示。

從全局的統計結果來看：

（1）一些約束沒有出現“例外”：C2.1，C2.2，C1.3，C1.4;

（2）一些約束出現比較高比例的“例外”：C1.1，C2.3，表明一致性約束需要綜合考慮是否進行比較，是否造成過多的空白區域和色度的語義;

（3）此外，實驗中還發現，對于屬性是否相同，需要更微妙的定義。一些受試者會采用一些其他的策略，如：坐標軸擁有相同的值標簽，趨勢線的一致性等;

（4）對于數值型和有序型數據而言，角度和色調通道都是提示確認情況發生概率較高的區域，用戶的認知習慣在這方面表現較為分散，在使用時需要慎重。

因此，通過測試可以做出以下分析：

（1）對不同的約束，確定它們適用的范圍，再確定何時系統需要執行約束條件;

（2）允許約束模型個性化，能夠學習用戶習慣并確定適合用戶的約束模型;

（3）給出修改后的預覽圖，用戶可以快速預覽效果并做出選擇;

（4）繪制視圖時應清楚地向用戶傳達不一致之處和可能的影響。

基于上述研究，最終完成有向加權圖的繪制如圖4所示（左下角為無向加權圖模式）。

5? 結? 論

本文研究針對有向加權圖的數據結構特點，將連接邊的方向、權重值等屬性作為視覺編碼的要素，納入力導向模型布局計算，在完整可視化復雜關系數據的各項屬性的同時，通過線型調控、基于邊密度繪制透明度等方法進一步降低了復雜圖的視覺雜亂和干擾問題。同時，對于如何提升大規模關系數據的視覺辨識度，在后續工作中還需要進一步研究。

參考文獻：

[1] 蔡朱華.基于聚類分析的可視化技術及其應用研究 [D].廈門：廈門大學，2014.

[2] 陳海東.不確定性可視化及分析方法研究 [D].杭州：浙江大學，2015.

[3] 丁治宇，陳海東，吳斐然，等.多變量空間數據場可視化綜述 [J].計算機輔助設計與圖形學學報，2013，25（11）：1597-1605.

[4] 姜曉睿，鄭春益，蔣莉，等.大規模出租車起止點數據可視分析 [J].計算機輔助設計與圖形學學報，2015，27（10）：1907-1917.

[5] 韋崗，曹燕，王一歌，等.計算機音樂可視化表征譜設計 [J].現代信息科技，2019，3（14）：5-7.

[6] 李春好，田波，劉玉國.逆層次分析法——復雜經濟社會系統評價問題的新方法探索 [J].吉林大學社會科學學報，2007（3）：118-124.

[7] 劉芳，田凱，周志光，等.基于SOM和引力場聚類的金融數據可視化 [J].計算機輔助設計與圖形學學報，2012，24（4）：435-442.

[8] 湯曉燕，劉文軍，朱東，等.基于ECharts的電動汽車監控可視化研究 [J].現代信息科技，2018，2（12）：46-48.

[9] TELEA A，ERSOY O，HOOGENDORP H，et al. Comparison of Node-Link and Hierarchical Edge Bundling Layouts：A User Study [C/OL]//Dagstuhl Seminar Proceedings 09211：Visualization and Monitoring of Network Traffic.[2009].http：//drops.dagstuhl.de/opus/volltexte/2009/2154.

[10] BATTISTA G D ，EADES P ，TAMASSIA R ，et al. Graph drawing：Algorithms for the visualization of graphs [M]. Prentice Hall PTR Upper Saddle River，NJ，USA，1998：258-264.

[11] CHANG B. Ecological footprint analysis based on RS and GIS in arid land [J].Journal of Geographical Sciences，2005，15（1）：44-52.

[12] CARPENDALE S.Evaluating information visualizations [M]//Lecture Notes in Computer Science.Heidelberg：Springer-Verlag，2008，4950：19-45.

[13] HURTER C，ERSOY O，TELEA A. Graph Bundling by Kernel Density Estimation [J]. Computer Graphics Forum，2012，31（3pt1）：865-874.

[14] COX D ，HARRIS R G . North American Free Trade and Its Implications for Canada：Results from a CGE Model of North American Trade[J]. World Economy，1992，15（1）：31-44.

[15] HOLTEN D . Hierarchical Edge Bundles：Visualization of Adjacency Relations in Hierarchical Data [J]. IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS，2006，12（5）：741-748.

[16] DANNY Holten，JARKE J. van Wijk. Force-Directed Edge Bundling for Graph Visualization [J]. Computer Graphics Forum，2009，28（3）：983-990.

[17] GANSNER E R，HU Y，NORTH S，et al. Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs [C]// Pacific Visualization Symposium （PacificVis）. IEEE Xplore，2011，18（1）：187-194.

[18] FRANK S，KAUFMAN A. Out-of-Core and Dynamic Programming for Data Distribution on a Volume Visualization Cluster [J].Computer Graphics Forum，2009，28（1）：141-153.

[19] FRUCHTERMAN T M J，REINGOLD E M. Graph drawing by force-directed placement [J].Software-Practice and Experience，1991，21（11）：1129-1164.

[20] YING-HUEY F，WARD MO，RUNDENSTEINER EA.Hierarchical parallel coordinates for exploration of large datasets [C].//Proceedings of visualization '99.Los Alamitos，IEEE Computer Society Press，1999：43-50.

[21] GRUENDL H ，RIEHMANN P ，PAUSCH Y ，et al. Time-Series Plots Integrated in Parallel-Coordinates Displays [J]. Computer Graphics Forum，2016，35（3）：321-330.

作者簡介：巫濱（1978-），男，漢族，江蘇常州人，博士，講師，研究方向：大數據可視化分析、真實感計算機圖形學及虛擬現實環境設計。