復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)并行算法

滕 飛 ，戴榮杰 ，任曉春

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 改進(jìn)思路

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

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

2 并行層級(jí)連接算法PHLink

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

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

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

2.1 相似度計(jì)算

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

算法1相似度計(jì)算

Mapper: map()

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

2.2 合并

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

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

算法2合并

Mapper: map()

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

輸出：＜k，v ＞ k為社區(qū)編號(hào) 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)；//當(dāng)前 id 與前一個(gè) 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)//利用并查集對(duì)pair進(jìn)行連通

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

合并作業(yè)的極端情況是每個(gè)map只處理一個(gè)社區(qū)，不進(jìn)行合并，合并工作全部由唯一的reduce完成. 此時(shí)，m1為待合并的社區(qū)數(shù)，社區(qū)的最大規(guī)模為鄰居邊的個(gè)數(shù)2K1，K1為子圖G1節(jié)點(diǎn)度的最大值. 故合并作業(yè)的并行算法時(shí)間復(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é)點(diǎn)stone，值為與stone相連的所有的普通節(jié)點(diǎn). 輸出鍵值對(duì)為邊社區(qū)，key為社區(qū)編號(hào)，value為社區(qū)對(duì)應(yīng)的邊集.

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

算法3歸屬

Mapper:map()

輸入：＜k，v ＞ k為樞紐節(jié)點(diǎn) stone，v為 stone的鄰居點(diǎn)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；//計(jì)算增量

（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)；

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

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

3 實(shí)驗(yàn)分析

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

3.1 評(píng)價(jià)指標(biāo)

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

表1 基準(zhǔn)測(cè)試數(shù)據(jù)集Tab.1 Benchmark datasets

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

準(zhǔn)確率定義為

?Cg(i)g(i)

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

召回率定義為

F1定義為

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

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

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

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

3.2 樞紐節(jié)點(diǎn)比例閾值對(duì)計(jì)算效率的影響

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

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

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

3.3 運(yùn)行時(shí)間及網(wǎng)絡(luò)規(guī)模

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

表3 運(yùn)行時(shí)間比較Tab.3 Comparison of computation time s

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

對(duì)于YouTube和Skitter兩個(gè)網(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ì)量評(píng)價(jià)

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

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

4 結(jié) 論

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

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

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