滕 飛 ，戴榮杰 ，任曉春

（1. 西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，四川 成都 611756；2. 軌道交通工程信息化國家重點實驗室（中鐵一院），陜西 西安 710043）

隨著信息技術(shù)的迅速發(fā)展，人類社會已經(jīng)邁入了復(fù)雜網(wǎng)絡(luò)時代，各種超大規(guī)模網(wǎng)絡(luò)不斷涌現(xiàn)，例如智能電網(wǎng)、電話網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等. 大規(guī)模復(fù)雜網(wǎng)絡(luò)中的一些社會化特征在全局層面往往具有穩(wěn)定的統(tǒng)計規(guī)律，可用來理解人類社交關(guān)系的結(jié)構(gòu)和行為. 社區(qū)發(fā)現(xiàn)根據(jù)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)探索網(wǎng)絡(luò)關(guān)系的群組特征，識別出網(wǎng)絡(luò)中有意義的、自然的、相對穩(wěn)態(tài)的社區(qū)結(jié)構(gòu)，對網(wǎng)絡(luò)信息的搜索與挖掘、輿論控制、信息推薦以及網(wǎng)絡(luò)演化預(yù)測具有重要價值.

早期的社區(qū)發(fā)現(xiàn)算法主要研究的是非重疊社區(qū)結(jié)構(gòu). 隨著人們對網(wǎng)絡(luò)性質(zhì)認識的加深和新型網(wǎng)絡(luò)不斷出現(xiàn)，非重疊社區(qū)成員屬性過于單一，無法體現(xiàn)復(fù)雜網(wǎng)絡(luò)形成的動機和社區(qū)結(jié)構(gòu)的豐富內(nèi)涵. 重疊社區(qū)發(fā)現(xiàn)問題最早由Palla等提出，允許一個節(jié)點同時屬于多個社區(qū)[1]. Palla等提出派系過濾算法 （clique percolation method，CPM），通過建立重疊矩陣尋找連通部分形成社區(qū)劃分[2]. 派系過濾算法需要以完全子圖為基本單元來發(fā)現(xiàn)重疊，這對于很多真實網(wǎng)絡(luò)尤其是稀疏網(wǎng)絡(luò)而言，限制條件過于嚴格，只能發(fā)現(xiàn)少量的重疊社團. 此后，非重疊社區(qū)算法經(jīng)過調(diào)整也應(yīng)用到重疊社區(qū)發(fā)現(xiàn)，例如局部優(yōu)化法[3-4]、標簽傳播法[5]、概率模型算法[6]、模糊聚類算法[7]，這些方法往往需要預(yù)先給定參數(shù)，算法的普適性和魯棒性受到一定限制. Ahn等在《Nature》雜志上首次提出將邊作為社區(qū)劃分的研究對象[8]，開創(chuàng)了重疊社區(qū)發(fā)現(xiàn)的一條新的道路，文獻[9]基于點的非重疊社區(qū)算法經(jīng)過調(diào)整可應(yīng)用到重疊社區(qū)發(fā)現(xiàn). 復(fù)雜網(wǎng)絡(luò)中的一條邊通常對應(yīng)某一種類型的特定交互，以邊為對象使得劃分結(jié)果更能真實地反映節(jié)點在網(wǎng)絡(luò)中的角色或功能，一條邊只歸屬于一個社區(qū)，從而允許一個節(jié)點歸屬于多個重疊社區(qū). 總體來說，基于邊的社區(qū)發(fā)現(xiàn)算法與同類型的基于點的算法相比，無論是時間還是空間復(fù)雜度都高出很多，主要是由于網(wǎng)絡(luò)中邊的數(shù)量要遠遠多于點的數(shù)量，因此復(fù)雜度是設(shè)計重疊社區(qū)發(fā)現(xiàn)算法時需要考慮的重要因素.

并行化是降低運算時間的有效途徑，目前可用的并行計算框架不斷豐富，如MPI、MapReduce、Spark和專門用于圖計算的GraphX、Pregel等. 結(jié)合并行計算框架的算法開發(fā)，可以緩解大規(guī)模復(fù)雜網(wǎng)絡(luò)的計算問題. 一些學(xué)者通過并行化實現(xiàn)非重疊社區(qū)發(fā)現(xiàn)算法的快速迭代，提高了運行時間方面的性能[10-11]. 社區(qū)發(fā)現(xiàn)并行算法帶來效率的提升主要依賴于計算框架的部署規(guī)模，其最大難點在于復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)本身固有的連通性和圖計算表現(xiàn)出強耦合性.因此，需要進行有效的圖分割，盡可能降低分布式計算的各子圖之間的耦合度. 本文選擇MapReduce作為并行計算的開發(fā)框架，提出了一種適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)算法PHLink （parallel hierarchical link）.

PHLink算法創(chuàng)新性的提出將節(jié)點按照復(fù)雜網(wǎng)絡(luò)的無標度特性進行分層，根據(jù)建立連邊的不同動機來探索節(jié)點的多重屬性和社區(qū)歸屬. 這種思想也同樣適用于其他基于邊的社區(qū)發(fā)現(xiàn)算法，用于降低邊計算的復(fù)雜度，具有一定的通用性. 其次，PHLink算法在Hadoop平臺上將復(fù)雜網(wǎng)絡(luò)進行分割和冗余存儲，減弱了圖計算的強耦合性，使子圖得以獨立的并行處理，解決了社區(qū)發(fā)現(xiàn)算法的分布式計算問題.大量真實網(wǎng)絡(luò)測試表明PHLink算法綜合性能良好，劃分社區(qū)質(zhì)量較高，在并行環(huán)境下具有良好的加速性和伸縮性，可以處理千萬級連邊規(guī)模的大規(guī)模復(fù)雜網(wǎng)絡(luò).

1 邊社區(qū)發(fā)現(xiàn)算法及其改進

1.1 邊社區(qū)發(fā)現(xiàn)算法及復(fù)雜度分析

傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法是將網(wǎng)絡(luò)劃分為若干個不重疊的點社區(qū)，每個節(jié)點具有唯一屬性且僅能隸屬于唯一社區(qū). 然而事實上每個節(jié)點可以包含多重屬性，出于不同動機與他人建立連接，例如親戚或同事關(guān)系. 邊社區(qū)能更為精確地刻畫屬性的類別，在應(yīng)用中更加具有實際意義.

圖論提供了一種用抽象的點和邊表示各種實際網(wǎng)絡(luò)的統(tǒng)一方法，是目前研究復(fù)雜網(wǎng)絡(luò)的一種共同語言，因此本文用圖的形式對復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)進行描述，刻畫邊社區(qū).

定義1（復(fù)雜網(wǎng)絡(luò)）復(fù)雜網(wǎng)絡(luò)可抽象為一個由點集V和邊集E組成的無向無權(quán)圖G（V，E），v∈V表示節(jié)點，e∈E表示節(jié)點之間的連接關(guān)系，點集和邊集的規(guī)模分別為n和m.

定義2（邊相似度）[8]具有一個公共節(jié)點vl的連邊對eil和ejl之間的邊相似度是節(jié)點vi和vj所擁有的共同鄰居的相對數(shù)量，記為

式中：vl、vi和 vj分別為第 l、i和 j個節(jié)點，i，j，l =1,2,···；n+（i）為節(jié)點vi及其所有鄰居節(jié)點的集合.

邊社區(qū)劃分可以采用Link單連接凝聚聚類的方法對邊集進行聚類[8]，該算法具有直觀、易理解的優(yōu)點，然而其復(fù)雜度較高，不適用于大規(guī)模的復(fù)雜網(wǎng)絡(luò). Link算法中最重要的步驟為計算連邊之間的相似度得到相似度矩陣，該矩陣代表了任意兩條邊之間的親疏關(guān)系，復(fù)雜度為O（m2）. 考慮到連邊相似度在計算時僅需考慮有共同節(jié)點的兩個連邊，因此相似度矩陣的復(fù)雜度可以降至O（nK2），其中，K是網(wǎng)絡(luò)中節(jié)點度的最大值.

1.2 改進思路

在線社交類的復(fù)雜網(wǎng)絡(luò)的一階度分布已經(jīng)被證明具有無標度特性，節(jié)點度為k的概率正比于k-γ，稱參數(shù)γ為冪律系數(shù). 有研究顯示社交網(wǎng)絡(luò)的冪律系數(shù)范圍在 1.5 ＜ γ＜ 2.5[12]. 以 YouTube 網(wǎng)絡(luò)為例[13]，雙對數(shù)坐標系下概率分布函數(shù)呈線性關(guān)系，γ約為1.7. 這意味著，YouTube網(wǎng)絡(luò)中僅有極少數(shù)的點擁有比較大的度，絕大多數(shù)的點只擁有少量連接. 比如度超過200節(jié)點僅占全部節(jié)點的0.2%，這些節(jié)點擁有的邊占總邊數(shù)的21%，而相似度計算量占比卻高達95%. 因此本文將利用冪律分布特性來減緩邊計算內(nèi)存存儲的壓力，降低算法復(fù)雜度.

一階度分布刻畫的是網(wǎng)絡(luò)中不同度的節(jié)點各自所占的比例，但具有相同度分布的兩個網(wǎng)絡(luò)可能具有非常不同的性質(zhì)或行為. 二階度分布顯示了度的相關(guān)性. Erzsebet等經(jīng)實際測量研究表明社交網(wǎng)絡(luò)的層級結(jié)構(gòu)使得集團內(nèi)部連接緊密，但節(jié)點平均度較小，集團間連接稀疏，但負責(zé)連接的樞紐節(jié)點度較大[14]. 樞紐節(jié)點之間的連接描述了核心層的連接情況，其社區(qū)密度將遠遠高于網(wǎng)絡(luò)的劃分密度，也即富人俱樂部連通性現(xiàn)象. 基于以上結(jié)論，本文按照一階度分布把網(wǎng)絡(luò)節(jié)點分為樞紐節(jié)點普通節(jié)點，分層進行相似連邊聚類. 由于樞紐節(jié)點往往跨領(lǐng)域連接到其他社區(qū)的節(jié)點，去除了樞紐節(jié)點和其歸屬邊后，由普通節(jié)點構(gòu)成社團的結(jié)構(gòu)將比之前更加清晰，有利于提取社區(qū)信息.

2 并行層級連接算法PHLink

本文基于Hadoop平臺設(shè)計并實現(xiàn)了并行層級連接算法PHLink，可以解決復(fù)雜網(wǎng)絡(luò)由于數(shù)據(jù)量大而導(dǎo)致的計算時間過長，內(nèi)存不足等問題. PHLink算法的示意圖如圖1所示，首先對原始網(wǎng)絡(luò)G進行預(yù)處理，分成G1、G2和G33個子圖，其中G1包含了普通節(jié)點之間的連邊，G2包含了普通節(jié)點與樞紐節(jié)點的連邊，G3包含了樞紐節(jié)點之間的連邊. PHLink分別對G1和G3進行相似度計算，采用凝聚聚類的方法合并相似的邊，形成邊社區(qū)；接下來將G2中的連邊歸屬到由G1形成的邊社區(qū)；最后將邊社區(qū)轉(zhuǎn)換成點社區(qū)，并對點社區(qū)進行清洗，去掉節(jié)點數(shù)少于3個的點社區(qū). 至此，PHLink算法得到了非重疊的邊社區(qū)劃分與重疊的點社區(qū)劃分結(jié)果.

圖1 PHLink算法示意Fig.1 Overview diagram for PHLink

在Hadoop平臺上實現(xiàn)PHLink算法的難點在于計算相似度、合并以及歸屬3個步驟，可以用3個MapReduce作業(yè)加以實現(xiàn)，需要重點完成Mapper和Reducer自定義類的設(shè)計.

2.1 相似度計算

預(yù)處理階段按照節(jié)點度將原始網(wǎng)絡(luò)G分割為3個子網(wǎng)絡(luò)G1、G2和G3，并以點鄰接表的格式存儲在 HDFS （Hadoop distributed file system）.

算法1相似度計算

Mapper: map()

輸入：＜k，v ＞ k為 node，v為 node所有的鄰居點 adj

θ為相似度值；

輸出：＜k，v ＞ k為 link，v為 link鄰居邊 neiglink

（1） 從HDFS讀入原始網(wǎng)絡(luò)G

（2） FOR each v1 in adj

（3） FOR each v2 in adj

（4）intersection=v1.getAdj()∩v2.getAdj()；

（5）union=v1.getAdj()∪v2.getAdj()；

（6）sim=intersection.size()/union.size()；

（7）link1= node+v1；

（8）link2= node + v2；

（9）IF (sim ＞ θ)

（10） write(key:link1，value:link2)；

（11） write(key:link2，value:link1)；

（12）ENDIF

（13）ENDFOR

（14） ENDFOR

Reducer: reduce()

輸入：＜k，v ＞ k為 link，v為 link鄰居邊 neiglink

輸出：＜k，v ＞ k為 link，v為 link所有的鄰居邊 linkAdj

（15） itr = neiglink.iterator()；//迭代器

（16） WHILE itr.hasNext() DO

（17） linkAdj = linkAdj∪itr.next()；

（18） ENDWHILE

（19） write(key:link，value: linkAdj)；

算法1中，map函數(shù)的輸入鍵值對為點鄰接表形式，value值是與key節(jié)點相鄰的所有節(jié)點的集合.輸出鍵值對為邊鄰接表形式，value值僅包括相似度大于參數(shù)θ的鄰居邊. map函數(shù)按照式（1）計算包含有共同點node的兩條相鄰邊的相似度（算法1（4）～（8）），如果相似度大于 θ，將兩條邊分別作為鍵和值輸出兩次（算法 1（9）～（12））. reduce函數(shù)對具有相同 key的邊進行規(guī)約操作（算法1（15）～（18）），輸出鍵值對為邊鄰接表形式.

2.2 合并

得到邊鄰接表之后，可以將每條邊及其鄰居邊初始化為邊社區(qū). 合并作業(yè)的目的是將具有單邊連接關(guān)系的小社區(qū)合并為大社區(qū). 本文利用并查集將小社區(qū)進行連通，解決了分布式計算中網(wǎng)絡(luò)耦合的問題. 考慮到合并具有層次性，本文采用多次合并的策略平衡計算中的時空復(fù)雜度，由map任務(wù)完成局部邊集的合并，reduce任務(wù)對map合并的結(jié)果進行匯總合并，有且僅有一個reduce任務(wù). map和reduce具有相同的功能，兩者采用了相同的算法.

算法2中，map函數(shù)通過掃描邊和其所在的社區(qū)編號找到社區(qū)之間的連通關(guān)系. 輸入鍵值對為初始邊社區(qū)，key為社區(qū)編號，value為社區(qū)對應(yīng)的邊集. 輸出鍵值對為合并后的邊社區(qū). linkMap存儲邊的社區(qū)編號，如果一條邊已經(jīng)存在linkMap中，則把已存儲的編號和當前的編號組成一對組合pair，標記兩個社區(qū)是連通的（算法 2（4）～（6）），更新邊的社區(qū)編號（算法2（7））. 否則，將邊與其所屬的社區(qū)編號組成新鍵值對存儲到linkMap （算法2（8）～（9））. 遍歷初始化社區(qū)中的每一條邊可以獲得所有社區(qū)與社區(qū)之間的連通關(guān)系，存放在pairSet （算法2（3）～（11））. cleanup函數(shù)通常在執(zhí)行完畢 map后，進行相關(guān)變量或資源的收尾工作，僅且執(zhí)行一次. 合并算法的cleanup函數(shù)利用并查集將社區(qū)進行連通（算法 2（12）～（14））. clusterMap存儲所有的邊社區(qū)，每條邊通過查詢并查集找到所歸屬的社區(qū)（算法 2（17）～（19）），如果社區(qū)不存在，則新建社區(qū)并加入 clusterMap （算法 2（21）～（23））. 由此，可以完成將具有單邊聯(lián)系的小社區(qū)合并為大社區(qū)的效果.

算法2合并

Mapper: map()

輸入：＜k，v ＞ k為社區(qū)編號 id，v為邊社區(qū) inCluster

輸出：＜k，v ＞ k為社區(qū)編號 id，v為邊社區(qū) outCluster

（1） 初始化 linkMap；//存放所有邊的 map 映射

（2） 初始化 pairSet；//存放社區(qū)之間連通關(guān)系的 set集合

（3） FOR each link in inCluster

（4） IF (linkMap.constainsKey(link))//邊已存在

（5）preId=linkMap.get(link)；

（6）pairSet.add(preId，id)；//當前 id 與前一個 id組成pair

（7）linkMap.put(link，id)；

（8）ELSE

（9）linkMap.put(link，id)；//新邊加入 linkMap

（10）END IF

（11） END FOR

Mapper: cleanup()

（12） FOR each pair in pariSet

（13） unionFound.union(pair.v1，pair.v2)//利用并查集對pair進行連通

（14） ENDFOR

（15） 初始化 clusterMap；//存放所有社區(qū)的 map 映射

（16） FOR each link in linkMap

（17）clusterId = unionFound.find(linkMap.get(link))//查找link應(yīng)歸屬的社區(qū)

（18） IF (clusterMap.containedKey(clusterId)) //已存在社區(qū)

（19） clusterMap.get(clusterId).add(link)；//加入邊

（20） ELSEIF

（21） outCluster = null；//增加新社區(qū)

（22） outCluster.add(link)；

（23） clusterMap.put(clusterId，outCluster)

（24） ENDIF

（25） ENDFOR

（26）write(key:clusterId，value: outCluster)；

Reducer:reduce()

（27） 同 Mapper:map()

Reducer:cleanup()

（28） 同 Mapper:cleanup()

map函數(shù)的時間復(fù)雜度為 O（sms），其中，s為map分片中鍵值對的個數(shù)，即輸入社區(qū)數(shù)，ms為map分片中不重復(fù)的邊數(shù)，也即社區(qū)的最大規(guī)模.cleanup函數(shù)中通過查詢并查集，為每條邊找到對應(yīng)的社區(qū)編號，時間復(fù)雜度為O（mslog s）. linkMap和clusterMap存儲的是map分片中每條邊的社區(qū)編號，空間復(fù)雜度為O（ms）.

合并作業(yè)的極端情況是每個map只處理一個社區(qū)，不進行合并，合并工作全部由唯一的reduce完成. 此時，m1為待合并的社區(qū)數(shù)，社區(qū)的最大規(guī)模為鄰居邊的個數(shù)2K1，K1為子圖G1節(jié)點度的最大值. 故合并作業(yè)的并行算法時間復(fù)雜度為O（m1K1），空間復(fù)雜度為 O（m1）.

2.3 歸屬

已知G1網(wǎng)絡(luò)的邊社區(qū)的劃分結(jié)果outCluster，歸屬作業(yè)把G2網(wǎng)絡(luò)的邊加入到已知邊社區(qū)中. 算法3中map函數(shù)的輸入鍵為樞紐節(jié)點stone，值為與stone相連的所有的普通節(jié)點. 輸出鍵值對為邊社區(qū)，key為社區(qū)編號，value為社區(qū)對應(yīng)的邊集.

map函數(shù)從HDFS讀入邊社區(qū)劃分outCluster，將鍵值對中包含的每條邊stone-node歸屬到可以使ΔD 增加最多的社區(qū)（算法 3（4）～（16））. reduce函數(shù)對具有相同key的社區(qū)進行規(guī)約操作（算法3（18）～（22）），輸出 key和 value.

算法3歸屬

Mapper:map()

輸入：＜k，v ＞ k為樞紐節(jié)點 stone，v為 stone的鄰居點adj

輸出：＜k，v ＞ k為 id，v為邊社區(qū) cluster

（1） 從 HDFS 讀取 outCluster;

（2） max=-1;

（3） id=-1;

（4） FOR each node in adj

（5） link = stone+node;

（6） FOR each cluster in outCluster//查找增量最大的社區(qū)

（7）IF (node in cluster)

（8） calculate ΔD；//計算增量

（9） IF (ΔD ＞ max )

（10） max=ΔD；

（11） id=clusterId;

（12） END IF

（13）END IF

（14）END FOR

（15） END FOR

（16） clusterMap.get(id).add(link)；//加入增量最大的社區(qū)

（17） write(key:id，value: clusterMap.get(id))；

Reducer: reduce()

輸入：＜k，v ＞ k為 id，v為 inCluster邊社區(qū)

輸出：＜k，v ＞ k 為 id，v為 outCluster 邊社區(qū)

（18） itr = inCluster.iterator()；//迭代器

（19） WHILE itr.hasNext() DO

（20） outCluster = outCluster∪itr.next()；

（21） ENDWHILE

（22） write(key:id，value: outCluster)；

歸屬并行算法時間復(fù)雜度為O（sq1），其中，q1是G1子圖劃分的社區(qū)數(shù). 算法從HDFS中將G1子圖的社區(qū)劃分讀入內(nèi)存，空間復(fù)雜度為O（m′1），此時，m′1為G1子圖的邊數(shù).

綜合相似度計算、合并、歸屬3個作業(yè)的復(fù)雜度分析，考慮到map分片的大小是人為可控的，子圖G3的規(guī)模遠遠小于子圖G1，PHLink算法的時間復(fù)雜度為 O（m1K1），空間復(fù)雜度 O（m）. 可見，PHLink算法具有較好的擴展性，可以通過增加工作節(jié)點，降低運行時間.

3 實驗分析

本實驗使用的Hadoop集群環(huán)境由12臺Dell E5506服務(wù)器組成，每臺服務(wù)器擁有4核CPU、12 GB內(nèi)存、500 GB硬盤、安裝了hadoop-2.4.1，并以千兆以太網(wǎng)相連. 本文中是實驗數(shù)據(jù)來自SNAP （Stanford network analysis project）實驗室真實網(wǎng)絡(luò)數(shù)據(jù)[13]，如表1所示，其中帶星號的3個網(wǎng)絡(luò)標注有g(shù)roundtruth高質(zhì)量社區(qū).

3.1 評價指標

假設(shè)真實社區(qū)為C*，由社區(qū)發(fā)現(xiàn)算法識別出的社區(qū)為，社區(qū)匹配定義為

表1 基準測試數(shù)據(jù)集Tab.1 Benchmark datasets

式中： Ci和分別為i個真實社區(qū)和第j個識別出的社區(qū).

準確率定義為

?Cg(i)g(i)

式中： 為第 個識別出的社區(qū).

召回率定義為

F1定義為

定義任意兩個節(jié)點u、v所歸屬的社區(qū)數(shù)量的準確性為[6]

擴展的規(guī)范化互信息（extended normalized mutual information，ENMI ）[6]度量了基準網(wǎng)絡(luò)的社區(qū)集合和挖掘算法發(fā)現(xiàn)的社區(qū)集合的一致性程度，定義參見文獻[3].

社區(qū)覆蓋率[8]定義為屬于非平凡社區(qū)（3個或以上節(jié)點的社區(qū)）的節(jié)點所占的比例.

社區(qū)重疊率[8]定義為每個節(jié)點所屬的非平凡社區(qū)的平均值.

3.2 樞紐節(jié)點比例閾值對計算效率的影響

PHLink算法計算效率受到樞紐節(jié)點比例閾值的影響. 比例閾值越高，計算效率越高，綜合指標相應(yīng)降低. 比例閾值需根據(jù)實際網(wǎng)絡(luò)的特性和規(guī)模選取.

如表2所見，大規(guī)模網(wǎng)絡(luò)的無標度特性更強，如YouTube、Skitter網(wǎng)絡(luò)，極少數(shù)的點擁有絕大多數(shù)的連邊，僅選擇度最大的0.1%的節(jié)點即可節(jié)省94%以上的計算量. 隨著比例閾值進一步提高，計算量隨之減少，但降低幅度變緩. DBLP和Amazon網(wǎng)絡(luò)的樞紐節(jié)點對計算量的影響較弱，是由于網(wǎng)絡(luò)本身特性決定的. 比如在DBLP中，單一學(xué)者的論文數(shù)量有限，一般最多能到達百篇量級，DBLP中節(jié)點的最大度為347，因此無標度特性比YouTube較弱.

表2 比例閾值對計算量的影響Tab.2 Effect of proportional threshold on computation %

3.3 運行時間及網(wǎng)絡(luò)規(guī)模

本文選取了重疊社區(qū)發(fā)現(xiàn)的經(jīng)典算法CPM[2]、Bigclam[6]、Link[8]與 PHLink 進行比較. 實驗中 You-Tube和Skitter網(wǎng)絡(luò)規(guī)模較大，采用12個節(jié)點并行處理，其余網(wǎng)絡(luò)僅用單個節(jié)點進行計算. Bigclam算法需要提前設(shè)置社區(qū)數(shù)作為輸入?yún)?shù)，其中DBLP和Amazon按照網(wǎng)絡(luò)的真實社區(qū)數(shù)取值，其他數(shù)據(jù)集由于社區(qū)數(shù)未知，取值30，如表3中括號所示.CPM算法設(shè)置完全圖參數(shù)為4，PHlink設(shè)置樞紐節(jié)點比例閾值為0.1%，結(jié)果如表3所示.

表3 運行時間比較Tab.3 Comparison of computation time s

PHLink無論從運算時間還是網(wǎng)絡(luò)規(guī)模都明顯好于其他幾種算法. 值得注意的PHLink處理Jazz網(wǎng)絡(luò)的時間要高于Facebook網(wǎng)絡(luò)，主要原因是PHLink算法的復(fù)雜度不僅與網(wǎng)絡(luò)規(guī)模有關(guān)，也受到網(wǎng)絡(luò)的稠密程度（平均度）的影響.

對于YouTube和Skitter兩個網(wǎng)絡(luò)，本文通過改變集群規(guī)模，考察PHLink算法的并行能力，如表4所示.

表4 PHLink算法加速性能Tab.4 Speedup for PHLink s

由表4可知，PHLink算法有著良好的并行加速性能，而且隨著網(wǎng)絡(luò)規(guī)模的增大，加速比接近于1.

3.4 社區(qū)質(zhì)量評價

評價指標采用 3.1 節(jié)中定義的 F1、 ? 、ENMI、重疊率和覆蓋率，將5項指標的取值分別進行歸一化，使得每個指標最大值為1，最小值為0.5項指標的歸一化值加和用于評價算法的綜合性能，其最大取值為5，最小取值為0.

PHLink和Link算法采用單連接凝聚聚類的方法對邊集進行聚類，將生成大量平凡社區(qū)，因此用來測度社區(qū)劃分準確性的F1、 ? 、ENMI 3項指標將以5 000個高質(zhì)量社區(qū)作為基準，重疊率和覆蓋率計算的是全網(wǎng)中屬于非平凡社區(qū)的節(jié)點. 如圖2所示，PHLink和Link的綜合性能相差無幾，其中，F(xiàn)1、?兩項指標優(yōu)于Bigclam算法. ENMI在Amazon數(shù)據(jù)集下遜于Bigclam算法，這與網(wǎng)絡(luò)數(shù)據(jù)集的特性有關(guān). Amazon與DBLP相比，平均社區(qū)規(guī)模小，節(jié)點分布廣，社區(qū)結(jié)構(gòu)較為松散. PHLink和Link算法的重疊率略高于Bigclam，但覆蓋率低于Bigclam，主要原因是Bigclam算法本身可以避免生成平凡社區(qū). 而實際網(wǎng)絡(luò)DBLP中，度為1的節(jié)點比例高達14%，存在大量的平凡社區(qū).

4 結(jié) 論

本文重點闡述了大規(guī)模復(fù)雜網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)并行算法 PHLink 的工作原理，基于MapReduce并行計算框架，解決了大規(guī)模復(fù)雜網(wǎng)絡(luò)中社區(qū)的識別問題. 根據(jù)復(fù)雜網(wǎng)絡(luò)的無標度特性將節(jié)點分為樞紐層和普通層，對不同節(jié)點建立連邊的原因進行分析和歸類，以邊作為社區(qū)劃分的研究對象，用以識別網(wǎng)絡(luò)中具有重疊性的社區(qū)結(jié)構(gòu). 由于節(jié)點分層處理，大大降低了計算量，并在此基礎(chǔ)上實現(xiàn)并行化，緩解了對內(nèi)存限制，使子圖得以獨立的并行處理，解決了傳統(tǒng)社區(qū)發(fā)現(xiàn)算法無法處理的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)劃分問題. 實驗在真實大規(guī)模復(fù)雜網(wǎng)絡(luò)上進行，與多種經(jīng)典的重疊社區(qū)發(fā)現(xiàn)算法進行對比，驗證了本文PHLink算法對大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)識別的時效性，可以處理千萬級連邊規(guī)模的大規(guī)模復(fù)雜網(wǎng)絡(luò).

圖2 綜合性能比較Fig.2 Comparison of composite performance

致謝：中鐵第一勘察設(shè)計院集團有限公司軌道交通工程信息化國家重點實驗室開放課題（SKLK16-04）.