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

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

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

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

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

中圖分類號：TP311.13 文獻(xiàn)標(biāo)識碼：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

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

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

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

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

1 問題描述和形式化

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

1.1 問題描述

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

2 算法描述

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

步驟1：Input G（V，E），then put them on HDFS.//將G（V，E）存儲(chǔ)到分布式文件系統(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.//進(jìn)行骨干度計(jì)算;

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)環(huán)境

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

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

服務(wù)器配置：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ù)集

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

3.3 結(jié)果討論

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

3.3.1 F均值

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

LFR是對社區(qū)劃分結(jié)果進(jìn)行評測的工具，可以產(chǎn)生具有重疊頂點(diǎn)的網(wǎng)絡(luò)。采用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é)點(diǎn)的數(shù)據(jù)集，其中n是節(jié)點(diǎn)數(shù)，平均度為15，最大度為50，混合參數(shù)為0.2，社區(qū)大小的最小值為20，社區(qū)大小的最大值為50，重疊節(jié)點(diǎn)數(shù)為0.1 * n，重疊頂點(diǎn)的成員數(shù)為4。在該數(shù)據(jù)集上分別評測CPM，Louvain，MMSB，CFM和DCFM算法的F均值，對比結(jié)果如圖3所示。

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

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

3.3.2 運(yùn)行時(shí)間

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

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

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

3.3.3 參數(shù)

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

1）Threshold參數(shù)

觀察數(shù)據(jù)集DBLP樣本1的計(jì)算結(jié)果。其骨干度為0.03～1.169，固定參數(shù)Threshold為0.01，將所有邊的2個(gè)節(jié)點(diǎn)都當(dāng)作潛在初始社區(qū);Coverage為0.0～1.0，固定參數(shù)Coverage為0.01時(shí)，除了社區(qū)之間Coverage為0時(shí)不會(huì)合并，其他都將進(jìn)行社區(qū)合并操作。固定參數(shù)Coverage為0.01時(shí)，調(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)均值相對越大，計(jì)算效果越好。

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)均值越大，計(jì)算效果越好。

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

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

4 結(jié) 語

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

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

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

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

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

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

參考文獻(xiàn)/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)江，桑睿彤，鄭藝峰.基于限制性隨機(jī)游走局部譜近似社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，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].計(jì)算機(jī)應(yīng)用與軟件，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ù)峰值點(diǎn)的局部社區(qū)發(fā)現(xiàn)算法[J].微型電腦應(yīng)用，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]劉強(qiáng)，賈焰，方濱興，等.并行社區(qū)發(fā)現(xiàn)算法的可擴(kuò)展性研究[J].通信學(xué)報(bào)，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)絡(luò)社區(qū)發(fā)現(xiàn)原型系統(tǒng)[J].科技導(dǎo)報(bào)，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)絡(luò)編碼的鏈路預(yù)測模型研究[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.