基于社區(qū)森林模型的分布式重疊社區(qū)發(fā)現(xiàn)算法

張妍　劉濱　梅衛(wèi)　許云峰　谷利東　于彭帥　石鈺　魏西峰

摘 要：重疊社區(qū)發(fā)現(xiàn)是復雜網(wǎng)絡挖掘中的重要基礎(chǔ)工作，可以應用于社交網(wǎng)絡、通訊網(wǎng)絡、蛋白質(zhì)相互作用網(wǎng)絡、代謝路徑網(wǎng)絡、交通網(wǎng)絡等多種網(wǎng)絡的數(shù)據(jù)分析，從而服務智慧交通、傳染病防治、輿情分析、新藥研制和人力資源管理等領(lǐng)域。傳統(tǒng)的單機運算架構(gòu)已經(jīng)難以滿足各類大規(guī)模復雜網(wǎng)絡的分析和計算要求。人工智能領(lǐng)域的研究人員提出將社區(qū)發(fā)現(xiàn)應用到網(wǎng)絡表示學習領(lǐng)域，以豐富網(wǎng)絡中節(jié)點和邊的特征，但傳統(tǒng)的重疊社區(qū)發(fā)現(xiàn)算法在設(shè)計時未能考慮來自網(wǎng)絡表示學習任務的相關(guān)要求，只重點關(guān)注節(jié)點的社區(qū)劃分，缺乏對社區(qū)內(nèi)部結(jié)構(gòu)和外部邊界的考慮，例如沒有涉及節(jié)點在社區(qū)內(nèi)部的權(quán)重和屬于多個社區(qū)的歸屬度排序等，因而不能提供網(wǎng)絡中節(jié)點和社區(qū)更豐富的特征信息，導致對網(wǎng)絡表示學習任務支持不足。

針對傳統(tǒng)單機重疊社區(qū)發(fā)現(xiàn)算法已經(jīng)不適用于大規(guī)模復雜網(wǎng)絡挖掘，以及不能滿足網(wǎng)絡表示學習任務的相關(guān)要求等問題，提出一種基于社區(qū)森林模型的分布式重疊社區(qū)發(fā)現(xiàn)算法（distributed community forest model，簡稱DCFM算法）。首先，將網(wǎng)絡數(shù)據(jù)集存儲到分布式文件系統(tǒng)，將數(shù)據(jù)分塊，使用分布式計算框架在每個數(shù)據(jù)分塊上執(zhí)行CFM算法;然后，執(zhí)行社區(qū)合并;最后，匯總社區(qū)劃分結(jié)果，使用真實的DBLP數(shù)據(jù)集將算法運行于Spark集群上，采用F均值和運行時間對算法進行評估。結(jié)果表明，DCFM算法的F均值稍遜于CFM算法，但其運算時間隨著節(jié)點的增加接近線性下降，在犧牲小部分F均值的同時，DCFM算法具備處理大規(guī)模網(wǎng)絡數(shù)據(jù)的能力;分割份數(shù)對計算時間的影響很大，在com-dblp.ungraph.txt數(shù)據(jù)集上，CFM算法處理數(shù)據(jù)需要192 min，而DCFM算法在將數(shù)據(jù)分成6份時，需要約91 min，分成100份后僅需要約13 min。因此，在大數(shù)據(jù)平臺上采用分布式計算骨干度，從而進行社區(qū)劃分、合并的DCFM算法是一種可行的大規(guī)模復雜網(wǎng)絡挖掘方法，通過分割網(wǎng)絡，可以大幅加快社區(qū)劃分速度，提高社區(qū)發(fā)現(xiàn)效率。

關(guān)鍵詞：分布式處理系統(tǒng);社交網(wǎng)絡;重疊社區(qū);社區(qū)森林模型;社區(qū)發(fā)現(xiàn)

中圖分類號：TP311.13 文獻標識碼：A

Abstract：Overlapping community discovery is an important basic work in complex network mining.It can be applied to the data analysis of social networks，communication networks，protein interaction networks，metabolic path networks，transportation networks and other networks，so as to serve the fields of intelligent transportation，infectious disease prevention and control，public opinion analysis，new drug development and human resource management.The traditional stand-alone computing architecture has been difficult to meet the analysis and computing requirements of various large-scale complex networks.Researchers in the field of artificial intelligence propose to apply community discovery to the field of network representation learning to enrich the characteristics of nodes and edges in the network.However，the traditional overlapping community discovery algorithm fails to consider the relevant requirements from the network representation learning task in its design，only focuses on the community division of nodes，and lacks consideration of the internal structure and external boundary of the community.For example，it does not involve the weight of nodes within the community and the attribution ranking belonging to multiple communities，so it cannot provide richer characteristic information of nodes and communities in the network，resulting in insufficient support for network representation learning tasks.Aiming at the problem that the traditional single machine overlapping community discovery algorithm is not suitable for large-scale complex network mining and cannot support the relevant requirements of network representation learning tasks，a distributed overlapping community discovery algorithm based on community forest model （DCFM algorithm） was proposed.Firstly，the network dataset was stored in the distributed file system，the data were divided into blocks，and the distributed computing framework was used to execute the CFM algorithm on each data block;then，the community consolidation was performed;Finally，the community division results were summarized，and the algorithm was run on the spark cluster by using the real DBLP dataset and was evaluated by F Value and running time.The results show that the f-means of DCFM algorithm is slightly inferior to that of CFM algorithm，but its operation time decreases linearly with the increase of nodes.While sacrificing a small part of f-means，DCFM algorithm has the ability to process large-scale network data;the number of split copies has a great impact on the calculation time，which can be found in com DBLP ungraph.Txt data set，CFM algorithm needs 192 min to process data，while DCFM algorithm needs about 91 min to divide the data into 6 parts，and only about 13 min after dividing into 100 parts.Therefore，on the big data platform，DCFM algorithm uses distributed computing backbone to divide and merge communities，which is a feasible large-scale complex network mining method.By dividing the network，it can greatly improve the speed of community division and the efficiency of community discovery.

Keywords：distributed processing system;social networks;overlapping communities;community forest model;commu-nity discovery

復雜網(wǎng)絡是理解和建模復雜系統(tǒng)的基本工具，這些復雜系統(tǒng)廣泛存在于物理、生物、神經(jīng)科學、工程和社會科學等領(lǐng)域中[1]。重疊社區(qū)發(fā)現(xiàn)是復雜網(wǎng)絡挖掘中的重要基礎(chǔ)工作，可以應用于社交網(wǎng)絡、通訊網(wǎng)絡、蛋白質(zhì)相互作用網(wǎng)絡、代謝路徑網(wǎng)絡、交通網(wǎng)絡等各種網(wǎng)絡的數(shù)據(jù)分析中，服務于人力資源管理、新藥研制、交通規(guī)劃、傳染病防治、輿情控制和表示學習[2]等領(lǐng)域。

近幾年，重疊社區(qū)發(fā)現(xiàn)算法領(lǐng)域又涌現(xiàn)出很多基于經(jīng)典社區(qū)發(fā)現(xiàn)算法的新研究，有些學者并行化了一些經(jīng)典社區(qū)發(fā)現(xiàn)算法，如PageRank。吳衛(wèi)江等[3]針對大型網(wǎng)絡中社區(qū)發(fā)現(xiàn)優(yōu)化方法的效率問題，提出了基于限制性隨機游走局部譜近似社區(qū)發(fā)現(xiàn)算法;陳界全等[4]提出基于SLPA優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法;王得翊等[5]針對復雜網(wǎng)絡研究面臨的網(wǎng)絡規(guī)模過大、難以獲取全局信息的困境，提出基于多階局部度數(shù)峰值點的局部社區(qū)發(fā)現(xiàn)算法;JALALI等[6]為改善協(xié)同過濾的可伸縮性、稀疏性和冷啟動問題，提出一種基于局部動態(tài)重疊社區(qū)檢測的社會協(xié)同過濾算法;BAHADORI等[7]針對現(xiàn)有動態(tài)社區(qū)檢測工作大多假設(shè)社區(qū)之間連接稀疏的問題，提出了一種概率重疊動態(tài)社區(qū)發(fā)現(xiàn)算法;GAO等[8]提出了基于約束個性化PageRank的重疊社區(qū)發(fā)現(xiàn)算法;ASMI等[9]提出了一種基于貪婪耦合種子展開法的重疊社區(qū)發(fā)現(xiàn)算法;ATTAL等[10]提出了一種使用核心標簽傳播算法和隸屬函數(shù)的重疊社區(qū)發(fā)現(xiàn)算法;BENNCIR等[11]針對現(xiàn)有重疊社區(qū)檢測方法通常會在社區(qū)之間建立比預期更大的重疊，并且不允許用戶與系統(tǒng)交互調(diào)節(jié)大小的問題，提出一種通過控制社區(qū)之間的重合程度進行重疊和非重疊社區(qū)發(fā)現(xiàn)的算法;NADERIPOUR等[12]針對目前大多數(shù)社區(qū)檢測方法主要集中在拓撲結(jié)構(gòu)、忽略了頂點異質(zhì)性的問題，提出一種大規(guī)模社交網(wǎng)絡中基于結(jié)構(gòu)或?qū)傩韵嗨菩缘哪：鐓^(qū)發(fā)現(xiàn)算法;BAHADORI等[13]針對基于隨機游走方法需要整個網(wǎng)絡信息且很難獲得的的問題，提出一種基于改進的有限隨機游走方法的重疊社區(qū)發(fā)現(xiàn)算法;WAN等[14]針對現(xiàn)有研究只考慮動態(tài)或重疊某一特征來評估社區(qū)檢測的問題，提出一種基于分解多目標進化的動態(tài)重疊社區(qū)發(fā)現(xiàn)算法;GAO等[15]提出了基于隸屬度傳播的重疊社區(qū)發(fā)現(xiàn)算法。一些學者還實現(xiàn)了經(jīng)典社區(qū)發(fā)現(xiàn)算法的并行化。例如：劉強等[16]對當前主流并行社區(qū)發(fā)現(xiàn)方法Louvain 算法和標簽傳播算法在超大規(guī)模數(shù)據(jù)集上的可擴展性進行了研究;ROGHANI等[17]提出了一種基于Spark的并行標簽擴散和標簽選擇社區(qū)發(fā)現(xiàn)算法;葉小榕等[18]利用Page-Rank算法和Z-Score算法計算用戶排名，應用并優(yōu)化LPA算法，將特征相近、聯(lián)系較密切的用戶快速劃分到同一社區(qū)中。這些研究工作出色解決了并行運算環(huán)境下的社區(qū)發(fā)現(xiàn)問題。

當前在網(wǎng)絡表示學習領(lǐng)域，越來越多的學者將社區(qū)結(jié)構(gòu)和網(wǎng)絡Motifs結(jié)構(gòu)等高階組織結(jié)構(gòu)特征融合到網(wǎng)絡嵌入中。骨干度[19]是一種和Motifs類似的高階網(wǎng)絡組織結(jié)構(gòu)。胡旭飛等[20]提出了一種基于骨干度與網(wǎng)絡嵌入的鏈路預測模型（BDLINE），在網(wǎng)絡表示學習算法LINE的基礎(chǔ)上融入骨干度特征，結(jié)果表明，在鏈路預測方面BDLINE均比其他網(wǎng)絡表示學習算法的性能有所提升，預測效果也更好;LI等[21]提出一種基于社區(qū)嵌入的社區(qū)發(fā)現(xiàn)算法。這些研究表明，重疊社區(qū)發(fā)現(xiàn)算法對大規(guī)模復雜網(wǎng)絡結(jié)構(gòu)刻畫得越清晰、越細致，網(wǎng)絡表示學習算法就越能學習到更好的網(wǎng)絡表示。基于社區(qū)森林模型的重疊社區(qū)發(fā)現(xiàn)算法（community forest model，簡稱CFM算法）是XU等[22]提出的一種基于社會學和生物學的自然啟發(fā)式社區(qū)發(fā)現(xiàn)方法，該算法基于骨干度和擴張度對重疊社區(qū)進行清晰定義，對社區(qū)內(nèi)部結(jié)構(gòu)和外部邊界進行清晰刻畫，并將該算法在分布式Spark計算平臺上得以實現(xiàn)，以應對來自大規(guī)模復雜網(wǎng)絡數(shù)據(jù)的挑戰(zhàn)。研究表明，在大規(guī)模社交網(wǎng)絡中，其比CPM，Louvin和MMSB等相關(guān)算法具有更好的性能。

但是以上這些工作仍無法應對如下2個挑戰(zhàn)。第一，研究者在各領(lǐng)域中構(gòu)建復雜網(wǎng)絡的規(guī)模急劇增大，傳統(tǒng)的單機算法已經(jīng)不能適應當前大規(guī)模復雜網(wǎng)絡挖掘的需求;第二，由于大數(shù)據(jù)和人工智能的快速發(fā)展，傳統(tǒng)的重疊社區(qū)發(fā)現(xiàn)算法在開發(fā)時尚未面對來自網(wǎng)絡表示學習任務的迫切需求，都只是重點關(guān)注節(jié)點的社區(qū)劃分，沒有關(guān)注社區(qū)的內(nèi)部結(jié)構(gòu)和外部邊界，因此不能提供網(wǎng)絡中節(jié)點和社區(qū)更豐富的特征信息，導致對下游網(wǎng)絡表示學習任務支持不足。并行重疊社區(qū)發(fā)現(xiàn)領(lǐng)域中的很多研究雖然解決了對大規(guī)模復雜網(wǎng)絡進行挖掘的問題，但是無法應對網(wǎng)絡表示學習任務對網(wǎng)絡豐富特征的迫切需求;而CFM算法雖然能夠應對網(wǎng)絡表示學習任務對網(wǎng)絡豐富特征的迫切需求，卻無法應對來自大規(guī)模復雜網(wǎng)絡的挑戰(zhàn)。因此，本文提出基于社區(qū)森林模型的分布式重疊社區(qū)發(fā)現(xiàn)算法，將社區(qū)發(fā)現(xiàn)應用到網(wǎng)絡表示學習領(lǐng)域，以此豐富網(wǎng)絡中節(jié)點和邊的特征，將分布式計算應用于重疊社區(qū)發(fā)現(xiàn)，提升社區(qū)發(fā)現(xiàn)算法的效率。

1 問題描述和形式化

CFM算法社區(qū)發(fā)現(xiàn)流程的特點，不需要復雜的迭代和采樣，因而更易于被擴展到主流大數(shù)據(jù)計算框架如Hadoop和Spark中。本文提出的DCFM算法，通過對社交網(wǎng)絡中邊的關(guān)系進行分析，挖掘社交網(wǎng)絡數(shù)據(jù)中節(jié)點之間以及社區(qū)之間的關(guān)系，為機器學習工作提供更豐富的表示學習特征。

1.1 問題描述

如何高效挖掘大規(guī)模網(wǎng)絡中節(jié)點、邊和社區(qū)等結(jié)構(gòu)更豐富的特征是本研究要解決的問題。借助分布式計算引擎的并行運算能力，利用社區(qū)森林模型深入挖掘詳細的網(wǎng)絡結(jié)構(gòu)，包括社區(qū)內(nèi)部結(jié)構(gòu)和外部邊界、社區(qū)之間的關(guān)系、節(jié)點和邊在網(wǎng)絡中所處的位置等，結(jié)合分布式計算引擎和社區(qū)森林模型，能夠高效挖掘網(wǎng)絡的豐富特征，為表示學習提供更多的支持。如果對大規(guī)模網(wǎng)絡進行并行運算，先要對其進行拆分，借助分布式文件系統(tǒng)對大文件分塊后，進行分布式冗余存儲。大規(guī)模網(wǎng)絡文件存儲的是節(jié)點之間的關(guān)系，這種文件被存儲到分布式文件系統(tǒng)后，網(wǎng)絡被隨機劃分成多個子網(wǎng)絡。在分布式計算平臺上的MapReduce計算架構(gòu)中，對子網(wǎng)絡使用CFM算法進行詳細網(wǎng)絡挖掘，再將各個子網(wǎng)絡中的社區(qū)進行合并，如果合并策略處理得當，這種方式的結(jié)果應該近似于整個網(wǎng)絡進行社區(qū)劃分的結(jié)果。合并結(jié)果的好壞取決于合并的標準。本文提出社區(qū)重疊率定義，根據(jù)社區(qū)之間的重疊率確定合并標準。基于重疊社區(qū)森林模型的社區(qū)發(fā)現(xiàn)算法設(shè)計思路可以概括如下：首先，將網(wǎng)絡進行分布式存儲;然后，將子網(wǎng)絡在分布式計算引擎上的MapReduce計算架構(gòu)中用CFM算法進行詳細社區(qū)劃分;最后，基于社區(qū)重疊率定義進行社區(qū)合并。

2 算法描述

DCFM可以描述為先將網(wǎng)絡數(shù)據(jù)集存儲到分布式文件系統(tǒng)上，分布式文件系統(tǒng)將數(shù)據(jù)分塊，在每個數(shù)據(jù)分塊中執(zhí)行CFM算法，然后執(zhí)行社區(qū)合并，最后匯總社區(qū)劃分結(jié)果。該算法的偽代碼如下。

步驟1：Input G（V，E），then put them on HDFS.//將G（V，E）存儲到分布式文件系統(tǒng)上，在分布式文件系統(tǒng)上將數(shù)據(jù)分塊;

步驟2：Graphx′s graphloader.edgelistfile method reads G（V，E） and generates a graph.//用GraphX圖處理工具生成圖;

步驟3：Caculate the backbone degree of E，then output backbone list.//進行骨干度計算;

步驟4：Put backbone list in distributed HDFS.//將骨干度列表上傳到分布式文件系統(tǒng)（如HDFS）上;

步驟5：Perform CFM algorithm in Map.//在Map中進行社區(qū)劃分;

步驟6：Make Community Merger in Reduce based on Coverage.//在Reduce中進行社區(qū)合并;

步驟7：Output the final results of community detection.//輸出合并后的社區(qū)劃分結(jié)果。

DCFM詳細流程圖如圖1所示。整個算法包括2個MapReduce流程。第1個MapReduce流程在步驟3中，使用分布式的MapReduce架構(gòu)計算圖中每條邊的骨干度;第2個MapReduce流程在步驟5和步驟6中。為了更直觀顯示，將步驟5和步驟6的MapReduce流程在圖1中展示，將步驟3計算骨干度在圖2中展示。圖1所示的步驟5中，首先在每個帶有骨干度列表信息的子圖中執(zhí)行CFM算法，獲得子社區(qū)的社區(qū)劃分結(jié)果，然后在步驟6中根據(jù)Coverage的閾值合并社區(qū)。

圖2中計算骨干度采用了GraphX的消息機制，該機制采用分布式圖運算架構(gòu)的底層運算邏輯，來源于經(jīng)典的標簽傳播算法。DCFM算法在各個子圖上進行分布式消息傳遞，然后在Reduce階段進行消息合并，從而巧妙地對圖中所有節(jié)點的鄰居信息進行統(tǒng)計，通過計算每個節(jié)點鄰居信息的交并比，獲得圖中每條邊的骨干度，最后獲得骨干度列表。

3 實驗內(nèi)容及結(jié)果討論

3.1 實驗環(huán)境

在3臺Dell R410服務器上搭建Spark集群，包括1臺Master節(jié)點和2臺Slave節(jié)點，其中Master節(jié)點16 G內(nèi)存，Slave節(jié)點8 G內(nèi)存，Yarn內(nèi)存總共21 G，提供jar包運行方式，使用Spark-Submit命令提交Spark應用。Spark版本：Spark2.2.0;Scala版本：Scala2.11;MySQL版本：MySQL5.7;CentOS版本：CentOS6.5;Hadoop版本：Hadoop2.7。每臺服務器內(nèi)存8 G。

CFM，Louvain，CFM和MMSB等算法的實驗環(huán)境如下。

服務器配置：Dell PowerEdge R720;CPU：Xeon E5-2603 * 2;內(nèi)存：384 G（DDR3 1 600 16 G * 24）;硬盤：300 G * 2。

操作系統(tǒng)：Windows server 2008，Ubuntu12.0 64 bit。

軟件：CFinder 2.0.6，SVINET 0.9-beta，CFM 0.1-beta，Louvin方法。

3.2 數(shù)據(jù)集

為了驗證分布式算法對計算效率的提升效果，采用學術(shù)界常用的2個大規(guī)模數(shù)據(jù)集：com-dblp.ungraph數(shù)據(jù)集和dblp20161201數(shù)據(jù)集。com-dblp.ungraph數(shù)據(jù)集是斯坦福大學SNAP研究組整理提供的DBLP學術(shù)協(xié)作網(wǎng)絡數(shù)據(jù)，dblp20161201數(shù)據(jù)集是從DBLP網(wǎng)站下載進行數(shù)據(jù)解析后生成的。這2個數(shù)據(jù)集的詳細描述見表1。為了驗證DCFM算法的有效性，從com-dblp.ungraph數(shù)據(jù)集中采樣出5個數(shù)據(jù)樣本，這5個數(shù)據(jù)樣本具有真實的社區(qū)劃分結(jié)果，因此可以采用F均值進行測評。

3.3 結(jié)果討論

先在具有真實社區(qū)劃分結(jié)果的5個社交網(wǎng)絡采樣上進行F均值評測，與CFM算法進行縱向?qū)Ρ?然后在大規(guī)模LFR數(shù)據(jù)集上進行F均值評測，并與CPM，Louvain，MMSB和CFM算法進行橫向?qū)Ρ龋C明DCFM算法的有效性，通過對大規(guī)模數(shù)據(jù)集上的運行時間進行對比，驗證DCFM算法對社區(qū)劃分效率的提升程度，調(diào)整DCFM算法中的3個關(guān)鍵參數(shù)對算法進行優(yōu)化。

3.3.1 F均值

首先采用5個樣本作為DBLP的標準數(shù)據(jù)，均有真實的社區(qū)劃分結(jié)果，運算完成后可以進行F均值評估。通過對比DCF算法和MCFM算法的F均值，評估DCFM算法是否可以在準確率和召回率方面與CFM算法相當，對比結(jié)果如表2所示。由表2可以看出，在DBLP樣本1—樣本3上，DCFM算法的F均值和CFM算法的F均值相差不大，在DBLP樣本4和樣本5上，DCFM算法的F均值不穩(wěn)定，考慮到運算速度的提升，其在F均值上的損失是可以均衡補償?shù)摹?/p>

LFR是對社區(qū)劃分結(jié)果進行評測的工具，可以產(chǎn)生具有重疊頂點的網(wǎng)絡。采用LFR生成數(shù)據(jù)集，命令如下：“/ benchmark -N n -k 15 -maxk 50 -mu 0.2 -minc 20 -maxc 50 -on 0.1 n -om 4”，產(chǎn)生從1 000到100萬節(jié)點的數(shù)據(jù)集，其中n是節(jié)點數(shù)，平均度為15，最大度為50，混合參數(shù)為0.2，社區(qū)大小的最小值為20，社區(qū)大小的最大值為50，重疊節(jié)點數(shù)為0.1 * n，重疊頂點的成員數(shù)為4。在該數(shù)據(jù)集上分別評測CPM，Louvain，MMSB，CFM和DCFM算法的F均值，對比結(jié)果如圖3所示。

圖3結(jié)果表明：CPM和MMSB兩者的F均值不穩(wěn)定，其中MMSB在PowerEdge R720上運行20 d以上無法獲得社區(qū)劃分結(jié)果，因此曲線不完整;Louvain的F均值曲線隨頂點數(shù)的增加而迅速下降;CFM在從1 000到1 000 000的LFR數(shù)據(jù)集中，性能非常穩(wěn)定，F(xiàn)均值保持在60%左右，大多高于DCFM，CPM，Louvain和MMSB算法，僅當CPM算法 k=3且頂點數(shù)> 10 000時F均值才低于CPM;DCFM算法的F均值雖稍低于CFM算法，但在多數(shù)LFR數(shù)據(jù)集中略好于Louvain和MMSB，也略好于當k>4時的CPM算法，但是低于當k=3和k=4時的CPM算法。綜合來說，由于DCFM可以在當前主流大數(shù)據(jù)框架Spark上運行，即使F均值略有不足，相對于其在實際海量復雜網(wǎng)絡挖掘中的作用來說，該算法也是一個不錯的選擇。

通過F均值實驗可知，雖然DCFM算法的F均值稍遜于CFM算法，但是由于DCFM算法對大規(guī)模網(wǎng)絡的處理能力要遠勝于CFM算法，因此DCFM算法在以犧牲小部分F均值作為代價的前提下，具備了大規(guī)模網(wǎng)絡數(shù)據(jù)處理能力，而這種分布式處理能力是當前工業(yè)界大規(guī)模網(wǎng)絡分析應用迫切需要的。

3.3.2 運行時間

為了驗證分布式算法對計算速度的提升，采用2個較大的數(shù)據(jù)集（com-dblp.ungraph數(shù)據(jù)集，包含317 080個節(jié)點和1 049 866條邊;dblp20161201數(shù)據(jù)集，包含1 072 373個節(jié)點和4 222 019條邊），通過調(diào)整參數(shù)partitionNum，評估DCMF算法的運行時間。分別計算2個不同大小的數(shù)據(jù)集在不同分割份數(shù)下的運行時間，使用Hash方式將圖分割成不同份數(shù)，結(jié)果如表3所示。在com-dblp.ungraph.txt數(shù)據(jù)集上，CFM算法處理該數(shù)據(jù)需要192 min，而DCFM算法在將數(shù)據(jù)分成6份時，需要約91 min，而分成100份后僅需要約13 min。在dblp20161201.txt數(shù)據(jù)集上，CFM算法處理該數(shù)據(jù)需要798 min，而DCFM算法在將數(shù)據(jù)分成100份時需要約303 min，而分成1 000份后僅需要約42 min。結(jié)果表明，分割份數(shù)對計算時間的影響很大，DCFM算法通過將網(wǎng)絡進行分割，可以大幅度提高社區(qū)劃分的速度。

運行時間與分割份數(shù)之間的關(guān)系如圖4所示，可以更清晰地展示分割分數(shù)和運行時間的負相關(guān)關(guān)系，即分割分數(shù)越多，運行時間越短。

通過調(diào)節(jié)分割份數(shù)來獲得最佳運算時間是可行的。目前，工業(yè)界要處理的大規(guī)模網(wǎng)絡包含數(shù)億節(jié)點和幾十億條邊，在這種需求背景下，單機社區(qū)發(fā)現(xiàn)算法已無法滿足網(wǎng)絡分析的時效性要求。例如基于圖的推薦任務中，國內(nèi)互聯(lián)網(wǎng)用戶節(jié)點數(shù)量過億，單機社區(qū)發(fā)現(xiàn)算法已很難滿足時效性的要求。DCFM算法將大規(guī)模網(wǎng)絡進行分塊，通過分布式運行CFM算法，再根據(jù)重合率進行合并，充分利用分布式集群的算力，提高了重疊社區(qū)發(fā)現(xiàn)算法的處理速度。

3.3.3 參數(shù)

DCFM算法中包含3個可調(diào)參數(shù)：partitionNum，Threshold和Coverage，通過對這3個參數(shù)進行配合調(diào)整，可以得到運算最快、效率最高、F均值最高的模型。通過調(diào)整partitionNum參數(shù)，可以使全部數(shù)據(jù)分成partitonNum份，對于并行計算來說，并不是partitonNum的值越大越好，該值越大task越多，反而會增加系統(tǒng)調(diào)度任務的時間。通過調(diào)整Threshold參數(shù)，可以控制社區(qū)劃分精度。社區(qū)劃分是取最大骨干度中2個節(jié)點作為初始社區(qū)，然后逐個加入其他節(jié)點，Threshold參數(shù)為最小可以被取出當做初始社區(qū)的骨干度。通過調(diào)整Coverage參數(shù)，可以在社區(qū)合并時控制社區(qū)相似度為多少時可以合并，參數(shù)Coverage代表可以合并社區(qū)相似度的最小值。參數(shù)Coverage不是越小越好，也不是越大越好，需要進行優(yōu)化。

1）Threshold參數(shù)

觀察數(shù)據(jù)集DBLP樣本1的計算結(jié)果。其骨干度為0.03～1.169，固定參數(shù)Threshold為0.01，將所有邊的2個節(jié)點都當作潛在初始社區(qū);Coverage為0.0～1.0，固定參數(shù)Coverage為0.01時，除了社區(qū)之間Coverage為0時不會合并，其他都將進行社區(qū)合并操作。固定參數(shù)Coverage為0.01時，調(diào)整參數(shù)Threshold的大小，查看不同參數(shù)Threshold對算法F均值的影響，結(jié)果如表4所示，其中Threshold為閾值，Coverage為最大的重疊率，F(xiàn)均值為評估社區(qū)發(fā)現(xiàn)效果的值。由表4數(shù)據(jù)可以發(fā)現(xiàn)，Threshold越小，F(xiàn)均值相對越大，計算效果越好。

2）Coverage參數(shù)

固定參數(shù)Threshold為0.01，調(diào)整參數(shù)Coverage的大小，查看不同參數(shù)Coverage對算法F均值的影響，結(jié)果如表5所示，其中Threshold為閾值，Coverage為最大的重疊率，F(xiàn)均值為評估社區(qū)發(fā)現(xiàn)效果的值。由表5可知，Coverage越小，F(xiàn)均值越大，計算效果越好。

將表4和表5的參數(shù)調(diào)優(yōu)數(shù)據(jù)進行可視化，結(jié)果如圖5所示。由圖5可以看出，Coverage和Threshhold參數(shù)對F均值有直接影響，它們與F均值呈負相關(guān)的關(guān)系，即二者值越大，F(xiàn)均值越小。因此要使DCFM具有最佳性能，必須將這2個參數(shù)設(shè)置得越小越好，經(jīng)驗值是將二者都設(shè)置成0.01。

通過參數(shù)調(diào)優(yōu)實驗可知，調(diào)節(jié)參數(shù)Threshold和參數(shù)Coverage，可以顯著提高算法的F均值。但是算法需要兼顧速度和F均值，所以對于大規(guī)模社交網(wǎng)絡而言，有時需要犧牲部分F均值來換取計算速度。

4 結(jié) 語

1）本文針對傳統(tǒng)單機重疊社區(qū)發(fā)現(xiàn)算法已經(jīng)不能適應當前大規(guī)模復雜網(wǎng)絡挖掘需求，以及不能支持來自網(wǎng)絡表示學習任務的迫切需求這2個問題，提出了基于社區(qū)森林模型的分布式重疊社區(qū)發(fā)現(xiàn)算法（簡稱DCFM算法）：將網(wǎng)絡數(shù)據(jù)集存儲到分布式HDFS上，由HDFS系統(tǒng)將數(shù)據(jù)分塊，在每個數(shù)據(jù)分塊中執(zhí)行CFM算法，然后執(zhí)行社區(qū)合并，最后對社區(qū)劃分結(jié)果進行匯總。

2）將DCFM算法運用于5個真實的DBLP采樣數(shù)據(jù)集，結(jié)果表明，其F均值稍遜于CFM算法，但是CFM算法對大規(guī)模網(wǎng)絡的處理能力要遠遜色于DCFM算法。此外，通過與CFM，CPM，Louvain和MMSB等算法進行橫向?qū)Ρ瓤芍珼CFM算法具有競爭力。因此，DCFM算法在犧牲小部分F均值的同時，具備了大規(guī)模網(wǎng)絡數(shù)據(jù)處理能力，這種分布式處理能力是當前工業(yè)界大規(guī)模網(wǎng)絡分析應用迫切需要的。

3）工業(yè)界目前要處理的大規(guī)模網(wǎng)絡包含數(shù)億個節(jié)點和幾十億條邊。在這種需求背景下，單機社區(qū)發(fā)現(xiàn)算法無法滿足其對網(wǎng)絡分析的時效性要求，但通過調(diào)節(jié)分割份數(shù)來獲得最佳運算時間是可行的。

4）調(diào)節(jié)Threshold參數(shù)和Coverage參數(shù)可以提升算法的F均值。用戶通過調(diào)節(jié)這2個參數(shù)，可使二者之間達到動態(tài)平衡，獲得更為滿意的社區(qū)劃分結(jié)果。

5）結(jié)合Spark和Hadoop等分布式計算架構(gòu)，對大規(guī)模復雜網(wǎng)絡數(shù)據(jù)進行分布式處理，可以有效提升社區(qū)發(fā)現(xiàn)算法的處理速度;同時，采用該算法對社交網(wǎng)絡中的邊關(guān)系進行計算分析，挖掘社交網(wǎng)絡數(shù)據(jù)中節(jié)點之間以及社區(qū)之間的關(guān)系，還可為機器學習工作提供更為豐富的表示學習特征。

6）DCFM算法目前在F均值方面與CFM算法仍有一定的差距，需要加以改進。未來工作中，如果想進一步提升算法的性能，還需要更換其他方法進行社區(qū)合并。如果突破了這個瓶頸，那么本算法將會獲得更好的性能。

參考文獻/References：

[1] ZHANG Y，XU H，XU Y F，et al.Finding structural hole spanners based on community forest model and diminishing marginal utility in large scale social networks[J].Knowledge-Based Systems，2020，199：105916.

[2] PHAM P，NGUYEN L T T，VO B，et al.Bot2Vec：A general approach of intra-community oriented representation learning for bot detection in different types of social networks[J].Information Systems，2022，103：101771.

[3] 吳衛(wèi)江，桑睿彤，鄭藝峰.基于限制性隨機游走局部譜近似社區(qū)發(fā)現(xiàn)算法[J].計算機工程與設(shè)計，2021，42（9）：2472-2477.

WU Weijiang，SANG Ruitong，ZHENG Yifeng.Local spectrum approximation algorithm with limited random walk for community detection[J].Computer Engineering and Design，2021，42（9）：2472-2477.

[4] 陳界全，王占全，李真，等.基于SLPA優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法[J].計算機應用與軟件，2021，38（1）：297-302.

CHEN Jiequan，WANG Zhanquan，LI Zhen，et al.An improved overlapping community detection algorithm based on slpa[J].Computer Applications and Software，2021，38（1）：297-302.

[5] 王得翊，焦澳琛，陳音拿，等.基于多階局部度數(shù)峰值點的局部社區(qū)發(fā)現(xiàn)算法[J].微型電腦應用，2021，37（6）：1-4.

WANG Deyi，JIAO Aochen，CHEN Yinna，et al.Local community detection based on n-order local degree central nodes[J].Microcomputer Applications，2021，37（6）：1-4.

[6] JALALI S，HOSSEINI M.Social collaborative filtering using local dynamic overlapping community detection[J].The Journal of Supercomputing，2021，77（10）：11786-11806.

[7] BAHADORI S，ZARE H，MORADI P.PODCD：Probabilistic overlapping dynamic community detection[J].Expert Systems with Applications，2021，174：114650.

[8] GAO Y，YU X Z，ZHANG H L.Overlapping community detection by constrained personalized PageRank[J].Expert Systems With Applications，2021，173：114682.

[9] ASMI K，LOTFI D，ABARDA A.The greedy coupled-seeds expansion method for the overlapping community detection in social networks[J].Computing，2022，104（2）：295-313.

[10]ATTAL J P，MALEK M，ZOLGHADRI M.Overlapping community detection using core label propagation algorithm and belonging functions[J].Applied Intelligence，2021，51（11）：8067-8087.

[11]BENNCIR C E，MAIZA I，BOUAGUEL W，et al.Disjoint and non-disjoint community detection with control of overlaps between communities[J].SN Computer Science，2021，2（1）：15.

[12]NADERIPOUR M，F(xiàn)AZEL ZARANDI M H，BASTANI S.Fuzzy community detection on the basis of similarities in structural/attribute in large-scale social networks[J].Artificial Intelligence Review，2022，55（2）：1373-1407.

[13]BAHADORI S，MORADI P，ZARE H.An improved limited random walk approach for identification of overlapping communities in complex networks[J].Applied Intelligence，2021，51（6）：3561-3580.

[14]WAN X，ZUO X Q，SONG F.Solving dynamic overlapping community detection problem by a multiobjective evolutionary algorithm based on decomposition[J].Swarm and Evolutionary Computation，2020，54：100668.

[15]GAO R，LI S F，SHI X H，et al.Overlapping community detection based on membership degree propagation[J].Entropy，2020，23（1）：15.

[16]劉強，賈焰，方濱興，等.并行社區(qū)發(fā)現(xiàn)算法的可擴展性研究[J].通信學報，2018，39（4）：13-20.

LIU Qiang，JIA Yan，F(xiàn)ANG Binxing，et al.Research on the scalability of parallel community detection algorithms[J].Journal on Communications，2018，39（4）：13-20.

[17]ROGHANI H，BOUYER A，NOURANI E.PLDLS：A novel parallel label diffusion and label selection：Based community detection algorithm based on Spark in social networks[J].Expert Systems with Applications，2021，183：115377.

[18]葉小榕，邵晴.基于Spark的大規(guī)模社交網(wǎng)絡社區(qū)發(fā)現(xiàn)原型系統(tǒng)[J].科技導報，2018，36（23）：93-101.

YE Xiaorong，SHAO Qing.A large scale social networking community detection prototype system based on Spark[J].Science & Techno-logy Review，2018，36（23）：93-101.

[19]XU Y F，XU H，ZHANG D W.A novel disjoint community detection algorithm for social networks based on backbone degree and expansion[J].Expert Systems with Applications，2015，42（21）：8349-8360.

[20]胡旭飛，許云峰.基于骨干度與網(wǎng)絡編碼的鏈路預測模型研究[J].河北工業(yè)科技，2019，36（5）：310-313.

HU Xufei，XU Yunfeng.Research on link prediction model based on backbone degree and network coding[J].Hebei Journal of Industrial Science & Technology，2019，36（5）：310-313.

[21]LI M Z，LU S Y，ZHANG L L，et al.A community detection method for social network based on community embedding[J].IEEE Transactions on Computational Social Systems，2021，8（2）：308-318.

[22]XU Y F，XU H，ZHANG D W，et al.Finding overlapping community from social networks based on community forest model[J].Know-ledgeBased Systems，2016，109：238-255.