時(shí)生樂(lè)，趙宇海，李 源，印 瑩，王國(guó)仁

東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110819

1 引言

圖模型強(qiáng)大的表達(dá)能力，使其在社交、化學(xué)、生物等領(lǐng)域有著廣泛的應(yīng)用，例如在社交領(lǐng)域，使用圖模型進(jìn)行建模，將數(shù)據(jù)用一個(gè)圖來(lái)表示，圖中的頂點(diǎn)表示個(gè)體，邊表示個(gè)體與個(gè)體之間的關(guān)系。隨著圖應(yīng)用的不斷增長(zhǎng)，人們對(duì)圖數(shù)據(jù)分析和管理中的基本問(wèn)題進(jìn)行了大量研究，其中發(fā)現(xiàn)聚類或社區(qū)結(jié)構(gòu)是圖數(shù)據(jù)分析中最重要的任務(wù)之一，通過(guò)發(fā)現(xiàn)數(shù)據(jù)中潛在的結(jié)構(gòu)，人們可以從海量數(shù)據(jù)中提煉出有價(jià)值的信息。例如在社交網(wǎng)絡(luò)中，通過(guò)對(duì)社交網(wǎng)絡(luò)進(jìn)行聚類分析，可以找到網(wǎng)絡(luò)中的社區(qū)，進(jìn)而可以分析社區(qū)中人們的行為并向?qū)υ撋鐓^(qū)感興趣的人推薦社區(qū)。

在當(dāng)前文獻(xiàn)中，已經(jīng)提出各種各樣的圖聚類算法，例如基于模塊性的圖聚類算法[1]、k-core算法[2]、kedge算法[3]、k-truss算法[4]、譜聚類算法[5]和局部密集子圖發(fā)現(xiàn)算法[6]等。然而上面這些算法都不能區(qū)分一個(gè)圖中頂點(diǎn)的不同角色，而對(duì)圖中頂點(diǎn)的角色進(jìn)行區(qū)分在現(xiàn)實(shí)中有重要應(yīng)用。為了能夠區(qū)分圖中頂點(diǎn)的不同角色，Xu等人第一次提出結(jié)構(gòu)化圖聚類算法[7]。該算法使用圖中頂點(diǎn)之間公共鄰居作為聚類條件對(duì)圖進(jìn)行聚類，并且同時(shí)將圖中的頂點(diǎn)分為聚類中的點(diǎn)、中心點(diǎn)、離群點(diǎn)3類。其中，聚類中的點(diǎn)指算法找出的每個(gè)簇中的頂點(diǎn)，中心點(diǎn)指橫跨兩個(gè)及兩個(gè)以上聚類的頂點(diǎn)，離群點(diǎn)指除聚類中的頂點(diǎn)和中心點(diǎn)之外的其他頂點(diǎn)。例如在圖1中，通過(guò)結(jié)構(gòu)化圖聚類算法找到圖中的兩個(gè)聚類：由頂點(diǎn)v1～v8組成的聚類1，頂點(diǎn)v10～v15組成的聚類2（分別用虛線圈出）；同時(shí)也找到了連接聚類1和聚類2的中心點(diǎn)v9和離群點(diǎn)v16、v17、v18。

結(jié)構(gòu)化圖聚類在實(shí)際生活中有重要應(yīng)用。例如，如果將圖1看作用于傳染疾病防控的圖數(shù)據(jù)，圖中的每個(gè)頂點(diǎn)表示一個(gè)人，頂點(diǎn)之間的連線代表人與人之間的接觸關(guān)系。在傳染疾病爆發(fā)時(shí)，如果能夠找到連接群體之間的關(guān)鍵人物（例如頂點(diǎn)v9），并對(duì)其隔離，就能夠有效阻止傳染疾病在群體之間進(jìn)行傳播，對(duì)疾病的防控具有重要意義。

Fig.1 Structural graph clustering圖1 結(jié)構(gòu)化圖聚類

本文通過(guò)對(duì)結(jié)構(gòu)化圖聚類中頂點(diǎn)間相似性定義和基于Hadoop[8]的MapReduce分布式結(jié)構(gòu)化圖聚類算法進(jìn)行分析，提出一種基于GraphX[9]的分布式結(jié)構(gòu)化圖聚類算法。

本文主要貢獻(xiàn)如下：

（1）通過(guò)對(duì)結(jié)構(gòu)化相似性定義的分析，找到一種減少圖中頂點(diǎn)之間結(jié)構(gòu)化相似性計(jì)算數(shù)量的削減策略；

（2）通過(guò)對(duì)結(jié)構(gòu)化相似性計(jì)算過(guò)程的分析，提出一種通過(guò)非精確計(jì)算頂點(diǎn)之間相似性來(lái)確定頂點(diǎn)之間是否相似的方法；

（3）通過(guò)發(fā)現(xiàn)現(xiàn)有分布式結(jié)構(gòu)化圖聚類算法在計(jì)算過(guò)程中需要大量磁盤I/O開銷的不足，提出一種基于GraphX的結(jié)構(gòu)化圖聚類算法消除計(jì)算過(guò)程中的磁盤I/O開銷。

本文剩余部分組織如下：第2章闡述和分析了分布式圖聚類的相關(guān)工作；第3章對(duì)分布式結(jié)構(gòu)化圖聚類問(wèn)題和相關(guān)概念進(jìn)行定義；第4章詳細(xì)闡述本文提出的基于GraphX的結(jié)構(gòu)化圖聚類算法；第5章通過(guò)對(duì)比實(shí)驗(yàn)分析算法的效率和可擴(kuò)展性；第6章對(duì)全文進(jìn)行總結(jié)。

2 相關(guān)工作

近年來(lái)，隨著社交網(wǎng)絡(luò)、生物、醫(yī)學(xué)等領(lǐng)域的快速發(fā)展，產(chǎn)生大量大規(guī)模圖數(shù)據(jù)集，由于內(nèi)存限制，使得傳統(tǒng)基于單機(jī)的圖聚類算法[1,7,10]已經(jīng)不能夠處理這些大規(guī)模圖數(shù)據(jù)集，因此基于分布式的圖聚類算法不斷出現(xiàn)。

分布式的圖聚類算法[11-12]主要思想是將圖數(shù)據(jù)集按照一定規(guī)則分布到集群的各個(gè)結(jié)點(diǎn)上，然后在各個(gè)結(jié)點(diǎn)處理一部分?jǐn)?shù)據(jù)集，在計(jì)算過(guò)程中只涉及結(jié)點(diǎn)間的網(wǎng)絡(luò)通信，不需要磁盤I/O開銷，且可以根據(jù)數(shù)據(jù)集的規(guī)模任意添加機(jī)器，可擴(kuò)展性好，理論上可以處理任意規(guī)模的數(shù)據(jù)集。因此開發(fā)分布式的圖聚類算法是圖挖掘研究的重點(diǎn)之一。

由于結(jié)構(gòu)化圖聚類算法能夠識(shí)別出頂點(diǎn)的不同角色，因此在圖分析中扮演著重要角色，文獻(xiàn)[13]是目前最具代表性的圖聚類算法之一，但是該算法存在大量磁盤I/O開銷和大量精確計(jì)算頂點(diǎn)之間結(jié)構(gòu)化相似性等問(wèn)題。

隨著分布式計(jì)算技術(shù)的快速發(fā)展，目前已經(jīng)出現(xiàn)了以Hadoop[8]和Spark[14]為代表的分布式系統(tǒng)，并在商業(yè)和研究中得到廣泛應(yīng)用。Hadoop具有高可靠、高擴(kuò)展、高容錯(cuò)等優(yōu)點(diǎn)，是目前商業(yè)領(lǐng)域使用最多的分布式系統(tǒng)之一。但Hadoop也有磁盤I/O開銷大、對(duì)圖計(jì)算和迭代計(jì)算支持不好等缺點(diǎn)。Spark是一個(gè)開源的分布式內(nèi)存計(jì)算框架，GraphX是Spark上的一個(gè)專門用來(lái)進(jìn)行圖計(jì)算的彈性分布式圖系統(tǒng)。GraphX通過(guò)Spark將數(shù)據(jù)并行和圖并行有效結(jié)合起來(lái)，極大提高了圖計(jì)算的存儲(chǔ)和執(zhí)行效率，且GraphX中內(nèi)置許多對(duì)圖進(jìn)行計(jì)算的原子操作，極大地方便圖計(jì)算應(yīng)用程序的開發(fā)。和Hadoop相比，Spark對(duì)迭代計(jì)算和圖計(jì)算的支持更加好，而在圖計(jì)算中像kcore、PageRank[15]等許多算法都需要迭代計(jì)算，這使得基于GraphX實(shí)現(xiàn)的圖算法執(zhí)行效率將會(huì)得到極大提升。

3 問(wèn)題描述

3.1 相關(guān)定義

本研究主要聚焦于無(wú)向無(wú)權(quán)重圖G=(V,E)，其中V表示圖G中所有頂點(diǎn)的集合，E表示圖G中所有邊的集合，用|V|=n表示圖中頂點(diǎn)個(gè)數(shù)，|E|=m表示圖中邊的條數(shù)，(v,w)∈E表示兩個(gè)端點(diǎn)為v和w的邊，Nv、Nw分別表示頂點(diǎn)v和w鄰居頂點(diǎn)的集合。

定義1（結(jié)構(gòu)化鄰居）對(duì)于圖G中任意一個(gè)頂點(diǎn)v∈V，頂點(diǎn)v的結(jié)構(gòu)化鄰居定義為：H[v]={w|(v,w)∈E}?{v}。

例如，在圖2中頂點(diǎn)v6的結(jié)構(gòu)化鄰居為H[v6]={v4,v5,v6,v7,v8,v11}，頂點(diǎn)v7的結(jié)構(gòu)化鄰居為H[v7]={v6,v7,v8,v9,v10,v11}。

Fig.2 Simple example圖2 一個(gè)簡(jiǎn)單示例

定義2（結(jié)構(gòu)化相似性）對(duì)于圖G中任意兩個(gè)頂點(diǎn)v，w∈V，頂點(diǎn)v、w的結(jié)構(gòu)化相似性定義為：

其中，|H[v]|、|H[w]|分別表示頂點(diǎn)v和w的結(jié)構(gòu)化鄰居的個(gè)數(shù)。

例如在圖2中，頂點(diǎn)v6和頂點(diǎn)v7的結(jié)構(gòu)化相似性為：

給定一個(gè)相似性閾值ε(0<ε≤1)，如果頂點(diǎn)v和頂點(diǎn)w的相似性閾值δ(v,w)≥ε，則稱頂點(diǎn)v和頂點(diǎn)w是相似的。例如在圖2中，設(shè)定相似性閾值為ε=0.8，頂點(diǎn)v6和v7相似性為δ(v6,v7)=2/3=0.667<0.8，因此頂點(diǎn)v5和v6不相似；頂點(diǎn)v4和v5相似性為δ(v4,，因此頂點(diǎn)v4和v5相似。

3.2 基于MapReduce的算法

現(xiàn)有分布式結(jié)構(gòu)化圖聚類算法[13]（parallel structural clustering algorithm for big networks，PSCAN）的主要思想是給定一個(gè)用鄰接列表表示的無(wú)向、無(wú)權(quán)重圖和一個(gè)相似性閾值ε(0<ε≤1)，返回圖中所有的聚類；該算法首先根據(jù)頂點(diǎn)的鄰接列表計(jì)算圖中所有鄰接頂點(diǎn)對(duì)之間的結(jié)構(gòu)化相似性，然后去掉圖中相似性小于給定閾值ε的頂點(diǎn)對(duì)之間的邊，最后找到圖中所有的連通分量，每個(gè)連通分量就是所要找的聚類，具體算法如算法1所示。

算法1PSCAN算法

輸入：一個(gè)由鄰接列表表示的圖G(V,E)，一個(gè)相似性閾值ε(0<ε≤ 1)。

輸出：圖G中所有聚類的集合。

1.Mapper階段：

2.for圖中每個(gè)頂點(diǎn)v∈Vdo

3.for頂點(diǎn)v的每個(gè)鄰居頂點(diǎn)vido

4. ifID(v)

5. 取(ID(v),ID(vi))作為key；

6. else

7. 取(ID(vi),ID(v))作為key；

8. end if；

9. 取頂點(diǎn)v的鄰居Nv作為value；

10. 發(fā)送鍵值對(duì)(key,value)；

11.end for；

12.end for；

13.Reducer階段：

14.得到從Mapper階段發(fā)送的鍵值對(duì)；

15.for每一個(gè)key相同的兩個(gè)鍵值對(duì)do

16.計(jì)算這兩個(gè)頂點(diǎn)的相似性e；

17.end for；

18.for圖中的每條邊(v,w)do

19.if頂點(diǎn)v、w的相似性e<εthen

20. 移除邊(v,w)；

21.end if；

22.end for；

23.計(jì)算連通分量；

PSCAN算法偽代碼如算法1所示，在Mapper階段（行1～12），計(jì)算每個(gè)頂點(diǎn)和它們的每個(gè)鄰居組成的鍵值對(duì)，使用ID(v)、ID(vi)的升序作為key（行4～8），使用頂點(diǎn)v的鄰居作為value；在Reducer階段（行13～22），計(jì)算每條邊(v,w)兩個(gè)端點(diǎn)的相似性e，如果e<ε（說(shuō)明兩個(gè)頂點(diǎn)不相似），移除邊(v,w)（行19～21），最后計(jì)算圖中的連通分量（行23）。算法使用標(biāo)記傳播算法來(lái)求連通分量，求得連通分量的集合就是最終的聚類結(jié)果。

上面算法產(chǎn)生大量的磁盤I/O開銷，且算法需要精確計(jì)算圖中所有鄰接頂點(diǎn)對(duì)之間的相似性，降低了算法的執(zhí)行效率。該算法除了執(zhí)行效率較低外，存在的另一個(gè)問(wèn)題是算法不能夠去掉只有少量頂點(diǎn)組成的聚類（例如有少量頂點(diǎn)組成的clique[16]），因?yàn)橹挥猩倭宽旤c(diǎn)組成的聚類在圖分析中沒(méi)有什么意義，所以這樣的聚類不應(yīng)包含在最終結(jié)果中。例如在圖1中，使用該算法將找到聚類1、聚類2和由頂點(diǎn)v17和頂點(diǎn)v18組成的聚類，因?yàn)楦鶕?jù)相似性定義可知，只有兩個(gè)頂點(diǎn)組成的聚類頂點(diǎn)之間的相似性恒為1，所以無(wú)論ε值為多大，只有兩個(gè)頂點(diǎn)組成的聚類始終包含在最終結(jié)果中，降低了算法的準(zhǔn)確性。

4GXDSGC算法

針對(duì)第3章PSCAN算法存在產(chǎn)生大量I/O開銷等不足，本文提出一種基于GraphX的分布式結(jié)構(gòu)化圖聚類算法GXDSGC（GraphX-based distributed structural graph clustering algorithm），該算法能夠很好解決上述問(wèn)題。給定一個(gè)無(wú)向無(wú)權(quán)重圖、一個(gè)相似性閾值ε(0<ε≤1)和聚類中頂點(diǎn)的最小個(gè)數(shù)minNum，GXDSGC算法找到圖中所有聚類和由中心點(diǎn)和離群點(diǎn)組成的頂點(diǎn)的集合。下面介紹算法中用到的兩個(gè)削減規(guī)則。

4.1 削減規(guī)則1

在現(xiàn)有的PSCAN算法中是計(jì)算圖中所有邊所關(guān)聯(lián)的頂點(diǎn)之間的相似性，頂點(diǎn)之間相似性的計(jì)算在整個(gè)算法中是一個(gè)比較耗時(shí)的操作，如果能夠減少圖中頂點(diǎn)之間相似性的計(jì)算量就會(huì)大大增加算法的執(zhí)行效率。通過(guò)對(duì)頂點(diǎn)之間相似性定義進(jìn)行分析后，得到下面的削減規(guī)則。

引理1對(duì)于一個(gè)給定的相似性閾值ε(0<ε≤1)和兩個(gè)頂點(diǎn)v和w，如果|Η[v]|<|Η[w]|×ε2或|Η[w]|<|Η[v]|×ε2，那么頂點(diǎn)v和w不相似。

證明因?yàn)閨Η[v]|<|Η[w]|×ε2，所以

即δ(v,w)<ε，所以頂點(diǎn)v和w不相似；同理當(dāng)|Η[w]|<|Η[v]|×ε2時(shí)，δ(v,w)<ε。

因此當(dāng) |Η[v]|<|Η[w]|×ε2或|Η[w]|<|Η[v]|×ε2時(shí)，頂點(diǎn)v和w不相似。 □

利用上面的削減規(guī)則，得到下面判斷兩個(gè)頂點(diǎn)不相似的算法。

算法2disSimWithPrune算法

輸入：頂點(diǎn)v和w的結(jié)構(gòu)化鄰居Η[v]和Η[w]，一個(gè)相似性閾值ε(0<ε≤1)。

輸出：如果不相似輸出true，否則輸出false。

1.if(|Η[v]|<|Η[w]|×ε2or|Η[w]|<|Η[v]|×ε2)

2.returntrue

3.else

4.returnfalse

該算法使用引理1來(lái)判斷兩個(gè)頂點(diǎn)不相似，如果兩個(gè)頂點(diǎn)v和w滿足引理1中的條件，則頂點(diǎn)v和w一定不相似，輸出true，否則不能確定這兩個(gè)頂點(diǎn)是否相似輸出false。

4.2 削減規(guī)則2

計(jì)算圖中頂點(diǎn)之間相似性的目的是判斷這兩個(gè)頂點(diǎn)是否相似，根據(jù)定義需要計(jì)算這兩個(gè)頂點(diǎn)公共鄰居的個(gè)數(shù)，在給定相似性閾值ε(0<ε≤1)時(shí)，如果能夠找到使得這兩個(gè)頂點(diǎn)相似的最小公共鄰居的數(shù)目，這樣在求公共鄰居數(shù)目時(shí)，一旦公共鄰居的個(gè)數(shù)大于使得頂點(diǎn)之間相似的最小公共鄰居的數(shù)目，就不需要再往下計(jì)算其他的公共鄰居。為了實(shí)現(xiàn)上述思想，本文給出下面的引理。

引理2對(duì)于一個(gè)給定的相似性閾值ε(0<ε≤1)和頂點(diǎn)v和w的結(jié)構(gòu)化鄰居Η[v]和Η[w]，設(shè)mincount(v,w)為大于等于的最小整數(shù)，即那么頂點(diǎn)v和w相似的充要條件是|Η[v]∩Η[w]|≥(v,w)。

利用引理2，算法3給出在不精確計(jì)算兩個(gè)頂點(diǎn)相似性的情況下，確定兩個(gè)頂點(diǎn)是否相似的算法。

算法3isSim算法

輸入：頂點(diǎn)v和w的鄰居Nv和Nw，用Nv[i]表示頂點(diǎn)v的第i+1個(gè)鄰居（其中Nv和Nw中的頂點(diǎn)按照頂點(diǎn)標(biāo)號(hào)的升序排列），一個(gè)相似性閾值ε(0<ε≤1)。

輸出：如果頂點(diǎn)v和w相似，輸出true，否則輸出false。

3.counter=2；/*記錄已求公共鄰居的個(gè)數(shù)*/

4.i=0；j=0；/*指示數(shù)組下標(biāo)*/

5.dv=Nv.length；dw=Nw.length；

6.whilecounter

7.if(Nv[i]

8.dv=dv-1；i=i+1；

9.else if(Nv[i]>Nw[j])then

10.dw=dw-1；

11.j=j+1；

12.else

13.counter=counter+1；

14.i=i+1；

15.j=j+1；

16.end if

17.end while

18.if(counter

19.returnfalse；

20.else

21.returntrue；

22.end if；

算法3中，首先求出使得頂點(diǎn)v和w相似的最小結(jié)構(gòu)化公共鄰居的個(gè)數(shù)（行1～2）；然后定義記錄已求結(jié)構(gòu)化公共鄰居個(gè)數(shù)的變量counter，因?yàn)樗惴▊魅氲氖琼旤c(diǎn)v和w的鄰居頂點(diǎn)，算法后面只是求頂點(diǎn)間公共鄰居的個(gè)數(shù)，并沒(méi)包含頂點(diǎn)v和w本身，而算法是求結(jié)構(gòu)化鄰居的公共頂點(diǎn)個(gè)數(shù)，因此初始化為2（行3）；接著初始化指示數(shù)組的下標(biāo)i=0，j=0（行4）；定義兩個(gè)鄰接列表中除已比較的不相等的鄰接頂點(diǎn)后剩余的頂點(diǎn)的個(gè)數(shù)，初始化為對(duì)應(yīng)兩個(gè)鄰接列表中元素的個(gè)數(shù)（行5）；在while循環(huán)中求結(jié)構(gòu)化公共鄰居的個(gè)數(shù)（行6～17），當(dāng)求得的結(jié)構(gòu)化公共鄰居的個(gè)數(shù)大于等于mincount或者除已比較的不相等的鄰接頂點(diǎn)后剩余的頂點(diǎn)的個(gè)數(shù)du，dv的最小值小于使得兩個(gè)頂點(diǎn)結(jié)構(gòu)化相似的最小結(jié)構(gòu)化公共鄰居的最小個(gè)數(shù)時(shí)，沒(méi)有必要再求后面的公共鄰居，直接跳出while循環(huán)；最后，判斷已求的結(jié)構(gòu)化公共鄰居數(shù)counter是否小于mincount，如果小于說(shuō)明兩個(gè)頂點(diǎn)不相似，返回false，否則兩個(gè)頂點(diǎn)相似，返回true（行19～22）。

4.3 連通分量計(jì)算

在計(jì)算圖中的每個(gè)連通分量時(shí)，本文使用Pregel框架[17]來(lái)分布式計(jì)算圖中所有的連通分量。Pregel將計(jì)算過(guò)程分為一個(gè)個(gè)超步，計(jì)算開始時(shí)標(biāo)記所有頂點(diǎn)為活動(dòng)狀態(tài)。在每個(gè)超步中，每個(gè)頂點(diǎn)接受上一個(gè)超步發(fā)送給它的消息后進(jìn)行處理并更新當(dāng)前頂點(diǎn)的狀態(tài)，更新后當(dāng)前頂點(diǎn)仍為活動(dòng)狀態(tài)則將處理后的結(jié)果發(fā)送給下一個(gè)超步，否則該頂點(diǎn)什么也不做，當(dāng)前超步中每個(gè)頂點(diǎn)都處理完成后進(jìn)入下一個(gè)超步，當(dāng)所有頂點(diǎn)都處于非活動(dòng)狀態(tài)時(shí)算法結(jié)束。下面通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)介紹使用Pregel計(jì)算連通分量的過(guò)程。

如圖3所示，例如，要求值為1、2、3、4的4個(gè)頂點(diǎn)組成的連通分量，白色頂點(diǎn)表示該頂點(diǎn)處于活動(dòng)狀態(tài)，灰色頂點(diǎn)表示該頂點(diǎn)處于非活動(dòng)狀態(tài)，實(shí)線表示頂點(diǎn)之間的邊，虛線表示向下一個(gè)超步中的頂點(diǎn)發(fā)送的消息。初始時(shí)4個(gè)頂點(diǎn)都處于活躍狀態(tài)，因此在超步0中，每個(gè)頂點(diǎn)都向它的鄰居發(fā)送自己的當(dāng)前值，在超步1中，每個(gè)頂點(diǎn)接受超步0發(fā)送過(guò)來(lái)的值，如果接收到的值的最大值比當(dāng)前頂點(diǎn)值大，則更新當(dāng)前值為接收的最大值，然后將該頂點(diǎn)標(biāo)記為活躍狀態(tài)并向鄰居頂點(diǎn)發(fā)送更新后的值，如果接收到的最大值比當(dāng)前頂點(diǎn)值小，則將該頂點(diǎn)標(biāo)記為非活躍狀態(tài)。例如，第一頂點(diǎn)收到的值為{2,3}，其中收到的最大值3大于當(dāng)前頂點(diǎn)，因此更新當(dāng)前頂點(diǎn)值為3，將該頂點(diǎn)標(biāo)記為活動(dòng)狀態(tài)并向下一個(gè)超步發(fā)送該頂點(diǎn)的當(dāng)前值，第4個(gè)頂點(diǎn)收到的值為3，小于當(dāng)前頂點(diǎn)的值4，標(biāo)記該頂點(diǎn)為非活動(dòng)狀態(tài)，超步2和超步1處理類似，最后在超步3中，由于所有頂點(diǎn)都成為非活動(dòng)狀態(tài)，因此算法結(jié)束，值相等的頂點(diǎn)在同一個(gè)連通分量中。

Fig.3 Computing connected component圖3 計(jì)算連通分量

4.4 完整算法描述

基于算法2、算法3、連通分量算法，下面給出基于GraphX的分布式結(jié)構(gòu)化圖聚類算法（GXDSGC）。

算法4GXDSGC算法

輸入：一個(gè)無(wú)向無(wú)權(quán)重圖G(V,E)，一個(gè)相似性閾值ε(0<ε≤1)，聚類中頂點(diǎn)的最小個(gè)數(shù)minNum。

輸出：圖G中所有的聚類的集合。

1.求出每個(gè)頂點(diǎn)的鄰居頂點(diǎn)；

2.將每個(gè)頂點(diǎn)的鄰居頂點(diǎn)作為該頂點(diǎn)的屬性值；

3.for在圖中的每個(gè)鄰接頂點(diǎn)對(duì)v,wdo

4.if(disSimWithPrune(Nv,Nw))then

5. (v,w).isSim=false；

6.else

7. (v,w).isSim=isSim(Nv,Nw)；

8. end if；

9.end for；

10.for(v,w)∈Edo

11.if((v,w).isSim=false)do

12.移除邊(v,w)；

13.end if；

14.end for；

15.計(jì)算圖G的連通分量；

16.for每個(gè)連通分量CCdo

17.ifCC.num

18. 移除CC；

19.end if；

20.end for；

基于GraphX的分布式結(jié)構(gòu)化圖聚類算法(GXDSGC)如算法4所示，算法首先使用GraphX中的兩個(gè)函數(shù)aggregateMessages和outerJoinVertices求出圖中每個(gè)頂點(diǎn)的鄰居頂點(diǎn)并將鄰居頂點(diǎn)作為該頂點(diǎn)的屬性值（行1～2）；然后對(duì)圖中的每個(gè)鄰接頂點(diǎn)對(duì)v,w求相似性（行3～9），在求相似性時(shí)，首先使用削減規(guī)則（算法2）判斷當(dāng)前頂點(diǎn)v,w是否不相似，如果不相似設(shè)置這兩個(gè)頂點(diǎn)間的相似性為false（行4～5），否則使用算法3來(lái)求這兩個(gè)頂點(diǎn)之間的相似性（行7）；接著移除圖中所有不相似的鄰接頂點(diǎn)對(duì)之間的邊，使用4.3節(jié)“連通分量算法”求得圖中所有的連通分量（行15）；然后刪除頂點(diǎn)個(gè)數(shù)小于指定閾值minNum的連通分量；最后求得的連通分量就是所要求的聚類。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)環(huán)境配置

本實(shí)驗(yàn)所用的軟硬件環(huán)境如下：集群由5臺(tái)服務(wù)器組成，每臺(tái)服務(wù)器的配置為：Red Hat 64位操作系統(tǒng)，16核CPU，主頻1.9 GHz，16 GB內(nèi)存，2 TB硬盤；Hadoop版本為2.6.0，Spark版本為1.6.0，Java版本為1.8.0，Scala版本為2.10.4。

開發(fā)環(huán)境配置：操作系統(tǒng)為Windows 732位旗艦版，主頻3.10 GHz，4 GB內(nèi)存，500 GB硬盤；開發(fā)工具IntelliJ IDEA Community Edition 15.0.2，Java版本為1.8.0，Scala版本為2.10.4。

5.2 實(shí)驗(yàn)所用數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集：本文使用DBLP、Youtube、LiveJournal 3個(gè)真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中，DBLP是一個(gè)作者協(xié)作網(wǎng)絡(luò)；Youtube是一個(gè)用戶到用戶鏈接網(wǎng)絡(luò)；LiveJournal是一個(gè)在線社交網(wǎng)絡(luò)。人工數(shù)據(jù)集使用文獻(xiàn)[18]中的算法生成。數(shù)據(jù)集統(tǒng)計(jì)信息如表1、表2所示。

Table 1 Real datasets表1 真實(shí)數(shù)據(jù)集

Table 2 Synthetic datasets表2 合成數(shù)據(jù)集

5.3 實(shí)驗(yàn)結(jié)果及分析

下面將本文中提出的GXDSGC算法和Zhao等人提出的PSCAN算法[13]進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)從運(yùn)行時(shí)間、削減策略和可擴(kuò)展性三方面來(lái)進(jìn)行比較。PSCAN算法和GXDSGC算法在相同配置的集群上運(yùn)行，因?yàn)镻SCAN算法并沒(méi)有指定聚類的最小尺寸，所以在實(shí)驗(yàn)中將GXDSGC算法的最小聚類尺寸設(shè)置為2，使得兩種算法的結(jié)果相同。下面分別從這三方面對(duì)GXDSGC算法進(jìn)行分析。

（1）運(yùn)行時(shí)間

在該實(shí)驗(yàn)中，對(duì)于不同數(shù)據(jù)集，在相似性閾值分別取0.6、0.7、0.8、0.9的情況下，分別運(yùn)行GXDSGC算法和PSCAN算法。算法在表1中數(shù)據(jù)集上的運(yùn)行時(shí)間如圖4所示。

從圖4中實(shí)驗(yàn)結(jié)果可以看出，在相似性閾值不斷增大情況下，兩個(gè)算法的運(yùn)行時(shí)間都逐漸減小，并且GXDSGC算法在4個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間比PSCAN算法快30多倍，說(shuō)明該算法和PSCAN算法相比是非常有效的。

GXDSGC算法速度比較快的原因主要有兩個(gè)：第一個(gè)是GXDSGC算法是基于GraphX的算法，當(dāng)集群的內(nèi)存足夠大時(shí)，數(shù)據(jù)在處理過(guò)程中整個(gè)數(shù)據(jù)都在內(nèi)存當(dāng)中，中間結(jié)果也是存儲(chǔ)在內(nèi)存的，避免了大量的磁盤I/O，節(jié)省了大量時(shí)間，而PSCAN在Hadoop集群中運(yùn)行時(shí)需要經(jīng)歷多個(gè)Mapper和Reducer階段，即使集群的內(nèi)存有足夠的空間，在每個(gè)階段都需要將中間結(jié)果存儲(chǔ)在磁盤中，在下一個(gè)階段從磁盤讀取中間結(jié)果，極大增加了磁盤I/O開銷，進(jìn)而增加了程序的運(yùn)行時(shí)間。第二個(gè)原因是GXDSGC算法在計(jì)算鄰接頂點(diǎn)之間相似性時(shí)，通過(guò)兩種削減策略來(lái)計(jì)算頂點(diǎn)之間的相似性，在不精確計(jì)算頂點(diǎn)間相似性的情況下，判斷出兩個(gè)頂點(diǎn)是否相似，進(jìn)一步減少了程序的運(yùn)行時(shí)間。

（2）削減策略

為了比較算法中兩個(gè)削減規(guī)則的有效性，在實(shí)驗(yàn)時(shí)，只記錄圖中頂點(diǎn)間相似性計(jì)算消耗的時(shí)間，對(duì)于每個(gè)數(shù)據(jù)集運(yùn)行5次算法，然后對(duì)消耗的時(shí)間求平均值，得到結(jié)果如圖5所示。

Fig.4 Running time圖4 運(yùn)行時(shí)間

從圖5中可以看出，對(duì)于每個(gè)數(shù)據(jù)集，使用削減規(guī)則和不使用削減規(guī)則相比，使用削減規(guī)則計(jì)算相似性所花費(fèi)時(shí)間明顯減少，說(shuō)明算法中削減規(guī)則確實(shí)減少了相似性計(jì)算消耗的時(shí)間。從圖5中還可以看出，對(duì)于每個(gè)數(shù)據(jù)集，隨著相似性閾值不斷增大，使用削減的算法運(yùn)行時(shí)間不斷減少，這是因?yàn)殡S著相似性閾值不斷增大，更多的相似性計(jì)算通過(guò)削減規(guī)則計(jì)算出來(lái)，說(shuō)明相似閾值越大，削減規(guī)則越有效。

為了進(jìn)一步比較算法中削減規(guī)則的有效性，下面實(shí)驗(yàn)使用表2中的合成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖6所示。

Fig.5 Pruning strategy圖5 削減策略

Fig.6 Pruning strategy on synthetic datasets圖6 合成數(shù)據(jù)集上的削減策略

首先，保持圖中邊條數(shù)不變，改變頂點(diǎn)個(gè)數(shù)，使用削減和不使用削減消耗時(shí)間如圖6(a)所示。然后，保持圖中頂點(diǎn)個(gè)數(shù)不變，改變邊的條數(shù)，使用削減和不使用削減消耗時(shí)間如圖6(b)所示。從圖6可以看出，無(wú)論是改變頂點(diǎn)個(gè)數(shù)還是改變邊條數(shù)，使用削減策略能夠明顯減少相似性計(jì)算所消耗的時(shí)間。從圖6(a)可以看出，隨著頂點(diǎn)個(gè)數(shù)增加，兩種算法消耗時(shí)間都不斷增大，但使用削減算法增幅較小，因?yàn)槭褂孟鳒p策略的算法能夠通過(guò)削減策略減少計(jì)算時(shí)間。從圖6(b)可以看出，在圖中頂點(diǎn)個(gè)數(shù)不變的情況下，隨著邊條數(shù)的增加，沒(méi)有使用削減策略計(jì)算相似性所消耗時(shí)間增加，而使用削減策略算法所消耗時(shí)間也增加但增幅較小，因?yàn)樵陧旤c(diǎn)個(gè)數(shù)不變的情況下，隨著邊數(shù)的增加，有更多相似性需要計(jì)算，所以增加了整個(gè)相似性計(jì)算時(shí)間；對(duì)于使用削減的算法，雖然有更多相似性需要計(jì)算，但是隨著邊數(shù)的增加，頂點(diǎn)鄰居個(gè)數(shù)會(huì)變大，就會(huì)有更多之前不能使用削減規(guī)則計(jì)算相似性的鄰接頂點(diǎn)能夠通過(guò)削減策略判斷其相似性，所以隨著邊條數(shù)的增加，計(jì)算相似性的時(shí)間雖然增加但增幅較小。從圖6還可以發(fā)現(xiàn)，一個(gè)圖越稠密，將會(huì)有更多的鄰接頂點(diǎn)能夠通過(guò)削減策略判斷其相似性，這樣削減策略就越有效，就能夠明顯減少算法在計(jì)算相似性時(shí)所消耗的時(shí)間，加快計(jì)算速度。

（3）可擴(kuò)展性

在該實(shí)驗(yàn)中，為了比較GXDSGC算法的可擴(kuò)展性，對(duì)于3個(gè)真實(shí)數(shù)據(jù)集，GXDSGC算法的相似性閾值設(shè)置為0.6，最小聚類尺寸設(shè)置為2，實(shí)驗(yàn)結(jié)果如圖7所示。圖7(a)表示在改變集群中機(jī)器數(shù)的情況下GXDSGC算法在各個(gè)數(shù)據(jù)集上的加速比。圖7(b)表示在改變集群中機(jī)器數(shù)的情況下GXDSGC算法在各個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間的相對(duì)加速比。在該實(shí)驗(yàn)中，相對(duì)加速比的計(jì)算公式為：

從圖7中可以看出，GXDSGC算法具有良好的可擴(kuò)展性，且隨著數(shù)據(jù)集規(guī)模的增加，算法的加速性能更好，因?yàn)殡S著圖尺寸的增加，減少集群中機(jī)器間的通信開銷在整個(gè)運(yùn)行時(shí)間中所占的百分比。從圖7(b)中可以看出，算法并沒(méi)有達(dá)到理想的相對(duì)加速比，因?yàn)榧褐袡C(jī)器之間需要進(jìn)行通信和數(shù)據(jù)交換，增加了運(yùn)行時(shí)間，使得相對(duì)加速比比理想加速比要小。

Fig.7 GXDSGC speedup圖7 GXDSGC加速比

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

SCAN算法利用頂點(diǎn)之間的結(jié)構(gòu)信息不僅能夠?qū)D進(jìn)行聚類，還能識(shí)別出圖中頂點(diǎn)的不同角色，為用戶提供豐富的信息；而PSCAN算法是SCAN算法在分布式集群上的擴(kuò)展。本文提出的GXDSGC算法是對(duì)PSCAN算法的進(jìn)一步優(yōu)化，GXDSGC算法在執(zhí)行過(guò)程中能夠極大減少I/O開銷，并能夠通過(guò)使用兩個(gè)削減策略減少相似性計(jì)算時(shí)間，通過(guò)實(shí)驗(yàn)表明GXDSGC算法處理數(shù)據(jù)更加高效，但GXDSGC算法在求連通分量時(shí)需要多次迭代，花費(fèi)大量時(shí)間且通信開銷也比較大，如何進(jìn)一步優(yōu)化算法，降低求連通分量的時(shí)間和通信開銷仍需進(jìn)一步研究。