[[183284]]

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

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

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

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

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

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

在采樣階段，采用隨機(jī)采樣方法。

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

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

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

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

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

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

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

圖5

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

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

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

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

***，他們采用Welsh-Powell方法對(duì)圖中的頂點(diǎn)進(jìn)行著色。因?yàn)橥瑐€(gè)頂點(diǎn)的位置分布可能因?yàn)橐恍┊惓Ｖ担瑢?dǎo)致在空間上不能聚集在一起。為了幫助用戶快速的識(shí)別同個(gè)頂點(diǎn)的位置分布，他們對(duì)圖中的頂點(diǎn)進(jìn)行了聚類處理。針對(duì)每個(gè)聚類，他們計(jì)算了群簇的邊緣，并將表示同個(gè)頂點(diǎn)的群簇通過圖8的方法，連接起來。

圖8 對(duì)頂點(diǎn)進(jìn)行聚類，添加邊緣的結(jié)果

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

接下來，我將介紹兩個(gè)實(shí)例，驗(yàn)證這個(gè)方法的可用性。

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

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

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

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

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

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

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