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

0 引言

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

算法開始：

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

PN= Initialization_layout_algorithm(G,Centrality);

For 1 → iterations do

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

For n in nodes do

For v ∈ neighbors(n) do

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

End For

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

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

End For

UpdateGlobalSpeed();

For n ∈ N do

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

End for

End For

算法結(jié)束

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

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

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

(1)

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

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

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

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

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

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

算法開始：

fornin nodes do

//根據(jù)節(jié)點的中心性計算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é)點的Closeness Centrality level計算半徑

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之間的隨機數(shù)，minSize是指的布局寬高的最小值，α和ε是常數(shù)，用來控制節(jié)點的初次分類，λ和γ是常數(shù)，用來控制節(jié)點所在區(qū)域。random(θ)是產(chǎn)生一個隨機的角度。

2.2 吸引力

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

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

(2)

2.3 基于PageRank的斥力

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

(3)

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

2.4 基于PageRank的重力

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

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

(4)

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

2.5 自適應(yīng)步長

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

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

(5)

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

(6)

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

(7)

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

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

(8)

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

(9)

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

因為重要性高的節(jié)點要在網(wǎng)絡(luò)全局中具有更大的影響力，因此這些節(jié)點也要擁有更大的牽引力。全局有效牽引力GFtra(t)是每個節(jié)點的有效牽引力與自身PageRank值的乘積的和。

(10)

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

(11)

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

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

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

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

圖1 算法整體流程圖

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

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

2.6.2 組件設(shè)計

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

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

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

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

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

5)DisplacementComponent：此組件是基于節(jié)點數(shù)據(jù)并行的，用來根據(jù)以上幾個組件的結(jié)果來更新每個節(jié)點當前的位置。

3 實驗評估

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

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

(12)

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

(13)

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

(14)

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

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

(15)

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

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

(16)

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

(17)

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

3.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)集

3.2 實驗環(huán)境

我們的機器使用的是英特爾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 算法配置

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

3.4 實驗結(jié)果

3.4.1 布局質(zhì)量

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

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

3.4.2 性能對比

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

表2 性能對比 s

4 結(jié)束語

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

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

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

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