面向大規(guī)模圖數(shù)據(jù)的并行圖布局算法

程致遠(yuǎn)，鮑玉斌，冷芳玲

東北大學(xué)計(jì)算機(jī)科學(xué)系，遼寧 沈陽(yáng) 110819

面向大規(guī)模圖數(shù)據(jù)的并行圖布局算法

程致遠(yuǎn)，鮑玉斌，冷芳玲

東北大學(xué)計(jì)算機(jī)科學(xué)系，遼寧 沈陽(yáng) 110819

圖模型是一種廣泛使用的建模工具。圖的可視化作為一種直觀的圖數(shù)據(jù)分析工具被廣泛使用。圖數(shù)據(jù)可視化中最關(guān)鍵的技術(shù)是圖布局算法，但是目前并沒(méi)有高效的并行圖布局算法，因此目前對(duì)于海量圖數(shù)據(jù)的可視化是一個(gè)挑戰(zhàn)性問(wèn)題。針對(duì)這一問(wèn)題，在力導(dǎo)向布局算法基礎(chǔ)上，忽略弱關(guān)聯(lián)頂點(diǎn)間的斥力計(jì)算，提出了k-friend布局算法；并針對(duì)海量圖數(shù)據(jù)設(shè)計(jì)了高效的并行圖布局算法。在人工和實(shí)際數(shù)據(jù)集上的測(cè)試結(jié)果表明，在布局質(zhì)量降低可容忍的情況下，該算法大幅度提升了布局的速度。

力導(dǎo)向算法；可視化分析；社交網(wǎng)絡(luò)；并行布局算法

1 引言

圖模型是一種廣泛使用的建模工具，許多應(yīng)用問(wèn)題都可以抽象成圖，如社交網(wǎng)絡(luò)就可以用圖模型進(jìn)行表示。圖數(shù)據(jù)的可視化技術(shù)可以將圖的鄰接表或者鄰接矩陣轉(zhuǎn)換為直觀的、用點(diǎn)和線組成的圖形，可以令研究人員直觀地看到圖數(shù)據(jù)的關(guān)聯(lián)關(guān)系和結(jié)構(gòu)，是圖數(shù)據(jù)分析的一種非常常用并且重要的手段。圖可視化技術(shù)中關(guān)鍵的一個(gè)環(huán)節(jié)是圖的布局算法。

力導(dǎo)向布局算法是目前最為常用的圖布局算法，其優(yōu)點(diǎn)是可以清晰地展現(xiàn)出圖的社區(qū)結(jié)構(gòu)，并且也能很好地展現(xiàn)出頂點(diǎn)之間的關(guān)聯(lián)關(guān)系，是由Peter Eades提出的。該算法通過(guò)模擬物理學(xué)的概念，認(rèn)為圖中的每一個(gè)點(diǎn)都受到引力和斥力的影響，鄰居頂點(diǎn)之間互相有吸引力，所有頂點(diǎn)之間存在排斥力，如果兩個(gè)頂點(diǎn)之間的吸引力大于排斥力，則這兩個(gè)頂點(diǎn)會(huì)被調(diào)整到更近的位置；反之，如果兩個(gè)頂點(diǎn)之間的排斥力大于吸引力，則這兩個(gè)頂點(diǎn)會(huì)被調(diào)整到較遠(yuǎn)的位置。其意義是可以使得關(guān)系緊密的頂點(diǎn)最終被放置到相對(duì)靠近的位置，不相關(guān)的頂點(diǎn)會(huì)被放置到相對(duì)較遠(yuǎn)的位置。從而，用戶可以根據(jù)兩個(gè)頂點(diǎn)間的距離得知這兩個(gè)頂點(diǎn)的相關(guān)性的強(qiáng)弱，同時(shí)，排斥力還可以使頂點(diǎn)之間存在一定的距離，使得網(wǎng)絡(luò)中的頂點(diǎn)不會(huì)因?yàn)樘芗蛘咧丿B而影響視覺(jué)觀察效果。

但是目前力導(dǎo)向算法的時(shí)間復(fù)雜度大多都是O(n2)，難以對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行布局，并且由于圖數(shù)據(jù)的特點(diǎn)是頂點(diǎn)之間的關(guān)系錯(cuò)綜復(fù)雜，其中任何一個(gè)頂點(diǎn)位置的改變都會(huì)影響其他所有頂點(diǎn)的位置，因此很難進(jìn)行并行化。

以上原因使得目前的圖布局算法不能適用于頂點(diǎn)數(shù)和邊數(shù)很大的圖。面對(duì)目前數(shù)據(jù)量越來(lái)越大的社交網(wǎng)絡(luò)數(shù)據(jù)，亟待一個(gè)能夠?qū)Υ笠?guī)模圖數(shù)據(jù)進(jìn)行布局的布局算法。本文通過(guò)忽略部分弱關(guān)聯(lián)頂點(diǎn)的斥力計(jì)算，在犧牲少量布局質(zhì)量的情況下，大幅度提升布局的速度，并且在此基礎(chǔ)上提出了并行計(jì)算的算法，最后測(cè)試表明，本文提出的圖布局算法在圖頂點(diǎn)數(shù)較多時(shí)，在計(jì)算速度上有比較大的提升，并且布局質(zhì)量下降的并不明顯。

2 相關(guān)工作

通常應(yīng)用問(wèn)題建模得到的圖結(jié)構(gòu)（如社交網(wǎng)絡(luò)結(jié)構(gòu)、Web連接圖結(jié)構(gòu)等）都是拓?fù)鋱D。拓?fù)鋱D可視化技術(shù)的核心是圖布局算法。關(guān)于圖布局算法已經(jīng)有許多的研究，同時(shí)也提出了一些圖可視化布局算法。目前圖布局算法主要分為3種：力導(dǎo)向布局算法、限定圖的展現(xiàn)形式和利用數(shù)據(jù)自身屬性信息的布局方法。

力導(dǎo)向布局算法[1]的主要思想是將整個(gè)拓?fù)鋱D看作一個(gè)物理系統(tǒng)，相鄰頂點(diǎn)之間存在引力，不相鄰的頂點(diǎn)間存在斥力，每次迭代計(jì)算頂點(diǎn)受到的合力，并根據(jù)合力移動(dòng)頂點(diǎn)，最終使整個(gè)系統(tǒng)達(dá)到一個(gè)能量的極小值。該布局算法對(duì)目前的社交數(shù)據(jù)有很好的展現(xiàn)效果，可以清晰地表現(xiàn)出頂點(diǎn)間的鄰接關(guān)系以及整個(gè)圖的社區(qū)結(jié)構(gòu)。代表性的算法有Fruchterman等人的FR算法[2]、Hu Y F提出的Hu氏算法[3]、Hadany等人提出的HH算法[4]、Kamada等人提出的KK算法[5]、GGK算法[6]等。力導(dǎo)向布局算法最早是由Eades在1984年提出的，基本思想是將整個(gè)圖看作一個(gè)頂點(diǎn)為鋼圈、邊為彈簧的物理系統(tǒng)，每個(gè)頂點(diǎn)被賦予初始位置后會(huì)根據(jù)受到的斥力和引力調(diào)整位置，直到整個(gè)系統(tǒng)達(dá)到一個(gè)穩(wěn)定的狀態(tài)。之后很多研究者針對(duì)Eades的算法提出了一些改進(jìn)算法，如KK算法、FR算法。HH算法首次使用了分層布局的手段，先返回一個(gè)粗略的結(jié)果，再繪制細(xì)節(jié)。這些算法的每一步迭代的時(shí)間復(fù)雜度都為O(n2)。Hu氏算法將遠(yuǎn)距離的一簇頂點(diǎn)聚集為一個(gè)超點(diǎn)，將每次迭代的時(shí)間復(fù)雜度降低到O(nlgn)。2014年Jacomy M針對(duì)FR算法提出了很多工程上的改進(jìn)，提出了局部速度的概念，使得每個(gè)頂點(diǎn)每次迭代可以移動(dòng)的最大位移與其出度成正比，加快了算法收斂的速度，但其本質(zhì)仍是FR算法，時(shí)間復(fù)雜度為O(n2)。力導(dǎo)向布局算法布局效果如圖1所示，本文提出的算法也是基于力導(dǎo)向算法的思想，但是由于這種算法的時(shí)間復(fù)雜度較高，一般不適合做大規(guī)模圖數(shù)據(jù)的展現(xiàn)，因此本文對(duì)這種算法進(jìn)行了改進(jìn)：對(duì)圖中頂點(diǎn)間的斥力的計(jì)算進(jìn)行了近似處理，認(rèn)為不（直接）相關(guān)聯(lián)的頂點(diǎn)之間的斥力可以近似計(jì)算，以提高算法的計(jì)算效率。

限定圖的展現(xiàn)形式的思想是對(duì)圖進(jìn)行布局之前，預(yù)先設(shè)定好圖的展現(xiàn)形式，每一個(gè)頂點(diǎn)在布局時(shí)都直接放在預(yù)先設(shè)定好的位置上，不需要考慮圖的整體拓?fù)浣Y(jié)構(gòu)，從而可以快速地對(duì)海量數(shù)據(jù)進(jìn)行布局。該算法的時(shí)間復(fù)雜度為O(n)。但是這種布局算法并不能反映出頂點(diǎn)之間的關(guān)聯(lián)關(guān)系，所以，一般不會(huì)用于對(duì)需要反映圖數(shù)據(jù)的整體結(jié)構(gòu)的數(shù)據(jù)進(jìn)行布局。這類算法的代表有圓形布局法[7]和矩形布局法[8]等。

圖1 力導(dǎo)向圖示例

目前很多圖數(shù)據(jù)都會(huì)附帶地理位置等信息，因此在這類圖數(shù)據(jù)進(jìn)行布局時(shí)可以利用數(shù)據(jù)自身的位置屬性信息。利用數(shù)據(jù)自身屬性信息的布局方法就是充分利用圖數(shù)據(jù)自身的這部分信息進(jìn)行布局，如地圖布局[9]等。這類算法的時(shí)間復(fù)雜度為O(n)，但是并不是所有的圖數(shù)據(jù)都有可以利用的屬性信息，因此不能用于沒(méi)有位置信息的圖數(shù)據(jù)的布局。

以上布局方法中，只有限定圖的展現(xiàn)形式和利用屬性信息的算法可以對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行布局，但是它們具有局限性。力導(dǎo)向類算法由于時(shí)間復(fù)雜度太大，不適合對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行布局。因此，這方面的研究比較少，Tikhonova A提出了一種FR算法的并行實(shí)現(xiàn)策略[10]，實(shí)驗(yàn)表明該算法隨著處理器核心數(shù)量的提高，算法的計(jì)算時(shí)間線性減少，但是作者并沒(méi)有測(cè)試這種算法在大數(shù)據(jù)下的性能，因?yàn)镕R算法每次迭代的時(shí)間復(fù)雜度為O(n2)，所以在數(shù)據(jù)量變大時(shí)該算法的性能不會(huì)很好。

力導(dǎo)向算法在處理社交數(shù)據(jù)時(shí)有很大的優(yōu)勢(shì)，可以清晰地顯示圖社交數(shù)據(jù)的社區(qū)結(jié)構(gòu)和關(guān)聯(lián)關(guān)系。因此，目前對(duì)于社交數(shù)據(jù)的布局大都使用力導(dǎo)向布局算法。力導(dǎo)向布局算法又稱為“彈簧算法”，目前最廣泛使用的是FR算法。

FR算法定義直接相連的頂點(diǎn)間存在引力，不直接相連的頂點(diǎn)間存在斥力，每一次迭代，分為3步：第一，對(duì)每個(gè)點(diǎn)計(jì)算其與相鄰頂點(diǎn)之間的引力；第二，對(duì)每個(gè)點(diǎn)計(jì)算其與其他所有頂點(diǎn)之間的斥力；第三，對(duì)每個(gè)頂點(diǎn)根據(jù)其引力和斥力的合力，調(diào)整其位置。調(diào)整位置的距離取決于一個(gè)退火函數(shù)。然后根據(jù)新得到的位置不斷迭代上述的3步，直到達(dá)到指定的迭代次數(shù)，或者這個(gè)系統(tǒng)的能量小于一個(gè)閾值。所有的力導(dǎo)向布局算法基本都是基于這個(gè)框架。由于FR算法要計(jì)算任意不相鄰頂點(diǎn)之間的斥力，所以導(dǎo)致算法每一次迭代的時(shí)間復(fù)雜度為O(n2)。

傳統(tǒng)力導(dǎo)向布局算法之所以要對(duì)任意的兩個(gè)頂點(diǎn)計(jì)算斥力是為了使不相關(guān)的頂點(diǎn)之間的距離盡可能的遠(yuǎn)。而通過(guò)觀察發(fā)現(xiàn)，在對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行分析時(shí)，通常只關(guān)心關(guān)系比較緊密的頂點(diǎn)之間的位置關(guān)系，而對(duì)于關(guān)系不緊密，甚至無(wú)關(guān)的兩個(gè)頂點(diǎn)，并不關(guān)心它們之間的距離是否跟它們之間關(guān)系的緊密程度成正比。換言之，人們只是希望這兩個(gè)頂點(diǎn)的距離不要太近，至于它們之間的距離到底多遠(yuǎn)，對(duì)分析數(shù)據(jù)幾乎沒(méi)有影響。在這個(gè)前提下，可以通過(guò)只計(jì)算與一個(gè)頂點(diǎn)關(guān)系緊密的k個(gè)頂點(diǎn)（如它的第一跳和第二跳鄰居）之間的引力和斥力的方法，將原本O(n2)時(shí)間復(fù)雜度的布局算法改進(jìn)為時(shí)間復(fù)雜度為O(kn)的算法。k的值越大，計(jì)算越精確，同時(shí)性能也越低，當(dāng)k為n-1（n為圖的頂點(diǎn)數(shù)）時(shí)，本文算法就退化為FR算法，時(shí)間復(fù)雜度變?yōu)镺(n2)。用戶需要根據(jù)自己對(duì)于計(jì)算結(jié)果精確度的需要，設(shè)置k的大小。

3 近似力導(dǎo)向布局算法（k-friend布局算法）

傳統(tǒng)的力導(dǎo)向算法認(rèn)為任何頂點(diǎn)之間都存在斥力，這樣可以使得不相干的頂點(diǎn)之間的距離較遠(yuǎn)，但這樣也使得計(jì)算的時(shí)間復(fù)雜度達(dá)到了O(n2)。在處理大規(guī)模圖數(shù)據(jù)時(shí)，人們往往只關(guān)心關(guān)聯(lián)關(guān)系較大的頂點(diǎn)之間的位置關(guān)系，而不相關(guān)或者相關(guān)性很小的兩個(gè)頂點(diǎn)之間的位置人們并不關(guān)心。換言之，人們希望看到關(guān)聯(lián)相對(duì)緊密的頂點(diǎn)之間的距離與關(guān)聯(lián)的緊密程度成正比，關(guān)聯(lián)程度越緊密，它們的距離越近，而對(duì)于關(guān)聯(lián)程度弱的頂點(diǎn)，它們之間的距離具體有多遠(yuǎn)，人們并不關(guān)心，只要不是太近就可以接受。因此對(duì)于聯(lián)系不緊密的頂點(diǎn)，可以不計(jì)算他們之間的斥力，即在用傳統(tǒng)力導(dǎo)向算法計(jì)算任意頂點(diǎn)間的斥力時(shí)，只計(jì)算關(guān)系最緊密的k個(gè)頂點(diǎn)之間的斥力，這樣可以在很大程度上降低算法的時(shí)間復(fù)雜度。因此，本文稱這種算法為k-friend布局算法。這里的k實(shí)際上是一個(gè)控制頂點(diǎn)數(shù)量的參數(shù)，它的確定應(yīng)該與一個(gè)頂點(diǎn)的平均幾跳鄰居數(shù)有關(guān)，如果只考慮一跳鄰居，則是只考慮與一個(gè)頂點(diǎn)直接相連的鄰居數(shù)，如果考慮兩跳鄰居，則是一個(gè)頂點(diǎn)的兩跳之內(nèi)的所有鄰居之和。當(dāng)這個(gè)頂點(diǎn)數(shù)超過(guò)了k的限制，就要采取一些措施控制鄰居的總數(shù)。這是因?yàn)?，在真?shí)圖中，很可能會(huì)存在超級(jí)頂點(diǎn)，即這個(gè)頂點(diǎn)的鄰居數(shù)遠(yuǎn)遠(yuǎn)大于其他頂點(diǎn)，這時(shí)從計(jì)算效率考慮，需要從中選擇k個(gè)頂點(diǎn)。k-friend布局算法具體的實(shí)現(xiàn)原理如下。

先介紹算法需要的數(shù)據(jù)結(jié)構(gòu)。每一個(gè)頂點(diǎn)包括頂點(diǎn)信息vertex和邊信息edges，使用二元組表示為＜vertex,edges＞；頂點(diǎn)v信息中包含頂點(diǎn)ID、頂點(diǎn)屬性、坐標(biāo)信息和與該頂點(diǎn)關(guān)系最緊密的k個(gè)頂點(diǎn)的集合friendSet（friendSet=＜friend1,friend2…friendk＞），即vertex=＜vertexID,attr,coord, friendSet＞。其中，friendSet中每一個(gè)數(shù)據(jù)項(xiàng)friend包括頂點(diǎn)u的ID和與頂點(diǎn)v之間的深度deep（即頂點(diǎn)v與頂點(diǎn)u之間的連接跳數(shù)），即friendi=＜vertexID,deep＞；坐標(biāo)信息中包括上一次迭代和本次迭代頂點(diǎn)的坐標(biāo)，即coord=＜o(jì)ldx,oldy,x,y＞。邊的信息包括目的頂點(diǎn)I D和邊的權(quán)值，即edges=＜(destVertexID1,weight1), (destVertexID2,weight2), …, (destVertexIDm, weightm)＞。

k-friend布局算法主要分為如下4個(gè)步驟。

步驟1 對(duì)圖數(shù)據(jù)進(jìn)行預(yù)處理，對(duì)每個(gè)頂點(diǎn)使用深度優(yōu)先搜索找出其跳鄰居，n表示頂點(diǎn)與其n階以上的鄰居之間的關(guān)系是可以被忽略的，n越大，布局越接近FR算法，同時(shí)計(jì)算時(shí)間也會(huì)變長(zhǎng)，因此用戶要根據(jù)自己對(duì)于精確度的需要來(lái)設(shè)置n的大小，如果數(shù)量大于k則在其中隨機(jī)選取k個(gè)。將這k個(gè)頂點(diǎn)的頂點(diǎn)ID和深度保存在頂點(diǎn)的friendSet中。經(jīng)過(guò)以上步驟后，會(huì)得到每個(gè)頂點(diǎn)的n跳鄰居集合friendSet =＜(vertexI D1,deep1),(vertexID2,deep2)，…，(vertexIDk, deepk)＞。

步驟2 為每個(gè)頂點(diǎn)分配一個(gè)初始位置。位置的分配策略已經(jīng)有很多的研究成果，本文采用與FR算法一樣的隨機(jī)分配策略。

步驟3 計(jì)算引力和斥力。對(duì)于每個(gè)頂點(diǎn)計(jì)算其與鄰居節(jié)點(diǎn)之間的引力fa(u,v)。計(jì)算其與friendSet中的節(jié)點(diǎn)的斥力fr(u,v)。具體引力斥力計(jì)算式有很多選擇，可以根據(jù)需要選擇不同的引力計(jì)算式，本文采用的是fa=d2/k、fr=k2/d，k為用戶認(rèn)為頂點(diǎn)之間最理想的距離，不影響布局結(jié)果，調(diào)整k相當(dāng)于對(duì)圖進(jìn)行整體縮放，d為兩個(gè)頂點(diǎn)之間的距離。引力和斥力計(jì)算式的算法會(huì)影響布局結(jié)果的社區(qū)屬性，可以通過(guò)調(diào)整引力和斥力的計(jì)算式使得布局結(jié)果更有社區(qū)結(jié)構(gòu)，參考文獻(xiàn)[11]進(jìn)行了深入的研究和探討。引力計(jì)算式的選擇不影響布局算法的本質(zhì)，只會(huì)對(duì)布局細(xì)節(jié)產(chǎn)生影響。

步驟4 根據(jù)頂點(diǎn)受到的斥力和引力調(diào)整頂點(diǎn)的位置。頂點(diǎn)移動(dòng)的最大距離可以根據(jù)退火算法進(jìn)行動(dòng)態(tài)的調(diào)整。

步驟5 重復(fù)執(zhí)行步驟3和步驟4，直到達(dá)到最大迭代步數(shù)，或者整個(gè)系統(tǒng)的能量小于給定的閾值。

該算法在布局階段每一次迭代的時(shí)間復(fù)雜度可以達(dá)到O(kn)。k為每個(gè)頂點(diǎn)friendSet的大小，在預(yù)處理階段由用戶指定。

k-friend布局算法描述如下。

要注意的是本算法雖然提升了時(shí)間復(fù)雜度，但是增加了空間復(fù)雜度，需要O(kn)的額外空間用以存儲(chǔ)頂點(diǎn)的friendSet。不過(guò)目前圖布局算法的瓶頸在于計(jì)算速度方面，內(nèi)存相對(duì)很寬裕，尤其是對(duì)于分布式計(jì)算系統(tǒng)而言。并且筆者認(rèn)為如果要使算法高效地并行化，那么friendSet是必不可少的。值得注意的是k的值越大，計(jì)算越精確，同時(shí)性能也越低，當(dāng)k為正無(wú)窮大時(shí)，本文算法等于FR算法，時(shí)間復(fù)雜度退化為O(n2)。用戶需要根據(jù)自己對(duì)于計(jì)算結(jié)果精確度的需要設(shè)置k的大小。

4 分層策略

由于只計(jì)算了關(guān)系相對(duì)緊密的頂點(diǎn)之間的斥力，這可能會(huì)導(dǎo)致關(guān)聯(lián)不緊密的頂點(diǎn)被布局到非常近的位置，雖然這樣的概率很低，這種情況會(huì)通過(guò)分層布局的方式進(jìn)一步降低這種情況的發(fā)生概率。

分層策略采用O DL（out degree layout）算法[12]，ODL算法是Chan提出的一種基于力導(dǎo)引算法的變種算法，并針對(duì)冪率分布的網(wǎng)絡(luò)提出了分層算法，比較適合于社交網(wǎng)絡(luò)。

ODL算法如下：首先對(duì)圖節(jié)點(diǎn)按照出度分類，將節(jié)點(diǎn)劃分到不同的層級(jí)L1…LM，然后從出度最大的一層開(kāi)始布局，將頂點(diǎn)不斷地加入上一層中，最終形成完整的布局結(jié)果。只要保證最初的第一級(jí)節(jié)點(diǎn)構(gòu)成的圖能夠近似地反映圖的整體結(jié)構(gòu)，那么后面全部節(jié)點(diǎn)的調(diào)整過(guò)程將會(huì)大大縮短，同時(shí)也會(huì)使得不相關(guān)的頂點(diǎn)不被放置到相近的位置。這是因?yàn)椴幌嚓P(guān)的頂點(diǎn)往往都會(huì)與不同的上層頂點(diǎn)有關(guān)系，所以會(huì)被放置在不同的上層頂點(diǎn)附近，而對(duì)于上層頂點(diǎn)可以采用精確的計(jì)算。因此，不同的上層頂點(diǎn)位置不會(huì)太近。ODL算法在計(jì)算第一層的時(shí)候會(huì)使用傳統(tǒng)的力導(dǎo)向算法，后面各層的計(jì)算采用改進(jìn)的力導(dǎo)向算法。ODL算法如下。

5 并行的近似計(jì)算力導(dǎo)向布局算法

雖然進(jìn)行了上面提到的種種優(yōu)化，但是面對(duì)目前數(shù)百萬(wàn)頂點(diǎn)的數(shù)據(jù)還是顯得力不從心，因此筆者使用分布式并行計(jì)算的方法進(jìn)一步提升算法的計(jì)算能力。關(guān)于大數(shù)據(jù)的并行計(jì)算模型有很多，如MapReduce模型和大塊同步模型（BSP模型）。本文使用BSP編程模型進(jìn)行編碼。

主要過(guò)程如下。

步驟1 找到每個(gè)頂點(diǎn)的n階鄰居，并將其存儲(chǔ)在頂點(diǎn)的friendSet中。

步驟2 將處理好的頂點(diǎn)數(shù)據(jù)分發(fā)到每一臺(tái)機(jī)器中，每臺(tái)機(jī)器會(huì)遍歷頂點(diǎn)數(shù)據(jù)。對(duì)于每一個(gè)頂點(diǎn)，將其位置發(fā)送給其friendSet中的頂點(diǎn)。

步驟3 每一個(gè)頂點(diǎn)在收到其friendSet中的頂點(diǎn)給自己發(fā)送來(lái)的位置后，算出自己與這個(gè)頂點(diǎn)的距離，然后判斷這個(gè)頂點(diǎn)是不是與自己有邊的頂點(diǎn)，如果是，則計(jì)算引力和斥力；如果不是，則只計(jì)算斥力，然后根據(jù)引力和斥力的合力，調(diào)整自己的位置，再次將自己的新位置發(fā)送給friendSet中的頂點(diǎn)。

步驟4 重復(fù)步驟3，直到達(dá)到迭代次數(shù)，或者整個(gè)系統(tǒng)趨于穩(wěn)定。

圖2 100個(gè)節(jié)點(diǎn)布局情況

圖3 1000個(gè)節(jié)點(diǎn)布局情況

基于pregel模型的k-friend布局算法（pk-friend布局算法）的偽代碼如下。

6 性能測(cè)試

本文算法分為單機(jī)和并行兩個(gè)版本。單機(jī)版本采用Java語(yǔ)言編寫(xiě)，測(cè)試環(huán)境為：I7處理器，8 GB內(nèi)存。并行版本采用Scala語(yǔ)言編寫(xiě)，測(cè)試環(huán)境為40臺(tái)高性能計(jì)算機(jī)組成的小型集群，具體配置為Intel-酷睿I7 CPU，8 GB內(nèi)存，Spark1.41版本分布式并行計(jì)算平臺(tái)，Hadoop2.6版本。

對(duì)于單機(jī)版本，筆者測(cè)試了100個(gè)節(jié)點(diǎn)的圖數(shù)據(jù)和1000個(gè)節(jié)點(diǎn)的平均出度為5的生成圖數(shù)據(jù)。布局效果如圖2和圖3所示。

效果基本與傳統(tǒng)力導(dǎo)向算法無(wú)異，其差別人眼很難分辨，因此筆者制定了量化的指標(biāo)對(duì)兩種算法進(jìn)行了對(duì)比。因?yàn)樵诖髨D數(shù)據(jù)分析的情況下，布局的目的是令鄰居節(jié)點(diǎn)位置盡量近，非鄰居節(jié)點(diǎn)之間的距離盡量遠(yuǎn)，并且忽略關(guān)系不緊密的頂點(diǎn)之間的位置關(guān)系，所以定義可視化質(zhì)量度量指標(biāo)Q如式（1）所示。

其中，E是相互之間存在邊的頂點(diǎn)對(duì)的集合，F(xiàn)是頂點(diǎn)與它的friendSet中的點(diǎn)分別組成的頂點(diǎn)對(duì)的集合。式（1）中，分母表示有邊的頂點(diǎn)之間的平均距離，分子表示每個(gè)頂點(diǎn)與其friendSet中頂點(diǎn)之間的平均距離，因此，Q值越大說(shuō)明布局效果越好。

通過(guò)隨機(jī)生成的圖數(shù)據(jù)對(duì)比了本文提出的k-friend布局算法和FR算法的性能。參數(shù)設(shè)置為：迭代次數(shù)為200次，退火函數(shù)為tn=0.95×tn-1，t1=140，深度值n為3，k為1000。

從圖4和圖5可以看出，本文算法與FR算法在布局質(zhì)量上的差距大概只有1%，幾乎可以忽略不計(jì)，而在計(jì)算時(shí)間上，本文算法有壓倒性的優(yōu)勢(shì)，尤其是在頂點(diǎn)數(shù)多的情況下，與頂點(diǎn)數(shù)目成線性關(guān)系，并且斜率也較小。

直觀上，本文提出的k-friend布局算法中的friendset的大小對(duì)算法的性能是有影響的，當(dāng)k等于圖的頂點(diǎn)數(shù)時(shí)，就與FR算法等效，當(dāng)k較小時(shí)，算法的速度會(huì)很快，但是算法的布局質(zhì)量就會(huì)下降。k又與考慮的鄰居的深度層數(shù)n有關(guān)。因此，本文測(cè)試了n值對(duì)布局結(jié)果的影響，使用爬取到的微博轉(zhuǎn)發(fā)信息對(duì)算法進(jìn)行測(cè)試。微博是小米手機(jī)在2015年1月7日發(fā)布的其將在1月15日舉辦產(chǎn)品發(fā)布會(huì)的一條微博，微博地址：http://weibo.com/2202387347/BEp EoDfJf?type=repost&retcode=6102#_ rnd1470800271407。布局效果如圖6所示，每一條邊代表一次轉(zhuǎn)發(fā)，每一個(gè)頂點(diǎn)代表一個(gè)轉(zhuǎn)發(fā)的人。

可以看到，隨著n的減少，由于斥力計(jì)算被減少了，會(huì)使得關(guān)系不緊密的頂點(diǎn)相對(duì)近一些，具體n如何選擇，要根據(jù)用戶的具體需求來(lái)確定。

對(duì)于并行算法的可擴(kuò)展性，本文設(shè)計(jì)節(jié)點(diǎn)數(shù)增加時(shí)算法的計(jì)算時(shí)間變化情況。使用爬取到的網(wǎng)站鏈接圖，頂點(diǎn)數(shù)為201582，邊數(shù)為230425。輸入?yún)?shù)為迭代次數(shù)為50次，退火函數(shù)為tn=0.95×tn-1，t1=140（即第一次迭代時(shí)的最大位移量，與tn=0.95×tn-1對(duì)應(yīng)），n=5。

從圖7可以看到，隨著處理器核數(shù)的增加，計(jì)算時(shí)間減少。

圖4 質(zhì)量對(duì)比

圖5 時(shí)間對(duì)比

圖6 布局算法性能對(duì)比

圖7 分布式版本性能測(cè)試

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

本文提出了k-friend布局算法，通過(guò)只計(jì)算關(guān)聯(lián)緊密頂點(diǎn)之間的斥力，使得在犧牲少量布局質(zhì)量的情況下，大幅度提升計(jì)算效率，同時(shí)也使得該算法的并行化成為了可能。使用分層的策略，既降低了不相鄰頂點(diǎn)被放置到相近位置的可能性，又提升了算法的執(zhí)行效率，而且采用這種策略可以使用戶在比較短的時(shí)間內(nèi)看到較概括的上層布局，在用戶觀察上層布局的同時(shí)，計(jì)算詳細(xì)的下層布局，提升了用戶體驗(yàn)。最后，使用分布式計(jì)算框架BSP框架實(shí)現(xiàn)了k-friend布局算法的并行算法，使得圖布局算法真正地可以處理海量的圖數(shù)據(jù)。

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，本文提出的算法無(wú)論是在處理速度上還是處理的數(shù)據(jù)量上，都優(yōu)于現(xiàn)有的其他算法，并能夠有效地對(duì)社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行可視化分析。

[1] QUIGLEY A, EADES P.FADE: graph drawing, clustering, and visual abstraction[C]//The 8th Symposium on Graph Drawing, September 20-23, 2000, Colonial Williamsburg, VA, USA.London: Springer-Verlag, 2000: 197-210.

[2] REINGOLD E.Graph drawing by forcedirected placement[J].Software: Practice and Experience, 1991, 21(11): 1129-1164.

[3] HU Y F.Efficient and high quality forcedirected graph drawing[J].Mathematica Journal, 2005, 10(6): 37-71.

[4] HADANY R, HAREL D.A multi-scale algorithm for drawing graphs nicely[J].Discrete Applied Mathematics, 2001, 113(1) : 3-21.

[5] KAMADA T, KAWAI S.An algorithm for drawing general undirected graphs[J].Information Processing Letters, 1989, 31(1) : 7-15.

[6] GAJER P, GOODRICH M T, KOBOUROV S G.A fast multi-dimensional algorithmfor drawing large graphs[J].Computational Geometry: Theory and Applications, 2004, 29(1) : 3-18.

[7] BREITKREUTZ B J, STARK C, TYERS M.Osprey: a network visualization system[J].Genome Biology, 2003, 4(3) : 22-24.

[8] ELMQVIST N, DO T N, GOODELL H, et al.ZAME: interactive large scale graph visualization[C]//IEEE Pacific Visualization Symposium, March 5-7, 2008, Kyoto, Japan.New Jersey: IEEE Press, 2008: 215-222.

[9] BECKER R A, EICK S G, WILKS A R.Visualizing network data[J].IEEE Trans on Visualization and Computer Graphics, 1995, 1(1): 16-28.

[10] TIKHONOVA A, MA K L.A scalable parallel force-directed graph layout algorithm[C]// Eurographics Conference on Parallel Graphics and Visualization, April 14-15, 2008, Crete, Greece.New York: ACM Press, 2008: 25-32.

[11] JACOMY M, VENTURINI T, HEYMANN S, et al.ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the gephi software[J].Plos One, 2014, 9(6): e98679.

[12] CHAN S M, CHUA K S, LECKIE C, et al.Visualisation of power-law network topologies[C]// The 11th IEEE International Conference on Networks(ICON2003), September 28-October 1, 2003, Sydney, NSW, Australia.New Jersey: IEEE Press, 2003: 69-74.

Parallel graph layout algorithm for large-scale graph data

CHENG Zhiyuan, BAO Yubin, LENG Fangling
Department of Computer Science of Northeastern University, Shenyang 110819, China

Graph models are modeling tools which are widely used.Data visualization techniques have been widely used as intuitive data analysis tools.Graph layout algorithm is the most critical technique of graph visualization, while there are no effective parallel graph layout algorithms.So to study on visualization of massive graph data is a challenging problem.Aiming at this problem, based on the force-directed layout algorithm and ignoring the repulsion force computation between weakly associated vertexes partially, a k-friend approximate layout algorithm was proposed, and an effective parallel layout algorithm was designed for massive graph data.The experimental results on artificial and real dataset show that the algorithms proposed greatly improve the layout speed.

force-directed algorithm, visualization analysis, social network, parallel layout algorithm

TP391

A

10.11959/j.issn.2096-0271.2016050

程致遠(yuǎn)（1991-），男，東北大學(xué)計(jì)算機(jī)科學(xué)系碩士生，主要研究方向?yàn)樵朴?jì)算、數(shù)據(jù)可視化。

鮑玉斌（1968-），男，博士，東北大學(xué)計(jì)算機(jī)科學(xué)系教授，主要研究方向?yàn)槁?lián)機(jī)分析處理、云計(jì)算、圖數(shù)據(jù)管理等。

冷芳玲（1978-），女，博士，東北大學(xué)計(jì)算機(jī)科學(xué)系講師，主要研究方向?yàn)榇髷?shù)據(jù)分析、數(shù)據(jù)可視化。

2016-08-10

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61433008）

Foundation Item: The National Natural Science Foundation of China(No.61433008)