基于PageRank的網絡布局算法

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

0 引言

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

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

1 相關工作

網絡可視化在提高布局算法的布局質量和縮短計算時間方面的研究有著顯著的進展。

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

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

2 基于PageRank的網絡布局算法

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

算法1:基于PageRank的網絡布局算法

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

輸出：具有位置信息的節點數據

算法開始：

//根據中心性獲取節點的初始位置, PN表示所有節點的位置數據。

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; //更新節點位置

End for

End For

算法結束

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

2.1 基于節點中心性的初始布局算法

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

(1)

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

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

雖然文中的初始布局算法依然使用了隨機數，但是，該算法沒有完全依賴于隨機數，而是根據每個節點的中心性給節點的初始位置劃定了區間，使其出現在一個合理的范圍，從而產生質量更高的初始布局。

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

輸入：具有中心性的節點數據

輸出：具有位置信息的節點數據

算法開始：

fornin nodes do

//根據節點的中心性計算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

// 根據節點的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

算法結束

其中:random(0,1)產生是0～1之間的隨機數，minSize是指的布局寬高的最小值，α和ε是常數，用來控制節點的初次分類，λ和γ是常數，用來控制節點所在區域。random(θ)是產生一個隨機的角度。

2.2 吸引力

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

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

(2)

2.3 基于PageRank的斥力

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

(3)

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

2.4 基于PageRank的重力

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

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

(4)

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

2.5 自適應步長

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

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

(5)

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

(6)

其中速度系數ks為一個常數，GSt為第t步迭代的網絡全局速度，將在接下來介紹GSt。為了防止單個節點的速度過快，設置了節點速度最大值。

(7)

其中:ksmax為常數。

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

(8)

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

(9)

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

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

(10)

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

(11)

其中:τ是一個調整全局速度的常數。

節點的重要性影響了網絡全局振蕩和全局牽引力的計算，這兩個因素又分別影響了節點的速度和網絡的全局速度，進一步影響了當前迭代的步長。每一個節點在每一次迭代都根據自身的參數和網絡的整體狀態獲得一個合適的步長。自適應步長的策略有效的平衡了布局算法的速度和質量。

2.6 異構并行架構設計

最初，計算機只包含用來運行編程任務的CPU。近年來，高性能計算領域中的主流計算機不斷添加了其他處理元素，其中最主要的就是GPU。隨著時間的推移，GPU從最初是被設計用來專門處理并行圖形計算問題到現在已經成了更強大且更廣義的處理器，在執行大規模并行計算中有著優越的性能和很高的效率。文中在上面所提出的布局引入網絡結構特征參數，來改進布局算法中重力，斥力以及自適應步長并且提出了基于Page- Rank的自適應步長來提高布局算法的效率和質量。可以讓布局算法以更少的迭代次數達到一個可讀性更高的布局。但是對于大部分的個人電腦來說，當面臨節點數量達到十萬甚至數百萬規模的大型復雜網絡的時候，由于力導向布局的需要大量迭代而不需要復雜的邏輯控制，如果要進一步提高布局計算速度，一個很合適的策略就是使用CPU+GPU異構并行計算來加速。CPU上進行復雜的邏輯判斷，GPU上進行大量的迭代計算，CPU和GPU通過PCI-E總線進行通信。異構并行計算的效率相比于傳統的并行計算擁有顯著的優勢。圖1顯示了文中算法的工作流圖，A部分運行在CPU上，B部分則運行在GPU上。

圖1 算法整體流程圖

2.6.1 異構架構

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

2.6.2 組件設計

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

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

2)AttractiveForceComponent：此組件是基于邊數據并行的，計算每個節點和他的相連接的節點之間的吸引力，這個力會讓相關聯的節點位置更近。

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

4)SpeedComponent：此組件是基于節點數據并行的，用來控制自適應步長的。

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

3 實驗評估

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

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

(12)

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

(13)

其中:E是網絡中邊的數量，N是節點集合，deg(n)是節點n的度。

(14)

其中:lσ是邊長的標準差，lμ是網絡布局中邊長的平均值。

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

(15)

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

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

(16)

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

(17)

文中測量了三個基于力導向模型的算法作為控制組，分別是OpenOrd，Yifan Hu和Fruchterman Reingold算法。其中OpenOrd和Yifan Hu都是具有出色的質量和性能的力導向模型的布局，Fruchterman Reingold是最經典的力導向模型布局之一。在另一個實驗中，我們在15種不同類型和規模的網絡數據上比較了文中提出的布局算法的兩個實現版本的計算時間。該算法的兩個版本分別基于純CPU實現版本和基于前文所提出的CPU + GPU的異構并行計算的實現版本。

3.1 實驗數據

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

表1 實驗數據集

3.2 實驗環境

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

3.3 算法配置

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

3.4 實驗結果

3.4.1 布局質量

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

圖2 布局質量測試結果

3.4.2 性能對比

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

表2 性能對比 s

4 結束語

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

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

最后，文中通過選取4個美學指標來評估布局結果，根據實驗發現了文中的算法在面對不同規模的網絡上都能夠得到不錯的布局質量。特別是在大規模網絡數據上，文中的算法依然能夠獲得一個高質量的布局結果。文中為了測試文中提出的異構并行計算框架的性能，選取了不同類型，不同規模的網絡數據，進行了大量的實驗。實驗結果表明了文中的異構并行計算框架能夠顯著的減少布局計算的時間。

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