[[183284]]

不確定網(wǎng)絡(luò)，在本文表示頂點是確定的(certain)，邊的存在與否滿足某種概率分布的網(wǎng)絡(luò)。在圖1中，左圖是確定網(wǎng)絡(luò)(certain graph)，右圖是不確定網(wǎng)絡(luò)(uncertain graph)。

在不確定網(wǎng)絡(luò)可視分析中，現(xiàn)有的方法往往直接在確定圖(exact graph)中用視覺變量(visual variables)表示不確定信息。這些方法可以很好的將圖的拓撲結(jié)構(gòu)展示出來，但忽略了不確定信息的概率分布情況。

在這篇文章[1]，作者們提出一個概率圖(probabilistic graph)布局方法。這個方法可以同時展示圖的拓撲結(jié)構(gòu)和不確定信息的概率分布。它的基本思想是，依據(jù)蒙特卡洛方法(Monte Carlo process)對不確定圖進行采樣;將采樣獲得圖根據(jù)力導(dǎo)向算法進行布局;之后，將所有采樣圖的力導(dǎo)向布局組合起來，獲得***概率圖的布局(如圖2所示)。

圖1 左圖是確定圖;右圖是不確定圖

圖2 文章提出的概率圖布局方法流程圖

文章分析的數(shù)據(jù)可以用G = (V, E, F)表示，其中V表示頂點集合。頂點是確定的元素;E表示邊集合。邊的存在與否滿足F表示的概率密度函數(shù)。

在采樣階段，采用隨機采樣方法。

在力導(dǎo)向布局階段，他們采用圖3公式優(yōu)化圖布局。其中dij表示頂點i和頂點j之間的理想距離;wij表示邊被選取的概率。

圖3 力導(dǎo)向算法優(yōu)化函數(shù)

在組合階段，目標(biāo)是將所有采樣圖的力導(dǎo)向布局整合成一個布局。文章提出的方法是構(gòu)建一個參考布局(reference layout)，然后將所有的采樣圖根據(jù)圖4公式，重新布局。

圖4 根據(jù)參考布局，重新布局的優(yōu)化函數(shù)

在文中，參考布局一般是期望圖(expected graph)。在期望圖中，邊的權(quán)重是該邊概率分布的期望值。

在可視化階段，為了更好的將每個頂點的位置分布情況和整體的圖結(jié)構(gòu)展示出來，他們對***計算得到的整合布局進行了一系列的處理。

首先，他們對圖中的頂點進行了滾雪球(splatting)處理。這樣處理的目的是為了更好的將相同頂點的可能位置展示出來。在實際處理中，他們采用核密度估計函數(shù)計算每個頂點位置的概率密度分布函數(shù)，然后用ray-casting的方法，將頂點的位置分布展現(xiàn)出來(圖5)。在核密度估計函數(shù)中，帶寬h的值對結(jié)果的影響很大。圖6展示了在不同h的情況，獲取的結(jié)果。從左至右，布局從欠平滑狀態(tài)過渡到過平滑狀態(tài)。文章作者認為欠平滑的布局更利于用戶進一步的分析，因為欠平滑的布局可以清晰展現(xiàn)頂點和邊的關(guān)系。

圖5

左圖每個方塊表示每個頂點位置的概率密度分布;右圖是在左圖基礎(chǔ)上進行ray-casting后得到的布局

圖6 從左至右，布局從欠平滑狀態(tài)過渡到過平滑狀態(tài)

接著，他們對***計算得到的整合圖中的邊進行了處理。為了更好的描述邊的分布和圖的拓撲結(jié)構(gòu)，他們對圖中的邊進行了層次聚類;接著采用貝賽爾曲線表示這些邊，并采用滾雪球的方法對邊進行可視化(圖7)。

圖7 左圖，直接用直線展示邊的布局;右圖，對邊進行一系列處理后的布局

***，他們采用Welsh-Powell方法對圖中的頂點進行著色。因為同個頂點的位置分布可能因為一些異常值，導(dǎo)致在空間上不能聚集在一起。為了幫助用戶快速的識別同個頂點的位置分布，他們對圖中的頂點進行了聚類處理。針對每個聚類，他們計算了群簇的邊緣，并將表示同個頂點的群簇通過圖8的方法，連接起來。

圖8 對頂點進行聚類，添加邊緣的結(jié)果

根據(jù)輪廓之間的空缺方向，用戶可以將屬于同個頂點的群簇鏈接起來。

接下來，我將介紹兩個實例，驗證這個方法的可用性。

***個例子使用的是人造數(shù)據(jù)。在這個數(shù)據(jù)中，有五個頂點，8條邊。每條邊的概率分布如圖9(c)***行所示。圖9(a)表示的是這個人造數(shù)據(jù)的期望圖。我們可以發(fā)現(xiàn)，這個布局可以清晰的展示圖的拓撲結(jié)構(gòu)，但不能將邊的不確定信息展示出來;圖9(b)表示的是通過文章的方法計算得到的布局。

它清晰的展現(xiàn)了圖的拓撲結(jié)構(gòu)和頂點的位置分布;圖9(c)表示的是邊的統(tǒng)計信息。每一列表示一條邊，***行表示邊存在與否的概率分布，第二行表示采樣獲得的邊的概率分布，第三行表示邊的歐拉距離分布。我們可以發(fā)現(xiàn)，同一列的三個分布都非常的相似。這說明，足夠的采樣是可以逼近真實概率分布的;也說明他們的方法可以很好的將圖拓撲結(jié)構(gòu)展現(xiàn)出來。

圖9 (a)期望圖;(b)根據(jù)文章的方法得到的布局;(c)邊的統(tǒng)計信息分布圖

在第二個例子中，他們嘗試用這個方法分析城市之間的行程時間。該例子分析了8個城市之間的行程時間。在構(gòu)圖上，他們將每個城市看作頂點，在可到達的城市之間建立邊。邊的權(quán)重表示行程時間。為獲取城市之間的行程時間，他們通過Google Direction API隨機獲取不同時間段，任意兩個連接的城市之間的行程時間，并通過直方圖處理，獲取城市之間行程時間的概率分布圖(如圖10(a)所示)。

接著，他們根據(jù)不同的參考布局，得到了不同的概率圖布局。圖10(b)和(c)展示的布局，在其參考布局中，頂點的位置是不確定的，但頂點之間的理想距離是相應(yīng)城市之間的真實距離。圖10(d)和(e)展示的布局，在其參考布局中，頂點的位置就是相應(yīng)城市的地理位置。我們可以發(fā)現(xiàn)，這兩類參考布局得到的***布局非常的相似，它們似乎只是旋轉(zhuǎn)了不同的角度。

圖10 (a)城市之間行程時間的概率分布圖;(b)(c)和(d)(e)是兩種參考布局得到的概率圖布局

總的來說，這篇文章提出了一個新穎的不確定網(wǎng)絡(luò)的可視化方法。他們的方法可以清晰的展現(xiàn)圖的拓撲結(jié)構(gòu)和圖中不確定信息的概率分布。