基于PageRank的網(wǎng)絡(luò)布局算法

(西南科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽(yáng) 621010 )

0 引言

現(xiàn)實(shí)世界中，許多復(fù)雜的系統(tǒng)都被建模成網(wǎng)絡(luò)的形式，例如社交網(wǎng)絡(luò)，生物網(wǎng)絡(luò)和通訊網(wǎng)絡(luò)等[1-2]。網(wǎng)絡(luò)可視化能夠讓人類利用眼睛這個(gè)最高效的信息獲取通道，最大化地發(fā)揮視覺(jué)感知能力，從這些網(wǎng)絡(luò)數(shù)據(jù)中獲取有用的信息。為了更有效地分析網(wǎng)絡(luò)，需要設(shè)計(jì)出一個(gè)高性能并且對(duì)人類來(lái)說(shuō)可讀性強(qiáng)的網(wǎng)絡(luò)布局方法。過(guò)去的數(shù)十年，人們?cè)O(shè)計(jì)了許多的網(wǎng)絡(luò)可視化算法，其中基于力導(dǎo)向模型的節(jié)點(diǎn)連接圖形式的布局由于其直觀并且便于展示數(shù)據(jù)之間的關(guān)系，得到了廣泛的應(yīng)用，促進(jìn)了各個(gè)學(xué)科的發(fā)展。

現(xiàn)實(shí)世界中的網(wǎng)絡(luò)許多都帶有無(wú)尺度特性，這類網(wǎng)絡(luò)的度分布符合冪律，典型特征是在網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)只和很少節(jié)點(diǎn)連接，而有極少的節(jié)點(diǎn)與非常多的節(jié)點(diǎn)連接。然而，目前已存在的網(wǎng)絡(luò)算法通常在均勻分布的，類似于網(wǎng)格狀結(jié)構(gòu)的數(shù)據(jù)上表現(xiàn)很好。因此目前基于力導(dǎo)向模型的網(wǎng)絡(luò)布局算法在處理大規(guī)?，F(xiàn)實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)時(shí)，產(chǎn)生的布局結(jié)果往往可讀性不夠理想，很難從中得到有價(jià)值的信息。同時(shí)，目前的布局算法在計(jì)算節(jié)點(diǎn)的位置時(shí)往往沒(méi)有考慮節(jié)點(diǎn)的特征參數(shù)，如PageRank和中心性等屬性。在布局算法的結(jié)果中，節(jié)點(diǎn)所在的位置只與節(jié)點(diǎn)的連接關(guān)系有關(guān)，而與節(jié)點(diǎn)的其他無(wú)關(guān)，這樣的布局結(jié)果是不精確的。當(dāng)前的網(wǎng)絡(luò)布局算法大部分都使用的是純CPU計(jì)算布局，或者基于GPU計(jì)算但是靈活性和穩(wěn)定性不夠，易用性以及性能無(wú)法令人滿意。當(dāng)需要對(duì)大規(guī)模現(xiàn)實(shí)世界網(wǎng)絡(luò)進(jìn)行可視分析的時(shí)候，一個(gè)高質(zhì)量的，計(jì)算時(shí)間短的網(wǎng)絡(luò)布局算法的需求越來(lái)越高。目前最主要的挑戰(zhàn)有兩個(gè)方面：第一，如何在處理大規(guī)模現(xiàn)實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)時(shí)得到一個(gè)高質(zhì)量的布局；第二，在面對(duì)大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的時(shí)候有效減少布局算法的計(jì)算時(shí)間。接下來(lái)文中將闡述如何解決這兩個(gè)挑戰(zhàn)。

1 相關(guān)工作

網(wǎng)絡(luò)可視化在提高布局算法的布局質(zhì)量和縮短計(jì)算時(shí)間方面的研究有著顯著的進(jìn)展。

Eades[3]在1984年第一次提出了基于力導(dǎo)向模型的網(wǎng)絡(luò)布局算法，這個(gè)布局算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)看成一個(gè)鋼環(huán)，邊是連接鋼環(huán)的彈簧，整個(gè)網(wǎng)絡(luò)構(gòu)成了一個(gè)彈簧機(jī)械系統(tǒng)。該算法可以獲得一個(gè)具有良好可讀性的布局，但是由于時(shí)間復(fù)雜度為O(N2)，所以很難適應(yīng)大規(guī)模網(wǎng)絡(luò)的應(yīng)用。在優(yōu)化斥力計(jì)算方面，F(xiàn)ruchterman和Reingold[4]提出將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)放在平均劃分的單元網(wǎng)格中，只計(jì)算一個(gè)節(jié)點(diǎn)相鄰的網(wǎng)格中節(jié)點(diǎn)的斥力來(lái)減少?gòu)?fù)雜性。但是這種做法忽略了太多的節(jié)點(diǎn)，生成的布局精確度不夠。Barnes和Hut[15]提出使用物理學(xué)中廣為人知的N-body模擬來(lái)解決斥力計(jì)算，主要思想是將遠(yuǎn)處的一組節(jié)點(diǎn)看成是一個(gè)超級(jí)節(jié)點(diǎn)，使得斥力計(jì)算的時(shí)間復(fù)雜度從O(N2)降到了O(Nlog(N))，并且也保證了布局的精確性。在減少迭代次數(shù)方面：Kamada和Kawai基于Eades的算法提出了KK[5]算法。該算法遵循了胡克定律的偏微分方程，并以此來(lái)優(yōu)化了節(jié)點(diǎn)的布局，提高了算法的收斂速度。為了減少迭代次數(shù)一些早期的改進(jìn)方案包括模擬退火[6]、GEM(Graph EMbedder)[7-8]、美觀費(fèi)校函數(shù)(Arsthetic Cost Function)[9]等。但是都容易陷入局部最優(yōu)。Hadany R[10]首先提出了MultiLevel方法。該方法主要有兩個(gè)部分，圖粗化和圖細(xì)化。在粗化階段，算法通過(guò)的迭代的執(zhí)行圖粗化算法得到多個(gè)層次的粗化圖，到達(dá)指定的層次后，再在當(dāng)前層次上進(jìn)行計(jì)算布局，由于此時(shí)節(jié)點(diǎn)較少，就可以快速地獲得布局結(jié)果；在細(xì)化階段，也就是遞歸返回階段，算法不斷的加入上一層粗化圖中的節(jié)點(diǎn)并且計(jì)算布局，最終獲得一個(gè)完整的布局結(jié)果。這種方式減少了布局整體迭代的次數(shù)，但是不適合真實(shí)世界的網(wǎng)絡(luò)數(shù)據(jù)。為了能夠有效減少大規(guī)模網(wǎng)絡(luò)布局的計(jì)算時(shí)間，許多研究人員在布局算法中使用了并行計(jì)算技術(shù)。其中比較常見(jiàn)的OpenOrd[11]是整合了edge-cutting，和average-link聚類優(yōu)化方案的并行網(wǎng)絡(luò)布局算法，但是這個(gè)算法不適合小規(guī)模網(wǎng)絡(luò)，并且只能夠用于無(wú)向圖。Arleo[12]提出了Multi-GiLA，它是第一個(gè)基于以頂點(diǎn)中心的計(jì)算范式的MultiLevel算法。隨著GPU計(jì)算的流行，F(xiàn)rishman Y[13]提出了將Multilevel運(yùn)行在GPU上的方法，但是并沒(méi)有使用成熟的GPU并行框架，算法的性能和魯棒性都不夠理想。

許多網(wǎng)絡(luò)布局算法產(chǎn)生的結(jié)果只和節(jié)點(diǎn)的連接關(guān)系有關(guān)，而與節(jié)點(diǎn)的網(wǎng)絡(luò)特征參數(shù)如PageRank，接近度中心性等沒(méi)有關(guān)系，這樣的布局算法造成了一些信息損失。文中根據(jù)力導(dǎo)向模型的性能依賴初始布局結(jié)果的隨機(jī)值結(jié)論[14]，提出了一個(gè)基于節(jié)點(diǎn)接近度中心性的初始布局算法來(lái)獲取一個(gè)更加合理的布局在初始布局階段。初始布局不再完全依賴于隨機(jī)值。為了能夠獲得一個(gè)質(zhì)量更高的布局結(jié)果，我們引入了節(jié)點(diǎn)重要性這一網(wǎng)絡(luò)拓?fù)涮卣鲄?shù)來(lái)改進(jìn)節(jié)點(diǎn)的斥力和重力的計(jì)算。文中采用PageRank來(lái)表示節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。為了更好地平衡布局的質(zhì)量與性能，我們提出了基于PageRank的自適應(yīng)步長(zhǎng)，越重要的節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)布局結(jié)果的影響越大。最后，我們基于成熟的CPU+GPU異構(gòu)并行架構(gòu)CUDA設(shè)計(jì)了一套異構(gòu)并行計(jì)算框架，使我們的算法靈活并且高效的運(yùn)行在了GPU上進(jìn)一步減少了算法的執(zhí)行時(shí)間。

2 基于PageRank的網(wǎng)絡(luò)布局算法

文中所提出的算法是基于力導(dǎo)向模型的算法，對(duì)于網(wǎng)絡(luò)數(shù)據(jù)來(lái)說(shuō)，力導(dǎo)向模型所得出的節(jié)點(diǎn)鏈接布局，這種布局是對(duì)網(wǎng)絡(luò)關(guān)系最直接最經(jīng)典的可視化表達(dá)。力導(dǎo)向模型算法中在計(jì)算節(jié)點(diǎn)受力情況的時(shí)候不需要太復(fù)雜的邏輯控制，只需要進(jìn)行大量的迭代計(jì)算，所以非常適合CPU+GPU的異構(gòu)并行處理。文中會(huì)在這部分會(huì)從初始布局算法和吸引力算法，以及基于PageRank的斥力，重力和自適應(yīng)步長(zhǎng)幾個(gè)方面詳細(xì)講解文中的布局算法。節(jié)點(diǎn)n受到的力F(n)則是由吸引力、斥力和重力產(chǎn)生的合力。文中在斥力計(jì)算部分采用了Barnes-Hut的四叉樹(shù)近似斥力優(yōu)化[15]，篇幅原因，文中不再詳細(xì)描述。最后介紹了文中提出的用于加速布局計(jì)算的異構(gòu)并行框架。算法1顯示了文中所提出的算法的偽代碼。

算法1:基于PageRank的網(wǎng)絡(luò)布局算法

輸入：圖G=(N,E), 迭代次數(shù)iterations, 重力和斥力系數(shù)kg和kr,PageRan和每一個(gè)節(jié)點(diǎn)的中心性Centrality.

輸出：具有位置信息的節(jié)點(diǎn)數(shù)據(jù)

算法開(kāi)始：

//根據(jù)中心性獲取節(jié)點(diǎn)的初始位置, PN表示所有節(jié)點(diǎn)的位置數(shù)據(jù)。

PN= Initialization_layout_algorithm(G,Centrality);

For 1 → iterations do

BH.rebuild() //重建Barnes-Hut樹(shù)

For n in nodes do

For v ∈ neighbors(n) do

Fn= Fn+ Fa(n,v);//計(jì)算吸引力

End For

Fn= Fn+ kr× BH.force_at(Pn,PR(n)); //計(jì)算基于PageRank的斥力

Fn= Fn- kg(PR(n));//計(jì)算基于PageRank的重力

End For

UpdateGlobalSpeed();

For n ∈ N do

Pn=local_speed(n,PR(n)) ×Fn; //更新節(jié)點(diǎn)位置

End for

End For

算法結(jié)束

其中:UpdateGlobalSpeed( )是更新節(jié)點(diǎn)的全局速度，local_speed(n,PR(n))是求出節(jié)點(diǎn)n的速度。

2.1 基于節(jié)點(diǎn)中心性的初始布局算法

如上文所述，大部分基于力導(dǎo)向模型的網(wǎng)絡(luò)布局算法在生成初始布局的時(shí)候大都使用隨機(jī)布局，導(dǎo)致了布局達(dá)到穩(wěn)定狀態(tài)所需要的時(shí)間依賴于隨機(jī)布局的結(jié)果。初始布局的結(jié)果完全取決于隨機(jī)數(shù)。文中引入了節(jié)點(diǎn)的Closeness Centrality來(lái)計(jì)算一個(gè)節(jié)點(diǎn)在初始布局所處的位置，因?yàn)楣?jié)點(diǎn)的Closeness Centrality反映了節(jié)點(diǎn)在網(wǎng)絡(luò)中居于中心的程度，是衡量節(jié)點(diǎn)中心性的指標(biāo)之一[9]。文中采用了Wasserman 和Faust[16]提出的Closeness Centrality計(jì)算公式。

(1)

其中:n-1是u所有可到達(dá)的節(jié)點(diǎn)的數(shù)量，N等于網(wǎng)絡(luò)中所有節(jié)點(diǎn)的數(shù)量，d(v,u)是節(jié)點(diǎn)v和u之間的最短路徑的距離。

為了將節(jié)點(diǎn)初步分類，文中提出了Closeness Centrality Level的概念，根據(jù)節(jié)點(diǎn)的中心性的值的大小，將節(jié)點(diǎn)分為3個(gè)等級(jí)。將值歸一化處理之后，值較大的部分節(jié)點(diǎn)等級(jí)為1，其次是等級(jí)2，最后，較小的部分節(jié)點(diǎn)等級(jí)為3。初始布局算法主要根據(jù)節(jié)點(diǎn)的等級(jí)將節(jié)點(diǎn)設(shè)置在不同的位置。等級(jí)為1的節(jié)點(diǎn)設(shè)置在布局正中心位置，等級(jí)為2的節(jié)點(diǎn)相比于1的節(jié)點(diǎn)要更邊緣一些，以此類推，等級(jí)為3的節(jié)點(diǎn)在布局的最邊緣位置。我們首先計(jì)算出所有節(jié)點(diǎn)在3個(gè)不同半徑范圍內(nèi)的極坐標(biāo)，然后根據(jù)極坐標(biāo)轉(zhuǎn)直角坐標(biāo)的公式得出每個(gè)節(jié)點(diǎn)的位置。初始布局算法的偽代碼如算法2所示。

雖然文中的初始布局算法依然使用了隨機(jī)數(shù)，但是，該算法沒(méi)有完全依賴于隨機(jī)數(shù)，而是根據(jù)每個(gè)節(jié)點(diǎn)的中心性給節(jié)點(diǎn)的初始位置劃定了區(qū)間，使其出現(xiàn)在一個(gè)合理的范圍，從而產(chǎn)生質(zhì)量更高的初始布局。

算法2:初始布局算法 (Initialization_layout_algorithm)

輸入：具有中心性的節(jié)點(diǎn)數(shù)據(jù)

輸出：具有位置信息的節(jié)點(diǎn)數(shù)據(jù)

算法開(kāi)始：

fornin nodes do

//根據(jù)節(jié)點(diǎn)的中心性計(jì)算Closeness Centrality level

if n.cc > maxCC × α then

n.cl = first;

end if

if maxCc ×ε≤ n.cc < maxCc ×αthen

n.cl = second;

end if

if n.cc < maxCc ×εthen

n.cl = third;

end if

// 根據(jù)節(jié)點(diǎn)的Closeness Centrality level計(jì)算半徑

if CL(n) == first then

r =(ε× random(0, 1)) × minSize;

end if

if CL(n) == second then

r= (ε+λ× random(0, 1)) × minSize;

end if

if CL(n) == third then

r= (α+γ× random(0, 1)) × minSize;

end if

n.x=r× cos(random(θ)/180) + width ÷ 2;

n.y=r× sin(random(θ)/180) + height ÷ 2;

end for

算法結(jié)束

其中:random(0,1)產(chǎn)生是0～1之間的隨機(jī)數(shù)，minSize是指的布局寬高的最小值，α和ε是常數(shù)，用來(lái)控制節(jié)點(diǎn)的初次分類，λ和γ是常數(shù)，用來(lái)控制節(jié)點(diǎn)所在區(qū)域。random(θ)是產(chǎn)生一個(gè)隨機(jī)的角度。

2.2 吸引力

節(jié)點(diǎn)n1和n2之間的吸引力Fa的計(jì)算往往是非常簡(jiǎn)單的。我們采用了傳統(tǒng)的力導(dǎo)向布局的節(jié)點(diǎn)之間吸引力計(jì)算方法，即線性依賴于兩個(gè)節(jié)點(diǎn)之間距離[17]。

Fa(n1,n2)=d(n1,n2)

(2)

2.3 基于PageRank的斥力

傳統(tǒng)的力導(dǎo)向模型的算法中，節(jié)點(diǎn)之間的斥力往往只跟兩個(gè)節(jié)點(diǎn)之間的距離有關(guān)系。經(jīng)過(guò)這么多的研究發(fā)現(xiàn)，網(wǎng)絡(luò)中不同節(jié)點(diǎn)的重要性和影響力是不一樣的[18]，計(jì)算布局的時(shí)候應(yīng)當(dāng)考慮節(jié)點(diǎn)的重要性所帶來(lái)的影響。影響力較高的一些節(jié)點(diǎn)彼此之間應(yīng)當(dāng)有一定的距離，從而形成多個(gè)簇，而不是受到重力的影響都聚在布局正中心形成一個(gè)較大的混亂的簇，以致于大大降低布局的可讀性。PageRank是一個(gè)很好的衡量節(jié)點(diǎn)重要性和影響力的參數(shù)。因此我們?cè)O(shè)計(jì)了一個(gè)基于PageRank 的斥力計(jì)算公式，節(jié)點(diǎn)n1和n2之間的斥力的大小與兩個(gè)節(jié)點(diǎn)的PageRank值的乘積成正比，與距離成反比。斥力計(jì)算公式如式(3)所示：

(3)

其中:PR(n1)為節(jié)點(diǎn)n1的PageRank值，我們的斥力計(jì)算公式中使用PR+1而不是PR是為了避免PR為0時(shí)出現(xiàn)斥力為0的情況，斥力系數(shù)kr是一個(gè)手動(dòng)設(shè)置的常數(shù)。d(n1,n2)為n1和n2之間的距離。

2.4 基于PageRank的重力

重力是一種改善力導(dǎo)向模型布局算法的視覺(jué)效果的常用方法[19]。部分網(wǎng)絡(luò)數(shù)據(jù)中可能包含了大量小型的非連通組件和離散的節(jié)點(diǎn)，這些元素在引力和斥力的影響下每次迭代都會(huì)被推離布局中心，這將導(dǎo)致會(huì)產(chǎn)生一個(gè)過(guò)于離散的布局。為了防止布局結(jié)果中的部分節(jié)點(diǎn)偏離布局中心太遠(yuǎn)，我們使用了重力。重力是一種將節(jié)點(diǎn)吸引到布局中心點(diǎn)的力，越重要的節(jié)點(diǎn)應(yīng)該擁有越強(qiáng)的重力。節(jié)點(diǎn)n受到的重力的計(jì)算公式如公式(4)所示：

Fg(n)=kg(PR(n)+1)

(4)

其中:kg是一個(gè)常數(shù)，表示重力系數(shù)，在算法執(zhí)行的時(shí)候傳入，PR(n)和式(3)一樣為節(jié)點(diǎn)n的PageRank值，下同。

2.5 自適應(yīng)步長(zhǎng)

在力導(dǎo)向模型布局的算法中，速度和精度一直都是一個(gè)難以兩全的選擇，布局中增加步長(zhǎng)就會(huì)提高布局算法的速度，但是會(huì)導(dǎo)致布局精度下降。同理，布局迭代中減小步長(zhǎng)會(huì)增加布局的精度，但是會(huì)降低布局算法的速度。為了平衡精度和速度，文中改進(jìn)了Jacomy M[20]的自適應(yīng)的步長(zhǎng)。自適應(yīng)步長(zhǎng)的主要思想是觀察每一次迭代每個(gè)節(jié)點(diǎn)的振蕩和全局網(wǎng)絡(luò)振蕩來(lái)針對(duì)每一個(gè)節(jié)點(diǎn)的每一次迭代計(jì)算一個(gè)專屬的步長(zhǎng)。文中通過(guò)引入PageRank從而讓重要性越高的節(jié)點(diǎn)的振蕩對(duì)布局產(chǎn)生越大的影響力，重要性越低的節(jié)點(diǎn)的振蕩對(duì)全局震蕩的影響越小。布局每一次迭代的步長(zhǎng)都與當(dāng)前的狀態(tài)和全局的狀態(tài)有關(guān)，這一策略有助于平衡算法的精度和速度。因此布局將會(huì)以更快的速度達(dá)到一個(gè)穩(wěn)定的狀態(tài)。每一步迭代的步長(zhǎng)都要根據(jù)節(jié)點(diǎn)在當(dāng)前步的振蕩和整個(gè)網(wǎng)絡(luò)在當(dāng)前步全局的振蕩來(lái)動(dòng)態(tài)調(diào)整。文中定義節(jié)點(diǎn)n的第t步迭代的振蕩OSCt(n)為第t步與t-1步應(yīng)用到節(jié)點(diǎn)n上的力的差的絕對(duì)值。

OSCt(n)=|Ft(n)-Ft-1(n)|

(5)

其中:Ft(n)為節(jié)點(diǎn)n在第t步迭代受到的力，此處的力指的是吸引力、斥力和重力的合力。根據(jù)基本的物理學(xué)公式可以得出節(jié)點(diǎn)n當(dāng)前步的步長(zhǎng)D(n)=F(n)S(n), 其中S(n)為節(jié)點(diǎn)速度。

(6)

其中速度系數(shù)ks為一個(gè)常數(shù)，GSt為第t步迭代的網(wǎng)絡(luò)全局速度，將在接下來(lái)介紹GSt。為了防止單個(gè)節(jié)點(diǎn)的速度過(guò)快，設(shè)置了節(jié)點(diǎn)速度最大值。

(7)

其中:ksmax為常數(shù)。

為了讓重要性高的節(jié)點(diǎn)的振蕩對(duì)網(wǎng)絡(luò)的全局產(chǎn)生更大的影響力，就必須在計(jì)算全局振蕩的時(shí)候考慮節(jié)點(diǎn)的重要性。文中使用節(jié)點(diǎn)的PageRank值作為節(jié)點(diǎn)的重要性衡量指標(biāo)，PageRank值越大的節(jié)點(diǎn)重要性越高。因此，節(jié)點(diǎn)n在第t次迭代的全局振蕩GOSC(t)定義為每個(gè)節(jié)點(diǎn)的振蕩與自身PageRank值的乘積的和。

(8)

為了幫助布局收斂，我們引入了牽引力，節(jié)點(diǎn)n在第t次迭代的有效牽引力trat(n)是與振蕩相反的，定義為第t次迭代的力與t-1次迭代的力的和的一半。

(9)

如果節(jié)點(diǎn)n第t次迭代后，返回了t-1次迭代的位置那么trat(n)= 0；如果節(jié)點(diǎn)一直保持之前的運(yùn)動(dòng)方向，那么trat(n)=Ft(n)。

因?yàn)橹匾愿叩墓?jié)點(diǎn)要在網(wǎng)絡(luò)全局中具有更大的影響力，因此這些節(jié)點(diǎn)也要擁有更大的牽引力。全局有效牽引力GFtra(t)是每個(gè)節(jié)點(diǎn)的有效牽引力與自身PageRank值的乘積的和。

(10)

全局速度GS(t)為全局有效牽引力與全局網(wǎng)絡(luò)振蕩的比。

(11)

其中:τ是一個(gè)調(diào)整全局速度的常數(shù)。

節(jié)點(diǎn)的重要性影響了網(wǎng)絡(luò)全局振蕩和全局牽引力的計(jì)算，這兩個(gè)因素又分別影響了節(jié)點(diǎn)的速度和網(wǎng)絡(luò)的全局速度，進(jìn)一步影響了當(dāng)前迭代的步長(zhǎng)。每一個(gè)節(jié)點(diǎn)在每一次迭代都根據(jù)自身的參數(shù)和網(wǎng)絡(luò)的整體狀態(tài)獲得一個(gè)合適的步長(zhǎng)。自適應(yīng)步長(zhǎng)的策略有效的平衡了布局算法的速度和質(zhì)量。

2.6 異構(gòu)并行架構(gòu)設(shè)計(jì)

最初，計(jì)算機(jī)只包含用來(lái)運(yùn)行編程任務(wù)的CPU。近年來(lái)，高性能計(jì)算領(lǐng)域中的主流計(jì)算機(jī)不斷添加了其他處理元素，其中最主要的就是GPU。隨著時(shí)間的推移，GPU從最初是被設(shè)計(jì)用來(lái)專門(mén)處理并行圖形計(jì)算問(wèn)題到現(xiàn)在已經(jīng)成了更強(qiáng)大且更廣義的處理器，在執(zhí)行大規(guī)模并行計(jì)算中有著優(yōu)越的性能和很高的效率。文中在上面所提出的布局引入網(wǎng)絡(luò)結(jié)構(gòu)特征參數(shù)，來(lái)改進(jìn)布局算法中重力，斥力以及自適應(yīng)步長(zhǎng)并且提出了基于Page- Rank的自適應(yīng)步長(zhǎng)來(lái)提高布局算法的效率和質(zhì)量?？梢宰尣季炙惴ㄒ愿俚牡螖?shù)達(dá)到一個(gè)可讀性更高的布局。但是對(duì)于大部分的個(gè)人電腦來(lái)說(shuō)，當(dāng)面臨節(jié)點(diǎn)數(shù)量達(dá)到十萬(wàn)甚至數(shù)百萬(wàn)規(guī)模的大型復(fù)雜網(wǎng)絡(luò)的時(shí)候，由于力導(dǎo)向布局的需要大量迭代而不需要復(fù)雜的邏輯控制，如果要進(jìn)一步提高布局計(jì)算速度，一個(gè)很合適的策略就是使用CPU+GPU異構(gòu)并行計(jì)算來(lái)加速。CPU上進(jìn)行復(fù)雜的邏輯判斷，GPU上進(jìn)行大量的迭代計(jì)算，CPU和GPU通過(guò)PCI-E總線進(jìn)行通信。異構(gòu)并行計(jì)算的效率相比于傳統(tǒng)的并行計(jì)算擁有顯著的優(yōu)勢(shì)。圖1顯示了文中算法的工作流圖，A部分運(yùn)行在CPU上，B部分則運(yùn)行在GPU上。

圖1 算法整體流程圖

2.6.1 異構(gòu)架構(gòu)

如果一個(gè)算法有較小的數(shù)據(jù)規(guī)模、復(fù)雜的邏輯控制，那么最好選擇CPU處理該問(wèn)題，因?yàn)樗刑幚韽?fù)雜邏輯和指令級(jí)并行性的能力。相反，如果該問(wèn)題包含較大規(guī)模的數(shù)據(jù)處理并表現(xiàn)出大量的數(shù)據(jù)并行性，那么使用GPU是最好的選擇。因?yàn)镚PU中有大量的可編程核心，可以支持大規(guī)模多線程運(yùn)算。CPU+GPU的異構(gòu)并行計(jì)算架構(gòu)可以實(shí)現(xiàn)功能互補(bǔ)，使得應(yīng)用程序獲得最佳的運(yùn)行效果。CUDA是一種通用的異構(gòu)并行計(jì)算平臺(tái)，通過(guò)使用CUDA可以像在CPU上一樣使用GPU來(lái)進(jìn)行計(jì)算。使用這個(gè)平臺(tái)即避能夠免重復(fù)造輪子又可以確保算法程序的穩(wěn)定性。為了進(jìn)一步提升框架的靈活性，我們?cè)O(shè)計(jì)了一系列組件去實(shí)現(xiàn)文中所提出算法的異構(gòu)并行執(zhí)行。

2.6.2 組件設(shè)計(jì)

本算法的不同迭代階段需要并行計(jì)算的數(shù)據(jù)不是一成不變的。例如，在計(jì)算吸引力的時(shí)候需要對(duì)邊數(shù)據(jù)進(jìn)行并行處理，當(dāng)計(jì)算斥力的時(shí)候需要對(duì)節(jié)點(diǎn)數(shù)據(jù)進(jìn)行并行處理。由于CUDA是基于數(shù)據(jù)并行而不是基于任務(wù)并行，所以程序從CPU拷貝到GPU上的數(shù)據(jù)是兩個(gè)數(shù)組組成，其中一個(gè)存放網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)據(jù)，另一個(gè)存放網(wǎng)絡(luò)的邊數(shù)據(jù)。我們?cè)O(shè)計(jì)了5個(gè)組件，一部分組件是基于節(jié)點(diǎn)數(shù)據(jù)并行，另一部分基于邊數(shù)據(jù)并行，每個(gè)組件內(nèi)部都包含一個(gè)或者多個(gè)kernel。通過(guò)這些組件，除了可以運(yùn)行文中所提出的算法之外，還可以通過(guò)替換其中某一個(gè)組件來(lái)靈活的切換成其他的網(wǎng)絡(luò)布局算法，例如替換吸引力計(jì)算的組件來(lái)改變吸引力計(jì)算的方法等。算法一開(kāi)始會(huì)在CPU上執(zhí)行初始布局，然后通過(guò)PCIE將數(shù)據(jù)拷貝到GPU上，開(kāi)始在GPU上迭代執(zhí)行以下5個(gè)組件：

1)GravityComponent：此組件是基于節(jié)點(diǎn)數(shù)據(jù)并行的組件。主要用來(lái)計(jì)算施加到每個(gè)節(jié)點(diǎn)上的重力。

2)AttractiveForceComponent：此組件是基于邊數(shù)據(jù)并行的，計(jì)算每個(gè)節(jié)點(diǎn)和他的相連接的節(jié)點(diǎn)之間的吸引力，這個(gè)力會(huì)讓相關(guān)聯(lián)的節(jié)點(diǎn)位置更近。

3)ReplusiveForceComponent：此組件是基于節(jié)點(diǎn)數(shù)據(jù)并行的。計(jì)算每一個(gè)節(jié)點(diǎn)受到的排斥力。使不直接關(guān)聯(lián)的節(jié)點(diǎn)距離遠(yuǎn)一些，同時(shí)各個(gè)“影響力者”保持一定的距離從而來(lái)減少邊交叉和視覺(jué)雜亂。

4)SpeedComponent：此組件是基于節(jié)點(diǎn)數(shù)據(jù)并行的，用來(lái)控制自適應(yīng)步長(zhǎng)的。

5)DisplacementComponent：此組件是基于節(jié)點(diǎn)數(shù)據(jù)并行的，用來(lái)根據(jù)以上幾個(gè)組件的結(jié)果來(lái)更新每個(gè)節(jié)點(diǎn)當(dāng)前的位置。

3 實(shí)驗(yàn)評(píng)估

文中設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)來(lái)評(píng)估前面所提出的算法的質(zhì)量以及異構(gòu)并行架構(gòu)的性能。在布局質(zhì)量評(píng)估實(shí)驗(yàn)中，在布局質(zhì)量評(píng)估實(shí)驗(yàn)中，使用Crosslessness[21], Edge length variation[22], Minimum angle metric[21]和Normalized Atedge Length[23]這四個(gè)美學(xué)量化標(biāo)準(zhǔn)測(cè)量布局結(jié)果的質(zhì)量。美學(xué)指標(biāo)可以對(duì)不同布局的質(zhì)量進(jìn)行定量比較[24]，這些指標(biāo)的詳細(xì)信息如下：

Crosslessness (AMc)：邊交叉最小化是當(dāng)前最重要的美學(xué)指標(biāo)之一[25-26]。文獻(xiàn)[24]中定義Crosslessness如下所示：

(12)

其中:c是實(shí)際邊交叉的數(shù)量，cmax是邊交叉的近似上限，計(jì)算方式如下：

(13)

其中:E是網(wǎng)絡(luò)中邊的數(shù)量，N是節(jié)點(diǎn)集合，deg(n)是節(jié)點(diǎn)n的度。

(14)

其中:lσ是邊長(zhǎng)的標(biāo)準(zhǔn)差，lμ是網(wǎng)絡(luò)布局中邊長(zhǎng)的平均值。

Minimum angle metric(AMa)：這個(gè)度量量化了頂點(diǎn)上入射邊之間的最小夾角最大化的準(zhǔn)則。文獻(xiàn)[24]將其定義為節(jié)點(diǎn)n上入射邊緣之間的最小角度與理想最小角度θ(n)的平均絕對(duì)偏差。

(15)

其中:θmin(n)是節(jié)點(diǎn)n的入射邊的最小夾角。

Normalized Atedge Length (AMn)：Nocak[23]提出的“Normalized Atedge Length”適用于無(wú)尺度網(wǎng)絡(luò)，定義如下：

(16)

其中:E是網(wǎng)絡(luò)中的邊集合，N是節(jié)點(diǎn)集合。|E|和|N|分別為邊的數(shù)量和節(jié)點(diǎn)的數(shù)量，d(n1,n2)是節(jié)點(diǎn)n1和n2之間的歐式距離。 由于Qnoack的值越小越好，為了避免理解偏差，文中將指標(biāo)反轉(zhuǎn)以使其更加的清晰。

(17)

文中測(cè)量了三個(gè)基于力導(dǎo)向模型的算法作為控制組，分別是OpenOrd，Yifan Hu和Fruchterman Reingold算法。其中OpenOrd和Yifan Hu都是具有出色的質(zhì)量和性能的力導(dǎo)向模型的布局，F(xiàn)ruchterman Reingold是最經(jīng)典的力導(dǎo)向模型布局之一。在另一個(gè)實(shí)驗(yàn)中，我們?cè)?5種不同類型和規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)上比較了文中提出的布局算法的兩個(gè)實(shí)現(xiàn)版本的計(jì)算時(shí)間。該算法的兩個(gè)版本分別基于純CPU實(shí)現(xiàn)版本和基于前文所提出的CPU + GPU的異構(gòu)并行計(jì)算的實(shí)現(xiàn)版本。

3.1 實(shí)驗(yàn)數(shù)據(jù)

文中使用了各種不同類別和不同大小的現(xiàn)實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)，用來(lái)評(píng)估我們算法的可靠性，如表1所示。這些數(shù)據(jù)來(lái)自三個(gè)數(shù)據(jù)集KONECT[27]，SNAP[28]和SuiteSparse Matrix Collection[29]。其中facebook和twitter與Slashdot都是社交網(wǎng)絡(luò)，Blogs是美國(guó)2004年大選期間博客之間的超鏈接網(wǎng)絡(luò)。commanche_dual是一個(gè)來(lái)自NASA的結(jié)構(gòu)性問(wèn)題網(wǎng)格。1138_bus是一個(gè)電力系統(tǒng)總線數(shù)據(jù)，fe_4elt2是流體力學(xué)相關(guān)的結(jié)構(gòu)性網(wǎng)格數(shù)據(jù)，3elt是一個(gè)2D有限元問(wèn)題網(wǎng)格數(shù)據(jù)，web- NotreDame是圣母大學(xué)nd.edu域名內(nèi)的頁(yè)面之間的超鏈接網(wǎng)絡(luò)，web-Stanford是來(lái)自斯坦福大學(xué)stanford.edu頁(yè)面之間的超鏈接。Web-Google是Google公司在2002年舉辦的Google Programm- ing Contest中的一部分?jǐn)?shù)據(jù)，節(jié)點(diǎn)代表web頁(yè)面，邊代表它們之間的超鏈接，baidu relatepages是百度百科文章之間的鏈接網(wǎng)絡(luò)。文中將從性能和視覺(jué)效果兩個(gè)方面分析我們的算法。文中將從算法質(zhì)量和異構(gòu)架構(gòu)的性能兩個(gè)方面來(lái)分析我們的工作。

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 實(shí)驗(yàn)環(huán)境

我們的機(jī)器使用的是英特爾Core i7-6700k @4 GHz 四核處理器(四核心八線程)，32 GB DDR4 2133 MHz內(nèi)存，Nvidia GeForce GTX 1080 8 GB顯卡。我們使用了cuda 10.0版本，gcc/g++版本是7.3.0，操作系統(tǒng)是Ubuntu Linux 18.04。

3.3 算法配置

在初始布局階段，我們?cè)O(shè)置常數(shù)α和ε分別為0.3和0.6，λ和γ分別為0.3和0.4，這樣做的目的是可以使節(jié)點(diǎn)坐標(biāo)的半徑r為繪制區(qū)域長(zhǎng)寬最小值的[0,0.3)倍，以及[0.3,0.6)和[0.6,1)倍三個(gè)環(huán)形區(qū)域。從而生成初始布局各個(gè)節(jié)點(diǎn)的坐標(biāo)。我們?cè)O(shè)置重力系數(shù)kg的值為1，斥力系數(shù)kr設(shè)置為5。

3.4 實(shí)驗(yàn)結(jié)果

3.4.1 布局質(zhì)量

文中使用以上4個(gè)美學(xué)指標(biāo)(AMc,AMl,AMa,AMn)，測(cè)量了文中所提出的算法和Yifan Hu,OpenOrd與Fruchterman Reingold 4個(gè)算法在不同類型和不同規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)中的布局質(zhì)量。圖2采用堆疊條形圖可視化了我們的實(shí)驗(yàn)結(jié)果，圖中從左往右數(shù)據(jù)的規(guī)模依次增大，第二行的網(wǎng)絡(luò)數(shù)據(jù)規(guī)模都要大于第一行。每一組條形圖表示一個(gè)網(wǎng)絡(luò)數(shù)據(jù)，其中每一個(gè)條，代表一個(gè)算法在這個(gè)網(wǎng)絡(luò)數(shù)據(jù)的布局結(jié)果的美學(xué)指標(biāo)得分狀況，條中不同的顏色代表了不同的美學(xué)指標(biāo)，從上到下依次是AMc,AMl,AMa,AMn。通過(guò)實(shí)驗(yàn)我們可以明顯地發(fā)現(xiàn)，總體上，文中的算法所計(jì)算出的布局質(zhì)量一直都優(yōu)于其他三種布局算法。在小規(guī)模網(wǎng)絡(luò)網(wǎng)絡(luò)上，文中的算法質(zhì)量雖然優(yōu)于另外三個(gè)布局算法，但是差距并不大。特別是在小規(guī)模的社交網(wǎng)絡(luò)上，F(xiàn)R算法的布局質(zhì)量十分優(yōu)秀，接近于文中的算法。在大規(guī)模網(wǎng)絡(luò)上，文中所提出的算法在質(zhì)量上就開(kāi)始和其他算法拉開(kāi)差距。Fruchterman Reingold算法的質(zhì)量要遠(yuǎn)低于其在小規(guī)模網(wǎng)絡(luò)上的質(zhì)量。OpenOrd算法和Yifan Hu算法的質(zhì)量也產(chǎn)生了較大的波動(dòng)，但是整體上也是低于它們?cè)谛∫?guī)模網(wǎng)絡(luò)上的質(zhì)量。我們的算法則保持了穩(wěn)定的高質(zhì)量，并且文中所提出的算法的美學(xué)指標(biāo)分?jǐn)?shù)也高于另外三個(gè)算法。文中的算法在面對(duì)大規(guī)?，F(xiàn)實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)的時(shí)候，能夠穩(wěn)定地得出一個(gè)高質(zhì)量的布局。

圖2 布局質(zhì)量測(cè)試結(jié)果

3.4.2 性能對(duì)比

表2顯示了文中所提出的算法的兩個(gè)版本在不同規(guī)模和不同類型的現(xiàn)實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)上的計(jì)算時(shí)所消耗的時(shí)間。其中CPU+GPU一列是該算法基于CPU+GPU的異構(gòu)并行計(jì)算框架的實(shí)現(xiàn)版本在各種不同的網(wǎng)絡(luò)數(shù)據(jù)上的布局計(jì)算所消耗的時(shí)間，CPU一列是該算法基于純CPU的實(shí)現(xiàn)版本所消耗的時(shí)間。文中的布局算法計(jì)算時(shí)間包含了初始布局的時(shí)間。從表2中可以看出，CPU+GPU的實(shí)現(xiàn)在不同規(guī)模和不同類型的網(wǎng)絡(luò)數(shù)據(jù)上的性能都超過(guò)了純CPU的版本。該算法的異構(gòu)并行架構(gòu)版本相對(duì)于純CPU計(jì)算的實(shí)現(xiàn)版本達(dá)到1倍到58倍的加速；在擁有325729個(gè)節(jié)點(diǎn)1497134條邊web-Notre- Dame數(shù)據(jù)上，純CPU版本的計(jì)算時(shí)間是482.167秒，然而CPU+GPU算法的時(shí)間是8.215秒，極大地縮短了布局計(jì)算時(shí)間。根據(jù)CPU+GPU列與CPU的實(shí)驗(yàn)數(shù)據(jù)結(jié)果的對(duì)比可以發(fā)現(xiàn)，我們提出的CPU+GPU的異構(gòu)并行計(jì)算框架在減少各種規(guī)模網(wǎng)絡(luò)布局算法的計(jì)算時(shí)間方面，效果非常顯著。

表2 性能對(duì)比 s

4 結(jié)束語(yǔ)

由于當(dāng)前主流的基于力導(dǎo)向模型網(wǎng)絡(luò)布局算法在面對(duì)大規(guī)?，F(xiàn)實(shí)世界網(wǎng)絡(luò)時(shí)出現(xiàn)布局質(zhì)量不佳，計(jì)算時(shí)間過(guò)長(zhǎng)的問(wèn)題，文中提出了一個(gè)基于PageRank的新的力導(dǎo)向模型的算法和一個(gè)基于CUDA的CPU+GPU異構(gòu)并行計(jì)算框架。文中引入了兩個(gè)拓?fù)涮卣鲄?shù)，節(jié)點(diǎn)中心性和PageRank。文中設(shè)計(jì)了一個(gè)基于節(jié)點(diǎn)中心性的網(wǎng)絡(luò)初始布局算法來(lái)讓網(wǎng)絡(luò)節(jié)點(diǎn)獲得一個(gè)較好的初始位置，以減少達(dá)到最優(yōu)布局所需要迭代的次數(shù)，同時(shí)也可以削弱力導(dǎo)向模型的網(wǎng)絡(luò)布局算法對(duì)初始布局隨機(jī)值的依賴性。

PageRank是衡量節(jié)點(diǎn)重要性的關(guān)鍵指標(biāo)。文中創(chuàng)造性的提出了基于PageRank的重力，斥力和自適應(yīng)步長(zhǎng)。重力是用來(lái)防止一部分離散的節(jié)點(diǎn)推離布局中心太遠(yuǎn)。因?yàn)樵街匾墓?jié)點(diǎn)應(yīng)當(dāng)距離布局重心越近，所以基于節(jié)點(diǎn)重要性的重力的計(jì)算公式中，節(jié)點(diǎn)的重力與節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度成正比。節(jié)點(diǎn)的PageRank值越大，節(jié)點(diǎn)的重力也就越大。為了防止重要性較高的節(jié)點(diǎn)都集中在布局中心靠的太近從而造成視覺(jué)遮擋，文中提出了基于節(jié)點(diǎn)重要性的斥力，使得重要程度較高的節(jié)點(diǎn)彼此之間擁有一定的距離，不至于在布局中心形成一個(gè)又大又密的簇，而是形成多個(gè)清晰的小型的簇。我們也使用了四叉樹(shù)斥力優(yōu)化來(lái)降低斥力計(jì)算部分的時(shí)間復(fù)雜度，提升了布局性能。為了平衡布局的精度和速度，我們提出了基于節(jié)點(diǎn)重要性的自適應(yīng)步長(zhǎng)，越重要節(jié)點(diǎn)的產(chǎn)生的振蕩對(duì)網(wǎng)絡(luò)全局造成的影響越大，每一個(gè)節(jié)點(diǎn)每一次迭代的步長(zhǎng)都是綜合考慮和網(wǎng)絡(luò)全局和節(jié)點(diǎn)自身情況所計(jì)算出來(lái)的。

最后，文中通過(guò)選取4個(gè)美學(xué)指標(biāo)來(lái)評(píng)估布局結(jié)果，根據(jù)實(shí)驗(yàn)發(fā)現(xiàn)了文中的算法在面對(duì)不同規(guī)模的網(wǎng)絡(luò)上都能夠得到不錯(cuò)的布局質(zhì)量。特別是在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)上，文中的算法依然能夠獲得一個(gè)高質(zhì)量的布局結(jié)果。文中為了測(cè)試文中提出的異構(gòu)并行計(jì)算框架的性能，選取了不同類型，不同規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)，進(jìn)行了大量的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明了文中的異構(gòu)并行計(jì)算框架能夠顯著的減少布局計(jì)算的時(shí)間。

未來(lái)我們會(huì)繼續(xù)完善現(xiàn)在的工作，使其應(yīng)用到大規(guī)模網(wǎng)絡(luò)可視化系統(tǒng)中，從而提升此類系統(tǒng)對(duì)大規(guī)模網(wǎng)絡(luò)的處理能力，使得研究人員可以更加便利地通過(guò)可視化系統(tǒng)來(lái)分析大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)。此外，我們將研究進(jìn)一步改進(jìn)節(jié)點(diǎn)重要性的計(jì)算方法，并且改進(jìn)算法可以根據(jù)不同的網(wǎng)絡(luò)類型，去自動(dòng)選取合適的節(jié)點(diǎn)重要性計(jì)算方法。