基于多層圖布局算法的不確定性網(wǎng)絡可視化方法

陳炳坤，周 虹

?

基于多層圖布局算法的不確定性網(wǎng)絡可視化方法

陳炳坤，周 虹

(深圳大學計算機與軟件學院，廣東 深圳 518060)

由于越來越多的數(shù)據(jù)包含了不確定性，可視化不確定性網(wǎng)絡最近幾年成為了數(shù)據(jù)可視化領域中的一個熱點。在現(xiàn)有的不確定性可視化研究中，基于概率圖布局的方法取得了比較好的效果，通過一種固定采樣圖算法，可以很好地可視化不確定性網(wǎng)絡，并反映出網(wǎng)絡中的概率分布情況。針對基于概率圖布局的方法存在運行時間過長、圖布局不穩(wěn)定等問題，提出了一種基于多層圖布局的方法，改進了多層圖布局算法并與固定采樣圖算法相結合，彌補基于概率圖布局的不確定性網(wǎng)絡可視化方法的缺陷。實驗證明改進之后的算法與原來的方法相比具有更高的時間效率，而且生成的圖結構更加穩(wěn)定。

不確定性可視化；多層圖布局；概率圖；圖固定算法

圖(graph)在數(shù)據(jù)可視化中占有重要的地位，圖也叫網(wǎng)絡，一般由結點和邊組成。通過圖可以幫助人們更好地理解數(shù)據(jù)，了解數(shù)據(jù)的內部結構。有不少針對確定性網(wǎng)絡的可視化方法已經(jīng)被提出，但是目前有很多應用包含的數(shù)據(jù)都帶有不確定性，為了更好地理解這些數(shù)據(jù)，不確定性可視化方法便應運而生。FENG等[1]使用了一種基于密度的方法來可視化統(tǒng)計中的不確定性，主要是通過核密度估計的方式估計多個樣本的密度函數(shù)，使用密度函數(shù)進行可視化，但是其方法只適用于平行坐標。TAK和TOET[2]使用了顏色來表示不確定性，隨著不確定性變化，顏色會發(fā)生改變。MACEACHREN等[3]采用了一種實證研究，研究了在不確定性可視化中，不同視覺變量和符號對可視化的直觀性造成的影響，并得出結論認為不確定性可視化應該關注模糊性。近年來，把圖可視化與不確定性可視化結合也得到了廣泛的關注。GUO等[4]研究在圖的邊上表示不確定性，把4種不同的視覺變量及其組合用于邊的不確定性描述上，對比其效果。VEHLOW等[5]研究了重疊社交結構網(wǎng)絡的不確定性可視化方法，因為在社交網(wǎng)絡中，一個對象可以同時存在于多個社交團體中，可以在可視化的過程中引入不確定性的概念。

SCHULZ等[6]提出了一種基于概率圖布局(probabilistic graph layout)的算法，通過數(shù)據(jù)產(chǎn)生圖的概率模型，使用概率模型采樣得到不同的圖，最后把這些圖結合成最終的可視化效果。本文把基于概率圖布局的方法簡稱為Schulz方法，使用Schulz方法能夠可視化不確定性網(wǎng)絡及其統(tǒng)計屬性，能夠很好地反映出不同實例之間的概率分布。Schulz方法主要分為兩部分，一部分為圖的布局算法，另一部分為圖的渲染算法，其中生成圖布局的過程中存在著時間過久、布局不穩(wěn)定等問題，針對這些問題，本文提出一種基于多層圖布局的方法加以改進，使Schulz方法具有更好的性能。

1 基于概率圖布局的不確定性網(wǎng)絡可視化方法

一般情況下，可以使用簡單的離散函數(shù)來進行問題的討論，即

其中，為邊存在的概率，對應的邊權重為1；1–為邊不存在的概率，對應的權重為0，表示節(jié)點和節(jié)點無窮遠。節(jié)點之間的距離可以使用權重的倒數(shù)(1/)表示，在使用力引導算法計算圖的布局時可以用1.5倍的最遠距離來表示無窮遠。文獻[6]方法基本流程如圖1所示，總的來說包含4個步驟。

圖1 Schulz方法的流程示意圖

1.1 生成期望圖布局

1.2 采樣得到采樣圖

1.3 圖固定算法

1.4 渲染

通過多次采樣并固定采樣圖后，可以對固定在一起的多個圖進行渲染，Schulz方法中為了可以反映出概率圖的概率分布，主要采用了node splatting算法[10]和edge splatting算法[11]進行渲染。圖2(a)為Schulz方法可視化的效果圖，而圖2(b)為對應期望圖布局。

圖2 Schulz方法可視化不確定性網(wǎng)絡例子

2 基于多層圖布局算法的不確定性網(wǎng)絡可視化方法

本文采用多層圖布局算法對Schulz方法中的固定算法進行改進，提出了基于多層圖布局算法的不確定性網(wǎng)絡可視化方法，簡稱為MLSchulz方法。圖3為MLSchulz方法的主要流程圖。在計算期望圖布局的過程中使用了多層圖布局算法，在固定采樣圖的過程中也使用了多層圖布局算法，但是因為要進行固定采樣圖的操作，需要對多層圖布局算法進行一些改進。另外多層圖布局算法首先生成較小的圖，再一步步擴充，因此無需使用PoivtMDS等算法進行圖布局的初始化。

圖3 MLSchulz方法的流程示意圖

2.1 多層圖布局算法

力引導算法具有容易實現(xiàn)且繪圖效果好等優(yōu)勢得到了廣泛的使用，但是當圖的規(guī)模到了一定的程度時，力引導算法的運行時間會很長。因此有很多研究人員提出了多層圖布局的算法。多層圖布局算法求解圖的布局不是一步到位的，而是一個從粗糙到精細的過程。

多層圖布局算法一開始只對粗糙圖(只包含少數(shù)節(jié)點的圖)進行力引導算法，然后逐步擴展粗糙圖得到最終結果，因此速度上有較大提升。HAREL和KOREN[12]提出了一種高效的多層圖布局算法，MLSchulz方法在該算法的基礎上進行改進。文 獻[12]的多層圖布局算法的流程如下：

設置初始值為初始粗糙圖的節(jié)點數(shù)，一般初始化為10以內的數(shù)。為兩層粗糙圖間節(jié)點增長的倍數(shù)，=3。為概率圖(,)的節(jié)點總數(shù)。

步驟1. 計算概率圖節(jié)點間的最短距離矩陣，隨機初始化圖的布局，令=，為當前粗糙圖包含的節(jié)點數(shù)。

步驟2. 在圖中找出個中心節(jié)點的集合，在最短距離矩陣中取出個中心點之間的距離矩陣，在布局中找出該個中心節(jié)點的布局。

步驟3. 使用力引導算法重新計算這個中心節(jié)點的位置，=(,)。

步驟5. 增加的值，=×，若值小于等于，則轉到步驟2，否則結束。

其中，距離矩陣為×矩陣，使用圖布局算法計算圖的二維布局，因此布局為×2矩陣，每一行表示一個點的二維坐標。步驟2中的矩陣為×矩陣，即個中心點之間的距離，為×2矩陣。此外步驟2中求出個中心節(jié)點的過程可以使用一種近似的中心算法[13]得到，具有更高的效率且最終得到的圖布局效果區(qū)別不大。

2.2 多層圖布局算法生成期望圖布局

步驟1. 計算圖中個節(jié)點間的最短距離矩陣，隨機初始化圖個節(jié)點的布局。

步驟3. 在最短距離矩陣中取出個中心點之間的距離矩陣，在布局中找出該個中心節(jié)點的布局。

步驟4. 根據(jù)式(4)使用力引導算法重新計算個中心節(jié)點的位置，=(,)。

步驟6. 增加的值，=×，若值小于等于，則轉到步驟2，否則結束并保存好隊列，在計算采樣圖的過程中還要使用。

2.3 多層圖布局算法固定采樣圖布局

在使用多層圖布局算法計算并固定采樣圖布局時，與先前的多層圖布局算法不同。因為在計算期望圖布局時已經(jīng)把每一層粗糙圖所用到的中心點保存下來了，因此在計算并固定采樣圖布局時，無需使用k-center算法，也無需初始化和等參數(shù)。直接從隊列中抽取出每一層所要用到的中心點，從采樣圖中抽取相應的節(jié)點，再優(yōu)化能量函數(shù)即可。在計算采樣圖每一層粗糙圖布局的過程中使用的能量函數(shù)為式(6)。采樣圖計算和固定的過程如下：

步驟2. 遍歷隊列，取出下一個粗糙圖包含的所有節(jié)點集合放入，因此中包含該層粗糙圖的所有中心點。

步驟3. 在距離矩陣′中找出集合中所有點的距離矩陣，記為′，從布局′中找出中所有點的布局，記為′作為中心點，同樣也要在期望圖布局中找出包含所有點的布局。

步驟4. 根據(jù)式(6)，使用力引導算法重新計算集合里中心節(jié)點的位置′，′=(′,′,′)。

步驟6. 若遍歷完隊列，則結束，否則返回步驟2。

3 實驗結果和分析

使用Schulz方法和MLSchulz方法分別進行3組實驗，對比分析兩種方法的性能。第1組實驗使用隨機生成的概率圖進行時間對比，第2組實驗使用合成數(shù)據(jù)集和真實數(shù)據(jù)集對比兩種方法的可視化效果，第3組實驗為驗證兩種方法的布局穩(wěn)定性。

3.1 時間對比

MLSchulz方法和Schulz方法主要的時間都集中在固定采樣圖上，即優(yōu)化式(6)的過程。為了更好地對比MLSchulz方法和Schulz方法在時間上的差異，MLSchulz方法和Schulz方法一樣采用了GANSNER等[14]提出對式(6)的優(yōu)化方法，對比兩種算法的時間效率。另外還要對比兩種算法收斂后得到的能量函數(shù)值，能量函數(shù)值為式(6)的值，從而得知兩種方法優(yōu)化結果的差異。

在實驗中，首先隨機生成10~200個點的概率圖，再使用兩種方法對這近200個概率圖進行可視化，每個概率圖進行10次采樣。得到兩種方法對于每個概率圖所得到的最終能量函數(shù)值和運行時間，如圖4所示。可以看出，MLSchulz方法在時間上要遠遠優(yōu)于Schulz方法，大約可以節(jié)省一半的時間。此外，在圖4(b)中運行的時間曲線在局部有下降的趨勢，出現(xiàn)這種現(xiàn)象的主要原因有：①在圖布局開始時會隨機初始化點的位置，不同的隨機值會對運行時間產(chǎn)生少量影響；②實驗中所使用的概率圖是隨機生成的，帶有一定的隨機性，但是運行時間在總體上會隨著節(jié)點變多而增大。圖4(a)為兩種方法最終得到的能量函數(shù)值，相差不大，說明使用了多層圖布局算法進行固定可以減少時間且不會導致優(yōu)化效果的下降。

圖4 兩種方法性能的對比

3.2 布局對比

實驗中使用了4種數(shù)據(jù)對比兩種方法的可視化效果。其中兩種數(shù)據(jù)為合成數(shù)據(jù)，另兩種為從String數(shù)據(jù)庫[15]中下載的蛋白質數(shù)據(jù)。

3.2.1 合成數(shù)據(jù)

首先使用合成數(shù)據(jù)來驗證MLSchulz方法和Schulz方法的效果，圖5(a)為一個合成的矩陣圖，矩陣圖包含5個節(jié)點和8條邊。其中，每一條邊的權重分別符合一個離散概率分布，圖5(b)為該矩陣圖的邊所符合的離散概率分布。

圖5 合成矩陣圖的期望布局及邊的概率分布

從圖5(b)可以看到，除了邊5,1和邊5,3，其余的邊權重的分布都是單峰的，是一個類似高斯分布的離散分布。而邊5,1和邊5,3所服從的分布包含兩個峰。對此矩陣圖進行可視化，驗證可視化結果能否反映出該圖的概率分布，并對比兩種方法的效果。圖6為兩種方法的可視化效果，采用的值均為0.3，采樣1 000次。

從圖6(a)和圖6(b)可以看到，節(jié)點5明顯分為了3個節(jié)點簇，分別往節(jié)點1和節(jié)點3的方向偏移。觀察節(jié)點1和節(jié)點3也可以發(fā)現(xiàn)，節(jié)點1和節(jié)點3也分為了3個簇，而節(jié)點2和節(jié)點4則只有一簇。說明了兩種方法都可以比較好地反映出邊5,1和邊5,3的雙峰分布，存在兩個出現(xiàn)頻率較高的權重。可以發(fā)現(xiàn)兩種方法在小的數(shù)據(jù)集上具有相似的可視化效果，并且都可以在一定程度上反映出數(shù)據(jù)集的概率分布。

圖6 兩種方法在合成矩陣圖的可視化效果

圖7 兩種方法在合成三叉樹數(shù)據(jù)中的可視化效果

3.2.2 蛋白質數(shù)據(jù)

從String數(shù)據(jù)庫中下載真實的蛋白質數(shù)據(jù)測試MLSchulz方法的效果，蛋白質數(shù)據(jù)集中包含了蛋白質之間發(fā)生聯(lián)系的概率，即聯(lián)系系數(shù)。實驗中采用了兩組蛋白質數(shù)據(jù)集：Amy2數(shù)據(jù)集和Amy數(shù)據(jù)集。Amy2數(shù)據(jù)集包含了11種蛋白質，而Amy數(shù)據(jù)集包含了31種蛋白質數(shù)據(jù)。

首先使用Amy2數(shù)據(jù)集進行實驗，表1為Amy2數(shù)據(jù)集的聯(lián)系系數(shù)表，可以看出Amy2蛋白質與數(shù)據(jù)集中其余的蛋白質之間都具有聯(lián)系系數(shù)。在實驗中使用離散形式的概率函數(shù)，如式(2)所示，權重只有1和0。例如Si和Amy2的聯(lián)系系數(shù)為0.934，則在采樣的過程中Si和Amy2之間權重為1的概率為0.934，而權重為0的概率為0.066。因此在生成期望圖時，兩種蛋白質之間的期望權重等于聯(lián)系系數(shù)，而兩種蛋白質之間的距離為聯(lián)系系數(shù)的倒數(shù)，在計算完最短路徑后要使用1.5倍的最遠距離代替無窮遠。

表1 Amy2蛋白質數(shù)據(jù)集

兩種方法可視化的結果有較大差別，可以通過表1中各蛋白質的聯(lián)系系數(shù)，對比兩種方法的可視化效果能否正確反映蛋白質間的關系。因為每種蛋白質與Amy2之間都存在聯(lián)系的可能，根據(jù)這些蛋白質與Amy2聯(lián)系系數(shù)由大到小排列，可以把蛋白質分為4組。第1組為(Si)，第2組為(Pygl，Pygm，Pygb)，第3組為(LOC286960、Athl1、Ctrb1)，第4組為(Cela3b、Gne、Pepf)。第1組蛋白質與Amy2之間的聯(lián)系系數(shù)最大，因此在可視化的結果中應該離Amy2蛋白質最近。而第4組蛋白質與Amy2蛋白質之間的聯(lián)系系數(shù)最小，因此在可視化的結果中應該離Amy2蛋白質最遠。從圖8可以看出，兩種方法的可視化結果都大致符合這一規(guī)律，說明兩種方法均可以較好地反映出蛋白質之間的聯(lián)系。

圖8 兩種方法在Amy2數(shù)據(jù)集中的可視化效果

圖9 兩種方法在Amy數(shù)據(jù)集中的可視化效果

3.3 布局穩(wěn)定性

圖10 MLSchulz方法的流程示意圖

4 結束語

本文主要基于文獻[6]中的不確定性網(wǎng)絡可視化方法(Schulz方法)，從時間效率和布局穩(wěn)定性兩方面對其進行了改進，提出了一種基于多層圖布局算法的不確定性網(wǎng)絡可視化方法，即MLSchulz方法。MLSchulz方法可以有效的改進Schulz方法的運行速度，適應更大的概率圖。另外多層圖布局算法實現(xiàn)的過程是逐步由粗糙到精細的，在優(yōu)化的過程中不容易陷入局部最小，因此也提高了布局的穩(wěn)定性。但是本文算法仍有很多地方值得研究和改進，目前使用的優(yōu)化方法速度較慢，需要研究一種更好的優(yōu)化方法，從而提高優(yōu)化能量函數(shù)的速度且不影響優(yōu)化效果；MLSchulz方法在初始化每一個粗糙圖的時候只使用了上一個粗糙圖的布局信息，可以對其改進同時利用上一個粗糙圖和期望圖的布局信息進行初始化。

[1] FENG D, KWOCK L, LEE Y, et al. Matching visual saliency to confidence in plots of uncertain data [J]. IEEE Transactions on Visualization & Computer Graphics, 2010, 16(6): 980-989.

[2] TAK S, TOET A. Color and uncertainty: it is not always black and white [EP/OL]. [2018-01-05]. https:// repository.tudelft.nl/view/tno/uuid:3e36b35d-eadf-47de-a25c-9a639402da26.

[3] MACEACHREN A, ROTH R E, O′BRIEN J, et al. Visual semiotics & uncertainty visualization: an empirical study [J]. IEEE Transactions on Visualization & Computer Graphics, 2012, 18(12): 2496-2505.

[4] GUO H, HUANG J, LAIDLAW D H. Representing uncertainty in graph edges: an evaluation of paired visual variables [J]. IEEE Transactions on Visualization and Computer Graphics, 2015, 21(10): 1173-1186.

[5] VEHLOW C, REINHARDT T, WEISKOPF D. Visualizing fuzzy overlapping communities in networks [J]. IEEE Transactions on Visualization & Computer Graphics, 2013, 19(12): 2486-2495.

[6] SCHULZ C, NOCAJ A, GOERTLER J, et al. Probabilistic graph layout for uncertain network visualization [J]. IEEE Transactions on Visualization & Computer Graphics, 2017, 23(1): 531-540.

[7] KAMADA T, KAWAI S. An algorithm for drawing general undirected graphs [J]. Information Processing Letters, 1989, 31(1): 7-15.

[8] BRANDES U, PICH C. Eigensolver methods for progressive multidimensional scaling of large data [C]// International Symposium on Graph Drawing. Berlin: Springer-Verlag, 2006: 42-53.

[9] BRANDES U, MADER M. A quantitative comparison of stress-minimization approaches for offline dynamic graph drawing [C]//International Symposium on Graph Drawing. Berlin: Springer-Verlag, 2011: 99-110.

[10] VAN LIERE R, DE LEEUW W, et al. GraphSplatting: visualizing graphs as continuous fields [J]. IEEE Transactions on Visualization & Computer Graphics, 2003, 9(2): 206-212.

[11] HOLTEN D. Hierarchical edge bundles: visualization of adjacency relations in hierarchical data [J]. IEEE Transactions on Visualization & Computer Graphics, 2006, 12(5): 741-748.

[12] HAREL D, KOREN Y. A fast multi-scale method for drawing large graphs [J]. Journal of Graph Algorithms & Applications, 2002, 1984(3): 183-196.

[13] HOCHBAUM D S. Approximation algorithms for NP-hard problems [M]. New York: Word Publishing Company, 1997: 37-39.

[14] GANSNER E R, KOREN Y, NORTH S. Graph drawing by stress majorization [C]//GD’04 Proceedings of the 12th International Conference on Graph Drawing. Berlin: Springer, 2004: 239-250.

[15] SZKLAREZYK D, FRANCESECHINI A, KUHN M, et al. The STRING database in 2011: functional interaction networks of proteins, globally integrated and scored [J]. Nucleic Acids Research, 2011, (39): 561-568.

Uncertainty Network Visualization Method Based on Multilevel Graph Layout Algorithm

CHEN Bingkun, ZHOU Hong

(College of Computer Science & Software Engineering, Shenzhen University, Shenzhen Guangdong 518060, China)

Visualizing uncertainty networks has become a hot topic in the field of data visualization in recent years, because more and more data contains uncertainties. In the uncertainty visualization research, a method based on the probability graph layout is fairly effective by using an anchoring algorithm to make good visualization of uncertain networks and reflect the probability distribution of the networks. However, the method has two limitations, the high time complexity and unstable layout. To address these issues, we propose an uncertainty network visualization method based on multilevel graph layout algorithm. This method combines the multilevel graph layout algorithm with anchoring algorithm, and improves the limitations of the original method. Experimental results demonstrate that our improved algorithm has higher time efficiency compared with the original method, and the generated graph structure is more stable.

uncertainty visualization; multilevel graph layout; probabilistic graph; graph anchoring algorithm

TP 391

10.11996/JG.j.2095-302X.2018061130

A

2095-302X(2018)06-1130-09

2018-03-08；

2018-06-04

國家自然科學基金青年科學基金項目(61103055)

陳炳坤(1993-)，男，廣東湛江人，碩士研究生。主要研究方向為信息可視化。E-mail：chenbingkun03@163.com

周 虹(1982-)，女，湖南長沙人，講師，博士。主要研究方向為信息可視化和可視分析。E-mail：hzhou@szu.edu.cn