李春英，湯志康+，湯 庸，趙劍冬，黃泳航

1.廣東技術(shù)師范學(xué)院 計算機科學(xué)學(xué)院，廣州 510665

2.華南師范大學(xué) 計算機科學(xué)學(xué)院，廣州 510631

1 引言

隨著網(wǎng)絡(luò)技術(shù)、智能終端以及計算交流技術(shù)的快速發(fā)展，社會網(wǎng)絡(luò)（social network service，SNS）已經(jīng)成為互聯(lián)網(wǎng)時代最具影響力的應(yīng)用。這些以人為中心的社會網(wǎng)絡(luò)是智能化程度很高的復(fù)雜網(wǎng)絡(luò)，受人的世界觀、生活環(huán)境、所處位置、興趣愛好等的影響，其遵循著“物以類聚、人以群分”（社區(qū)結(jié)構(gòu)）的特點。而在真實社區(qū)結(jié)構(gòu)中，一些用戶可能同時屬于親人社區(qū)、朋友社區(qū)、興趣愛好社區(qū)等多個不同的社區(qū)，這樣的社區(qū)稱之為重疊社區(qū)。重疊社區(qū)檢測研究為在線社會網(wǎng)絡(luò)的推薦系統(tǒng)[1-2]、鏈接預(yù)測[3-4]、異質(zhì)網(wǎng)絡(luò)分析[5]、社會網(wǎng)絡(luò)演變[6]等提供決策性支持，使社會網(wǎng)絡(luò)在為用戶提供優(yōu)質(zhì)服務(wù)的同時也為其保持用戶的粘性和持續(xù)活躍度提供了幫助。

社區(qū)檢測也叫作社區(qū)聚簇，近十年已成為計算機、物理、生物、社會學(xué)以及復(fù)雜性系統(tǒng)科學(xué)等多學(xué)科的研究熱點。學(xué)者們從不同角度對社區(qū)檢測算法進(jìn)行了嘗試，如模塊度算法[7-8]、層次聚類算法[9-10]、基于k-clique的算法[11-12]、基于鏈接聚類的算法[13-14]、基于局部優(yōu)化和擴展的算法[15]以及基于標(biāo)簽傳播的算法（label propagation algorithm，LPA）[16]等。其中，基于標(biāo)簽傳播的社區(qū)檢測算法提出了一個很好的視角，采用信息傳播來確定復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。因其簡單易行而受到學(xué)者的廣泛關(guān)注。LPA算法采用獨一無二的標(biāo)簽對網(wǎng)絡(luò)中的節(jié)點進(jìn)行初始化，在每一步標(biāo)簽更新中，節(jié)點吸收其鄰居節(jié)點最大的標(biāo)簽。這種基于agent和分散的方法使LPA算法不需要先驗知識且擁有近似線性的時間復(fù)雜度，因而能夠適應(yīng)于擁有百萬級節(jié)點的復(fù)雜網(wǎng)絡(luò)[17]。但是LPA算法的異步更新方式導(dǎo)致其具有較弱的健壯性。針對這個問題，文獻(xiàn)[18]結(jié)合同步更新和異步更新策略，提出LPA算法的半同步更新版本。實驗結(jié)果表明該算法提高了LPA算法的性能和健壯性。文獻(xiàn)[19]綜合考慮頂點鄰居中相同標(biāo)簽所占比例、頂點度數(shù)和邊的權(quán)重等信息來計算每個頂點的標(biāo)簽影響值并更新頂點的標(biāo)簽。文獻(xiàn)[20]提出LPA算法的同步更新版本（synchronous version of LPA，LPA-S）。LPA-S算法使用獨一無二的標(biāo)簽對復(fù)雜網(wǎng)絡(luò)中的節(jié)點進(jìn)行初始化，并提出概率更新策略避免在同步更新時產(chǎn)生標(biāo)簽振蕩現(xiàn)象。但是，文獻(xiàn)[16-20]均是針對復(fù)雜網(wǎng)絡(luò)非重疊社區(qū)的檢測算法。

實際上，社區(qū)重疊是真實復(fù)雜網(wǎng)絡(luò)非常重要的特征，重疊節(jié)點在復(fù)雜網(wǎng)絡(luò)中通常扮演著重要的角色[21]。因此，文獻(xiàn)[22]提出了多標(biāo)簽同步傳播算法（community overlap propagation algorithm，COPRA）檢測復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)。該算法繼承了LPA算法時間復(fù)雜度低、適用大型網(wǎng)絡(luò)等優(yōu)點。但是其通過輸入?yún)?shù)v控制節(jié)點所屬的社區(qū)個數(shù)，這難于適應(yīng)節(jié)點所屬社區(qū)個數(shù)差異較大的真實社會網(wǎng)絡(luò)。另外，一些算法[23-24]的實驗結(jié)果表明，COPRA算法在一些復(fù)雜網(wǎng)絡(luò)的社區(qū)劃分結(jié)果中存在過擬合現(xiàn)象，即社區(qū)劃分結(jié)果產(chǎn)生了一個包含所有節(jié)點的大社區(qū)。文獻(xiàn)[23]提出了最小極大團(tuán)標(biāo)簽傳播算法（minimal maximal clique label propagation algorithm，MMCLPA）檢測復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)。該算法采用最小極大團(tuán)及自適應(yīng)閾值的方式提高了算法的質(zhì)量并克服了預(yù)先輸入?yún)?shù)對未知復(fù)雜網(wǎng)絡(luò)的局限性等問題。但文獻(xiàn)[25]在真實社會網(wǎng)絡(luò)中的實驗結(jié)果表明MMCLPA算法的自適應(yīng)閾值偏小，可能導(dǎo)致一些社會網(wǎng)絡(luò)的社區(qū)檢測結(jié)果中存在過多重疊節(jié)點。另外，MMCLPA算法中可能存在同步和異步兩種標(biāo)簽更新方式，這可能引起不穩(wěn)定的社區(qū)檢測質(zhì)量。劉世超等[26]提出一種基于標(biāo)簽傳播概率的重疊社區(qū)發(fā)現(xiàn)算法（label-propagation-probability-based，LPPB），LPPB算法根據(jù)節(jié)點的影響力大小進(jìn)行更新，綜合網(wǎng)絡(luò)結(jié)構(gòu)的傳播特性、節(jié)點的屬性特征和歷史標(biāo)簽記錄信息等計算及修正標(biāo)簽的傳播概率及更新結(jié)果。和COPRA算法一樣，LPPB算法通過輸入?yún)?shù)調(diào)整節(jié)點可以擁有的最大標(biāo)簽數(shù)，預(yù)先輸入?yún)?shù)的方法使得LPPB算法很難適應(yīng)各種類型真實社會網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)檢測。

基于以上研究以及文獻(xiàn)[27-28]提出的在微觀層次上更加易于檢測高質(zhì)量的社區(qū)結(jié)構(gòu)等觀點，提出基于微觀結(jié)構(gòu)極大團(tuán)的同步自適應(yīng)標(biāo)簽傳播算法（synchronous adaptive label propagation algorithm，ALPA-S）和異步自適應(yīng)標(biāo)簽傳播算法（asynchronous adaptive label propagation algorithm，ALPA-A）檢測社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。本文的主要貢獻(xiàn)可以概括為兩點：（1）兩種算法均以微觀結(jié)構(gòu)極大團(tuán)作為社區(qū)結(jié)構(gòu)的核心，通過相應(yīng)更新規(guī)則實現(xiàn)節(jié)點的標(biāo)簽更新，算法全程不需要參數(shù)控制，極大團(tuán)中節(jié)點數(shù)和標(biāo)簽權(quán)重閾值均會根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及節(jié)點標(biāo)簽個數(shù)的不同而自動調(diào)整，使算法能夠更好地適應(yīng)多種拓?fù)浣Y(jié)構(gòu)類型的社會網(wǎng)絡(luò)。（2）兩種算法均可用于檢測社會網(wǎng)絡(luò)中的重疊社區(qū)和非重疊社區(qū)，具有良好的適應(yīng)性。

2 ALPA-S算法

2.1 初始化

k-core[29]是圖論中一個非常重要的概念，其被廣泛應(yīng)用于網(wǎng)絡(luò)結(jié)構(gòu)可視化[30-31]，解釋社會網(wǎng)絡(luò)的協(xié)同過程[32-33]，分析復(fù)雜網(wǎng)絡(luò)中節(jié)點的層次和連通性[34]以及分析復(fù)雜網(wǎng)絡(luò)的發(fā)展和演化[35]等。在社區(qū)檢測方面，常常利用k-core作為子路線解決復(fù)雜網(wǎng)絡(luò)中的難題，如計算k-clique、計算連接關(guān)系緊密的子圖以及求解至少k度子圖（at-least-k-subgraph）的問題等[36-37]?？紤]到社會網(wǎng)絡(luò)中影響力大的節(jié)點對社區(qū)的形成具有一定的促進(jìn)作用以及基于微觀角度更加易于檢測社區(qū)結(jié)構(gòu)等問題，提出基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)度量節(jié)點的影響力，并按照節(jié)點影響力強弱在社會網(wǎng)絡(luò)中依次尋找局部極大團(tuán)（如定義1），并為極大團(tuán)中的節(jié)點賦予標(biāo)簽及權(quán)重。

定義1（極大團(tuán)）社會網(wǎng)絡(luò)被模型化為圖G={V,E}的形式，其中V表示社會網(wǎng)絡(luò)節(jié)點集合，E表示節(jié)點間相鄰關(guān)系集合。每個節(jié)點vi(vi∈V)都有一個標(biāo)簽集合Ci,N(vi)是節(jié)點vi的鄰居節(jié)點集合，|N(vi)|代表節(jié)點vi的影響力。以V中Ci=的影響力最大節(jié)點vi及N(vi)中標(biāo)簽集為空的影響力最大節(jié)點vj構(gòu)成的邊(vi,vj)為初始邊，按照節(jié)點影響力強弱構(gòu)建完全圖Gm，稱Gm為團(tuán)。若Gm?G，且不存在完全圖Gt?G，使得Gm?Gt，則稱Gm為極大團(tuán)（maximal clique），簡稱MC。

按照定義1，一個極大團(tuán)至少包含3個節(jié)點。實際上，文獻(xiàn)[25]已經(jīng)表明3個節(jié)點可以構(gòu)成一個小型社區(qū)。同時，為了降低算法的運行時間以及避免類似CPM算法[11]在稠密復(fù)雜網(wǎng)絡(luò)中尋找全部極大團(tuán)耗費大量時間等問題，提出的極大團(tuán)在復(fù)雜網(wǎng)絡(luò)中是唯一的，即任何兩個極大團(tuán)間的交集為空集。結(jié)合定義1，ALPA-S算法標(biāo)簽初始化過程如下所示。

（1）對于社會網(wǎng)絡(luò)中的任一節(jié)點vi的標(biāo)簽集Ci，設(shè)置Ci←? ；

（2）c←1；

（3）按照定義1尋找MC，對MC中的每一個節(jié)點vi的標(biāo)簽集Ci，令Ci←{(c,1)}；

（4）c←c+1；

（5）重復(fù)步驟（3）、（4），直到?jīng)]有滿足要求的節(jié)點為止。

按照算法初始化規(guī)則，ALPA-S算法在圖1所示的復(fù)雜網(wǎng)絡(luò)中共找到2個極大團(tuán)，分別為(a,b,c)和(e,g,f)。并且極大團(tuán)(a,b,c)中節(jié)點標(biāo)簽和權(quán)重均為1；極大團(tuán)(e,g,f)中的節(jié)點標(biāo)簽均為2，權(quán)重也均為1。如圖1所示。初始化后MC中的節(jié)點均擁有了標(biāo)簽和權(quán)重，而非MC節(jié)點則沒有獲得標(biāo)簽和權(quán)重。根據(jù)復(fù)雜網(wǎng)絡(luò)小世界模型，只要節(jié)點擁有鄰居，則在算法標(biāo)簽更新中可使其獲得標(biāo)簽。

Fig.1 Complex network initialized graph圖1 復(fù)雜網(wǎng)絡(luò)初始化結(jié)果圖

2.2 迭代過程

復(fù)雜網(wǎng)絡(luò)初始化后，一些節(jié)點獲得了標(biāo)簽和權(quán)重，這些標(biāo)簽和權(quán)重成為算法迭代開始時的種子。算法迭代時，節(jié)點繼承其所有鄰居節(jié)點的標(biāo)簽及按照權(quán)重更新規(guī)則產(chǎn)生的權(quán)重值。通過對復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及節(jié)點所屬社區(qū)情況的深度分析可知，節(jié)點是否屬于某個社區(qū)與節(jié)點在該社區(qū)對應(yīng)標(biāo)簽下的權(quán)重有關(guān)，而節(jié)點在某個標(biāo)簽下的權(quán)重值則與節(jié)點在該標(biāo)簽下的度數(shù)分布情況有關(guān)。例如，復(fù)雜網(wǎng)絡(luò)中的一個5度節(jié)點vi，其中4度貢獻(xiàn)給了社區(qū)1，說明在vi的5個關(guān)系中與社區(qū)1中的節(jié)點有4條連接關(guān)系；1度貢獻(xiàn)給了社區(qū)2，說明vi的5個關(guān)系中與社區(qū)2中的節(jié)點有1條連接關(guān)系。直觀上講，該節(jié)點vi應(yīng)該更大程度上屬于社區(qū)1，而不屬于社區(qū)2。因此，標(biāo)簽權(quán)重的計算方法需要充分考慮節(jié)點度數(shù)在各個標(biāo)簽下的分布并且要避免某個鄰居節(jié)點標(biāo)簽權(quán)重過大產(chǎn)生的“吞噬”問題。根據(jù)以上分析，提出權(quán)重計算公式（1）。假設(shè)函數(shù)bt(c,vi)表示在第t輪迭代時標(biāo)簽c在節(jié)點vi下的權(quán)重值。在ALPA-S算法中，權(quán)重的更新方法如式（1）所示。

其中，N(vi)表示節(jié)點vi所有鄰居節(jié)點的集合。節(jié)點vi在第t-1步已經(jīng)擁有標(biāo)簽c，則節(jié)點vi在第t步更新時，如果其鄰居節(jié)點vj也擁有標(biāo)簽c，則節(jié)點vi在第t步標(biāo)簽c下的權(quán)重值為其在第t-1步標(biāo)簽c的權(quán)重值與其鄰居節(jié)點vj在第t-1步標(biāo)簽c的權(quán)重值與節(jié)點vi度數(shù)的比值之和。若被更新節(jié)點vi中第t步?jīng)]有鄰居節(jié)點的標(biāo)簽c，則bt-1(c,vi)值為0。節(jié)點vi接收鄰居節(jié)點的標(biāo)簽c作為新標(biāo)簽，并按照式（1）計算標(biāo)簽c對應(yīng)的權(quán)重。

另外，考慮到社區(qū)結(jié)構(gòu)的局部性以及為了避免無效標(biāo)簽被傳播得更遠(yuǎn)，ALPA-S算法在每次迭代后對所有節(jié)點下的標(biāo)簽進(jìn)行處理。COPRA算法將預(yù)先輸入?yún)?shù)v的倒數(shù)作為節(jié)點標(biāo)簽是否有意義的判斷閾值。與參數(shù)v并不一定適用于社會網(wǎng)絡(luò)中所有節(jié)點一樣，將作為所有節(jié)點標(biāo)簽權(quán)重是否有意義的判斷閾值也不一定合適。受COPRA算法的啟發(fā)，將作為節(jié)點標(biāo)簽是否有意義的判斷條件。與COPRA算法不同的是是一個與每個節(jié)點的標(biāo)簽個數(shù)L有關(guān)的變量，把這個變量叫作自適應(yīng)閾值，具體如定義2所示。

定義2（自適應(yīng)閾值）如果一個節(jié)點vi擁有L個標(biāo)簽，則每個有意義標(biāo)簽的權(quán)重值應(yīng)該大于等于即為節(jié)點vi對應(yīng)的權(quán)重閾值。每個節(jié)點在每次迭代后擁有的標(biāo)簽個數(shù)不同，權(quán)重閾值因此也不同。把隨著節(jié)點標(biāo)簽個數(shù)發(fā)生變化的變量叫作自適應(yīng)閾值。

ALPA-S算法迭代過程如下所示。

（1）t←1。

（2）按照式（1）更新節(jié)點的標(biāo)簽及權(quán)重。

（4）歸一化所保留節(jié)點的標(biāo)簽權(quán)重，使其和為1。

（5）如果每個節(jié)點都擁有了標(biāo)簽，則算法停止。

（6）否則t←t+1，重復(fù)步驟（2）～（5）。

按照算法的迭代規(guī)則，對圖1復(fù)雜網(wǎng)絡(luò)初始化結(jié)果進(jìn)行第1輪迭代后，節(jié)點標(biāo)簽權(quán)重的一種更新結(jié)果為同時，按照自適應(yīng)閾值剔除無意義的標(biāo)簽及權(quán)重。具體過程為：僅有一個標(biāo)簽的節(jié)點不作處理，包含2個及以上標(biāo)簽的節(jié)點為e、g、f、a。其中，節(jié)點e有兩個標(biāo)簽，因此對應(yīng)的自適應(yīng)閾值為，刪除標(biāo)簽權(quán)重小于的標(biāo)簽權(quán)重有序?qū)?，則節(jié)點e僅剩下標(biāo)簽2，為其余3個節(jié)點g、f、a與節(jié)點e自適應(yīng)閾值相同，使用類似的方法刪除權(quán)重小于的標(biāo)簽權(quán)重有序?qū)?，結(jié)果為最后對所有節(jié)點的標(biāo)簽權(quán)重歸一化處理，結(jié)果為圖2顯示了ALPAS算法按照標(biāo)簽更新規(guī)則迭代1次后并進(jìn)行歸一化處理后的結(jié)果。

Fig.2 Propagation of labels:first iteration圖2 第1次標(biāo)簽傳播后的復(fù)雜網(wǎng)絡(luò)結(jié)果圖

2.3 終止條件

考慮到社區(qū)結(jié)構(gòu)的局部性以及離極大團(tuán)較遠(yuǎn)的節(jié)點擁有標(biāo)簽即達(dá)到了局部社區(qū)劃分的目的，使用所有節(jié)點擁有標(biāo)簽作為ALPA-S算法迭代終止的條件。這個終止條件可以使標(biāo)簽在有意義的局部范圍內(nèi)傳播并有效減少算法的迭代次數(shù)，同時可以避免同步更新算法（如DLPA[38]）為了達(dá)到穩(wěn)定狀態(tài)而產(chǎn)生的標(biāo)簽振蕩問題以及過擬合現(xiàn)象等。按照這個終止條件，圖1所示復(fù)雜網(wǎng)絡(luò)在第1次迭代后，所有節(jié)點都擁有了標(biāo)簽，則ALPA-S算法終止。

2.4 后期處理

在ALPA-S算法中，標(biāo)簽的數(shù)量是復(fù)雜網(wǎng)絡(luò)中不相交極大團(tuán)的數(shù)量。隨著迭代過程的推進(jìn)，標(biāo)簽數(shù)量逐漸減少。當(dāng)算法終止時，剩余標(biāo)簽的數(shù)量代表復(fù)雜網(wǎng)絡(luò)中的社區(qū)個數(shù)，一個標(biāo)簽代表一個社區(qū)。如果一個節(jié)點擁有至少兩個標(biāo)簽（即標(biāo)簽集長度|Ci|＞1），表明該節(jié)點同時屬于至少兩個社區(qū)，則該節(jié)點為重疊節(jié)點，如定義3所示。按照此規(guī)則，圖2所示的迭代結(jié)果包含兩個社區(qū)：社區(qū)1{a,b,c,d}和社區(qū)2{a,e,f,g},則a為重疊節(jié)點。但是，按照這種方法形成的社區(qū)往往會存在一些子集社區(qū)。如在社區(qū)結(jié)果中有兩個不同的社區(qū)Ci和Cj，分別為Ci={v1,v2,v3,v4},Cj={v1,v2,v3,v4,v5}。不難看出社區(qū)Ci是社區(qū)Cj的子集。顯然,保留社區(qū)Cj更有意義。因此，ALPA-S算法按照定義4的規(guī)則處理社區(qū)檢測結(jié)果中的子集社區(qū)。

定義3（重疊節(jié)點）Ci和Cj是兩個不同的社區(qū)，若節(jié)點vi同時屬于社區(qū)Ci和Cj，則稱節(jié)點vi為重疊節(jié)點。即：overlap(vi)??vi(vi∈Ci∩Cj∧Ci≠Cj)。

定義4（社區(qū)處理）若存在社區(qū)Ci和并且Ci?Cj，則刪除社區(qū)Ci，保留社區(qū)Cj。

2.5 時間復(fù)雜度

假設(shè)復(fù)雜網(wǎng)絡(luò)中有n個節(jié)點且節(jié)點的平均度數(shù)為k,有H個極大團(tuán)且極大團(tuán)平均節(jié)點數(shù)為m。ALPAS算法的時間復(fù)雜度主要分為三部分：（1）初始化過程；（2）迭代過程；（3）后期處理。

ALPA-S算法在初始化階段設(shè)置網(wǎng)絡(luò)中節(jié)點vi的標(biāo)簽集Ci=Φ，時間復(fù)雜度為O(n)；之后按照定義1尋找網(wǎng)絡(luò)中的MC，尋找MC過程產(chǎn)生的時間復(fù)雜度為因此，ALPA-S算法整個初始化過程產(chǎn)生的時間復(fù)雜度為

假設(shè)ALPA-S算法收斂時需要的迭代次數(shù)為T,每個節(jié)點更新標(biāo)簽分為3個過程：

（1）按照式（1）更新當(dāng)前節(jié)點的標(biāo)簽及權(quán)重；

（2）對更新后的節(jié)點標(biāo)簽進(jìn)行處理；

（3）對節(jié)點保留標(biāo)簽的權(quán)重進(jìn)行歸一化處理。

因此，ALPA-S算法迭代過程的時間復(fù)雜度為O(Tkn)。

ALPA-S算法后期處理過程產(chǎn)生的時間復(fù)雜度為O(n)。

3 ALPA-A算法

考慮使用異步標(biāo)簽傳播方式會使算法更快收斂，提出異步自適應(yīng)標(biāo)簽傳播算法（asynchronous adaptive label propagation algorithm，ALPA-A）。ALPAA算法的初始化過程、后期處理過程與ALPA-S算法相同。不同之處在于ALPA-A算法采用異步更新方式，具體更新規(guī)則如式（2）所示。

其中，bt-1(c,vi)為節(jié)點vi在第t-1步被更新的結(jié)果。N(vi)為節(jié)點vi的鄰居節(jié)點集合，N(vi)=N1(vi)∪N2(vi)，且N1(vi)∩N2(vi)=?。N1(vi)中的節(jié)點在第t步已經(jīng)被更新，N2(vi)中節(jié)點的最新結(jié)果則是在第t-1步被更新。如果節(jié)點vi的鄰接節(jié)點vj在第t步被更新，則更新節(jié)點vi的標(biāo)簽及權(quán)重時使用節(jié)點vj最近被更新的結(jié)果。否則使用其在第t-1步的更新結(jié)果。ALPAA與ALPA-S只是算法迭代過程采用的更新規(guī)則不同。盡管兩種算法收斂時的迭代次數(shù)可能不同，但它們的時間復(fù)雜度是一致的。

4 實驗

4.1 實驗數(shù)據(jù)和評價方法

通過兩種方式評估算法的性能：一種是使用仿真網(wǎng)絡(luò)生成程序LFR[39]生成帶有重疊社區(qū)和非重疊社區(qū)的仿真網(wǎng)絡(luò)數(shù)據(jù)集；另一種是使用現(xiàn)實生活中真實的社會網(wǎng)絡(luò)數(shù)據(jù)集。實驗環(huán)境為Win 7 OS、Intel?Core? i5 3.20 GHz處理器，算法實現(xiàn)為Python2.7程序設(shè)計語言，算法評價環(huán)境為Eclipse平臺下的Java語言，數(shù)據(jù)集格式均為文本文檔。

4.1.1 仿真網(wǎng)絡(luò)數(shù)據(jù)和評價方法

LFR仿真網(wǎng)絡(luò)生成程序在產(chǎn)生仿真網(wǎng)絡(luò)數(shù)據(jù)的同時也產(chǎn)生了社區(qū)劃分的結(jié)果，方便算法使用其生成的仿真網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行社區(qū)劃分的結(jié)果與已知社區(qū)進(jìn)行對比。利用LFR產(chǎn)生的仿真網(wǎng)絡(luò)數(shù)據(jù)集如表1所示。其中，n表示仿真網(wǎng)絡(luò)中的節(jié)點數(shù)，k是仿真網(wǎng)絡(luò)節(jié)點的平均度數(shù)。kmax表示仿真網(wǎng)絡(luò)中節(jié)點度數(shù)的最大值。Cmin表示仿真網(wǎng)絡(luò)社區(qū)長度的最小值。Cmax表示仿真網(wǎng)絡(luò)社區(qū)長度的最大值。On表示仿真網(wǎng)絡(luò)中重疊節(jié)點的個數(shù)。Om表示仿真網(wǎng)絡(luò)中重疊節(jié)點所屬的社區(qū)個數(shù)。t1為仿真網(wǎng)絡(luò)節(jié)點度數(shù)的密率分布指數(shù)。t2為仿真網(wǎng)絡(luò)社區(qū)大小的密率分布指數(shù)?；旌蠀?shù)μ取值范圍是[0，1]。取值越大，生成的仿真網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)越不明顯，當(dāng)取值為0時，整個網(wǎng)絡(luò)是一個社區(qū)；當(dāng)取值為1時，則生成的是一個隨機網(wǎng)絡(luò)。實際上，真實社會網(wǎng)絡(luò)大多具有一定的社區(qū)結(jié)構(gòu)性，因此本實驗使用的仿真網(wǎng)絡(luò)數(shù)據(jù)集μ取值范圍是[0，0.8]，每次增加0.1。

Table 1 LFR benchmark network dataset表1 LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集

本文使用Lancichinetti等人在文獻(xiàn)[40]中提出的標(biāo)準(zhǔn)互信息（normalized mutual information，NMI）評估算法在仿真網(wǎng)絡(luò)數(shù)據(jù)集上的社區(qū)檢測質(zhì)量。NMI可以測量兩個社區(qū)間的相似程度，NMI∈[0,1]，其值越大表明兩個社區(qū)越相似。NMI具體信息詳見式（3）。

其中，A和B表示網(wǎng)絡(luò)的兩種劃分結(jié)果，C表示混合矩陣，其元素Cij表示劃分A中的社團(tuán)i里面的節(jié)點在劃分B中的社團(tuán)j里面出現(xiàn)的個數(shù)。CA和CB表示劃分A和劃分B中的社團(tuán)的個數(shù)，Ci,表示矩陣C中第i行的元素之和，C,j表示矩陣C中第j列的元素之和，n表示網(wǎng)絡(luò)的節(jié)點個數(shù)。

4.1.2 真實網(wǎng)絡(luò)數(shù)據(jù)和評價方法

考慮到真實社會網(wǎng)絡(luò)和仿真網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)等信息存在一定的差異性，使用5種不同規(guī)模的真實社會網(wǎng)絡(luò)（Karate[41]、Dolphins[42]、Football[43]、Power[44]和 CA-hepPH[45]）對社區(qū)檢測算法進(jìn)行性能評價。Karate[41]是圣所迦利的空手道俱樂部的人際關(guān)系社會網(wǎng)絡(luò)，該網(wǎng)絡(luò)具有34個節(jié)點和78條邊，是一個小規(guī)模的真實社會網(wǎng)絡(luò)。Dolphins[42]是Lusseau等[46]在新西蘭對62只寬吻海豚的生活習(xí)性進(jìn)行了長時間的觀察，發(fā)現(xiàn)海豚的交往呈現(xiàn)出特定的模式，并構(gòu)造了包含62個節(jié)點的海豚社會網(wǎng)絡(luò)。Football[43]是美國大學(xué)秋季比賽中各足球俱樂部通過比賽關(guān)系產(chǎn)生的社會網(wǎng)絡(luò)。Power[44]是美國西部電網(wǎng)構(gòu)成的復(fù)雜網(wǎng)絡(luò)。CA-hepPH[45]是一個科學(xué)家合作的較大規(guī)模的真實社會網(wǎng)絡(luò)，具有11 204個節(jié)點和117 649條單向邊。這些社會網(wǎng)絡(luò)（如表2所示）中的節(jié)點代表的是真實個體，而邊代表了個體之間的關(guān)系。它們的規(guī)模、拓?fù)浣Y(jié)構(gòu)等特性不同，應(yīng)該能夠更好地評價社區(qū)檢測算法的性能。

Table 2 Real social network dataset表2 真實社會網(wǎng)絡(luò)數(shù)據(jù)集

人們通常不了解真實社會網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)情況，也很難有事實上的評價標(biāo)準(zhǔn)。Newman等提出的模塊度[47-49]方法得到廣泛認(rèn)可并被用于評價社區(qū)檢測算法在真實社會網(wǎng)絡(luò)數(shù)據(jù)集上的社區(qū)檢測質(zhì)量。其中，文獻(xiàn)[49]將問題擴展到無向無權(quán)重復(fù)雜網(wǎng)絡(luò)，提出一個用于檢測重疊社區(qū)的模塊度函數(shù)Qov，詳見式（4）所示。

在式（4）中，m表示復(fù)雜網(wǎng)絡(luò)的邊數(shù)。ki、kj是節(jié)點i、j的度數(shù)。A是網(wǎng)絡(luò)的鄰接矩陣，如果節(jié)點i和j相鄰，則Aij=1，否則Aij=0。如果節(jié)點i和j在同一個社區(qū)，δ(Ci,Cj)=1，否則δ(Ci,Cj)=0。

4.2 算法性能

GCE算法[50]提出k-clique中的參數(shù)k為3或4時，clique的大小是比較恰當(dāng)?shù)?。因此，本?jié)對MC的長度進(jìn)行了限定，分別為|MC|≥3和|MC|≥4兩種情況，并使用ALPA-S算法驗證兩種情況下的社區(qū)檢測質(zhì)量。ALPA-S算法分別在S1、S2、S3和S4仿真網(wǎng)絡(luò)數(shù)據(jù)集對應(yīng)的32個仿真網(wǎng)絡(luò)上運行10次，并對社區(qū)檢測結(jié)果的NMI值進(jìn)行了平均計算，結(jié)果如圖3（a）～圖3（d）所示，其中圖3（a）為仿真網(wǎng)絡(luò)數(shù)據(jù)集S1上的結(jié)果，圖3（b）為仿真網(wǎng)絡(luò)數(shù)據(jù)集S2上的結(jié)果，圖3（c）為仿真網(wǎng)絡(luò)數(shù)據(jù)集S3上的結(jié)果，圖3（d）為仿真網(wǎng)絡(luò)數(shù)據(jù)集S4上的結(jié)果。

圖3表示ALPA-S算法在兩種MC長度下在仿真網(wǎng)絡(luò)S1(a)、S2(b)、S3(c)和S4(d)上的社區(qū)檢測質(zhì)量。實驗結(jié)果表明，當(dāng)μ＞0.5且|MC|≥4時，在小型仿真網(wǎng)絡(luò)數(shù)據(jù)集S1和S2上，ALPA-S算法沒有取得較好的社區(qū)檢測質(zhì)量。而在較大的仿真網(wǎng)絡(luò)數(shù)據(jù)集S3上，ALPA-S算法在兩種長度的MC上均取得了較好的社區(qū)檢測質(zhì)量。但在S4數(shù)據(jù)集上，當(dāng)|MC|≥4時，ALPA-S算法的社區(qū)檢測質(zhì)量明顯劣于|MC|≥3時。實際上，當(dāng)|MC|≥4時，僅僅包含3個節(jié)點的小型社區(qū)無法被正確檢測，而文獻(xiàn)[25]證實過一個真實社會網(wǎng)絡(luò)的社區(qū)可能只包含3個節(jié)點。綜合考慮，選擇|MC|≥3作為ALPA-S算法和ALPA-A算法初始化時極大團(tuán)長度的限定條件。

另外，ALPA-S和ALPA-A在仿真網(wǎng)絡(luò)中檢測的極大團(tuán)個數(shù)即是兩種算法初始化時產(chǎn)生的標(biāo)簽數(shù)，為了證明這種方法極大地降低了算法中的冗余標(biāo)簽數(shù)以及減少了算法更新時標(biāo)簽選擇的代價，現(xiàn)以ALPA-S算法為例，使用表1中較大的仿真網(wǎng)絡(luò)數(shù)據(jù)集S3和S4對應(yīng)的16個仿真網(wǎng)絡(luò)作為實驗數(shù)據(jù)集驗證ALPA-S算法中產(chǎn)生的標(biāo)簽數(shù)以及標(biāo)簽節(jié)點比，實驗結(jié)果如圖4中的（a）和（b）所示。其中，標(biāo)簽節(jié)點比如式（5）所示。在式（5）中，Cn表示仿真網(wǎng)絡(luò)在ALPAS算法初始化時產(chǎn)生的標(biāo)簽數(shù)c與該仿真網(wǎng)絡(luò)節(jié)點數(shù)n的比值，即標(biāo)簽節(jié)點比。

Fig.3 Community detection result ofALPA-S algorithm in both MC lengths圖3 ALPA-S算法在兩種MC長度下的社區(qū)檢測質(zhì)量

在圖4的（a）和（b）中，ALPA-S算法在每個仿真網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了10次實驗，產(chǎn)生的標(biāo)簽數(shù)量略有差異。對10次實驗產(chǎn)生的極大團(tuán)數(shù)求平均值。從圖4（a）、（b）中可以看出，ALPA-S算法在16個仿真網(wǎng)絡(luò)上產(chǎn)生的標(biāo)簽節(jié)點比（label-node ratio）均小于10%，這極大降低了ALPA-S算法迭代時標(biāo)簽選擇的風(fēng)險，算法結(jié)果相對更穩(wěn)定。另外，這里應(yīng)該被提及的是ALPA-S算法和ALPA-A算法在尋找極大團(tuán)時，當(dāng)有兩個或更多個影響力相同的鄰接節(jié)點同時符合條件加入一個極大團(tuán)時，算法隨機選擇其中一個節(jié)點。這種隨機選擇可能導(dǎo)致社區(qū)劃分質(zhì)量的差異。但是，通過實驗結(jié)果分析得知，這種隨機選擇引起的社區(qū)劃分質(zhì)量不穩(wěn)定性誤差范圍在0.1%左右。可見，這種隨機選擇并未引起兩種算法社區(qū)檢測質(zhì)量的較大不穩(wěn)定性。被隨機選擇加入極大團(tuán)忽略的節(jié)點可能最終都沒有被加入到任何一個極大團(tuán)中，但在后續(xù)的標(biāo)簽更新過程中，其仍然會和與它有最多關(guān)聯(lián)關(guān)系的極大團(tuán)中的節(jié)點擁有同一個標(biāo)簽，并進(jìn)而屬于同一個社區(qū)。因此，構(gòu)建極大團(tuán)時的節(jié)點隨機性選擇問題對兩種算法社區(qū)檢測質(zhì)量的影響較小。

使用表1的S5數(shù)據(jù)集驗證ALPA-S和ALPA-A兩種算法在具有不同重疊社區(qū)數(shù)的仿真網(wǎng)絡(luò)中的社區(qū)檢測質(zhì)量，結(jié)果如圖5所示。從圖5可知，當(dāng)Om=0時，即仿真網(wǎng)絡(luò)中沒有重疊社區(qū)時，兩種算法均取得了較好的社區(qū)檢測質(zhì)量。說明兩種算法均適合于具有非重疊社區(qū)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)。隨著網(wǎng)絡(luò)中節(jié)點所屬的重疊社區(qū)數(shù)目的增加，兩種算法均保持著良好的社區(qū)檢測質(zhì)量，說明兩種算法亦均適合于節(jié)點屬于多個重疊社區(qū)的復(fù)雜網(wǎng)絡(luò)上的社區(qū)檢測。但是從圖5顯示的結(jié)果可以看出，在5種仿真網(wǎng)絡(luò)數(shù)據(jù)集上，同步算法ALPA-S的社區(qū)檢測質(zhì)量略優(yōu)于異步算法ALPA-A。

Fig.4 Number of labels and label-node ratio ofALPA-S algorithm on artificial networks圖4 ALPA-S算法在仿真網(wǎng)絡(luò)上產(chǎn)生的標(biāo)簽數(shù)及標(biāo)簽節(jié)點比

Fig.5 Result of community detection of two kinds of algorithms on artificial networks containing different number of overlapping community圖5 兩種算法在具有不同重疊社區(qū)數(shù)的仿真網(wǎng)絡(luò)上的社區(qū)檢測質(zhì)量

Fig.6 Iteration number of two kinds of algorithms on 32 artificial networks圖6 兩種算法在32個仿真網(wǎng)絡(luò)上的迭代次數(shù)

ALPA-S和ALPA-A兩種算法均提出極大團(tuán)MC是社區(qū)的核心結(jié)構(gòu)，社區(qū)內(nèi)的其他節(jié)點應(yīng)該圍繞在極大團(tuán)的周圍。使用實驗中的迭代次數(shù)來進(jìn)行驗證，結(jié)果如圖6所示。圖6顯示了同步算法ALPA-S和異步算法ALPA-A分別在32個仿真網(wǎng)絡(luò)上進(jìn)行實驗算法收斂時需要的迭代次數(shù)。結(jié)果表明兩種算法在32個仿真網(wǎng)絡(luò)上收斂時所需要的迭代次數(shù)均為1～2次，說明極大團(tuán)MC是社區(qū)的核心結(jié)構(gòu)，其余節(jié)點在MC的周圍且通過1～2步即可到達(dá)MC中的節(jié)點。也進(jìn)一步說明了兩種算法的迭代計算代價是比較小的。另外，通過在32個仿真網(wǎng)絡(luò)上的迭代次數(shù)計算可知，這兩種算法都極容易收斂。其中，ALPA-S在32個仿真網(wǎng)絡(luò)上的平均迭代次數(shù)是1.438，而ALPAA則是1.375。這也進(jìn)一步說明同步算法需要更多的迭代次數(shù)才能夠使算法收斂，而異步算法的收斂速度較快。

4.3 和其他算法的對比

（1）仿真網(wǎng)絡(luò)上的實驗

使用32個仿真網(wǎng)絡(luò)數(shù)據(jù)集（如表1的S1、S2、S3和S4所示）對比ALPA-S算法、ALPA-A算法和其他幾個經(jīng)典算法如LPA算法、COPRA算法、DEMON（democratic estimate of the modular organization of a network）算法[27]和GCE（greedy clique expansion）算法在稀疏和稠密復(fù)雜網(wǎng)絡(luò)上的社區(qū)檢測性能。結(jié)果分別如圖7中的（a）～（d）所示。

圖7展示了相關(guān)算法在4種類型32個仿真網(wǎng)絡(luò)S1、S2、S3和S4上的社區(qū)檢測質(zhì)量，分別如圖7中的（a）～（d）所示。從圖7可以得出如下結(jié)論：

①LPA算法、COPRA算法、GCE算法和ALPA-A算法在不同類型的復(fù)雜網(wǎng)絡(luò)上的社區(qū)檢測質(zhì)量不穩(wěn)定；

②ALPA-S算法和DEMON算法在混合參數(shù)μ值逐漸增加，社區(qū)結(jié)構(gòu)逐漸不清晰的情況下，無論在稀疏還是稠密復(fù)雜網(wǎng)絡(luò)中均呈現(xiàn)了較好的社區(qū)檢測質(zhì)量。

（2）真實網(wǎng)絡(luò)上的實驗

在5種真實社會網(wǎng)絡(luò)數(shù)據(jù)集上繼續(xù)驗證所提算法的社區(qū)檢測質(zhì)量，并使用模塊度函數(shù)Qov作為評價標(biāo)準(zhǔn)，結(jié)果如圖8所示。從圖8可以得出如下一些結(jié)論：

①ALPA-S算法在5種真實社會網(wǎng)絡(luò)上的社區(qū)檢測質(zhì)量總體好于其他5種算法;

②ALPA-A算法在不同社會網(wǎng)絡(luò)上的社區(qū)檢測質(zhì)量仍然表現(xiàn)出了一定的不穩(wěn)定性;

③在仿真網(wǎng)絡(luò)實驗中一直表現(xiàn)較好的DEMON算法，在真實社會網(wǎng)絡(luò)中的社區(qū)檢測質(zhì)量卻明顯表現(xiàn)不佳。

Fig.7 Result of community detection of related algorithms on 4 kinds of benchmark networks圖7 相關(guān)算法在4種類型仿真網(wǎng)絡(luò)上的社區(qū)檢測質(zhì)量

同時，在5種真實社會網(wǎng)絡(luò)上檢驗算法在初始化時產(chǎn)生的標(biāo)簽節(jié)點比及算法的迭代次數(shù)，以便進(jìn)一步驗證本文提出算法的性能，結(jié)果分別如圖9和圖10所示。從圖9和圖10中可以看出，不同真實復(fù)雜網(wǎng)絡(luò)被ALPA-S算法初始化后產(chǎn)生的標(biāo)簽節(jié)點比差異較大。其中，電力網(wǎng)絡(luò)Power初始化后的標(biāo)簽節(jié)點比僅為4.37%，而迭代次數(shù)卻多達(dá)10次和7次，這和仿真網(wǎng)絡(luò)上的實驗結(jié)果有較大的不同。因此，對使用ALPA-S算法通過最后一次迭代才能擁有標(biāo)簽的節(jié)點所在的社區(qū)之一進(jìn)行了可視化分析。選中的社區(qū)包含100個節(jié)點，為了繪圖方便，對該社區(qū)中的100個節(jié)點重新映射編號，可視化結(jié)果如圖11所示。從圖11可以看出該社區(qū)呈現(xiàn)近似樹狀的拓?fù)浣Y(jié)構(gòu)特征，并且其僅包含1個極大團(tuán){26，67，71}，如圖11紅色部分所示，其余節(jié)點均圍繞在該極大團(tuán)的周圍。從這些結(jié)果可知，Power中極大團(tuán)數(shù)量較少，因此初始化時其獲得的標(biāo)簽數(shù)量亦較少，這解釋了圖9中Power網(wǎng)絡(luò)具有較小的標(biāo)簽節(jié)點比以及需要較多迭代次數(shù)的根源。另外，從圖8可知，ALPA-A算法在Power上的表現(xiàn)好于其他5種算法，這也許可以說明當(dāng)社區(qū)中的核心結(jié)構(gòu)較少時，異步算法能夠更快收斂的同時，亦能取得更好的社區(qū)檢測質(zhì)量。

綜上所述，通過仿真網(wǎng)絡(luò)和真實網(wǎng)絡(luò)上的實驗表明，異步算法ALPA-A能夠更快地使算法收斂，其在社區(qū)核心結(jié)構(gòu)較少的社會網(wǎng)絡(luò)中能夠取得較好的社區(qū)檢測質(zhì)量，但是在不同類型復(fù)雜網(wǎng)絡(luò)中的社區(qū)檢測質(zhì)量仍然不夠穩(wěn)定。而同步算法ALPA-S無論在稀疏或稠密、社區(qū)結(jié)構(gòu)明顯與否以及在各種不同類型的真實社會網(wǎng)絡(luò)中的社區(qū)檢測質(zhì)量均優(yōu)于其他社區(qū)檢測算法，體現(xiàn)了其具有較好的自適應(yīng)性、穩(wěn)定性和健壯性。

Fig.8 Modularity of community detection of related algorithms on 5 real social networks圖8 相關(guān)算法在5種真實社會網(wǎng)絡(luò)上的社區(qū)檢測模塊度

Fig.9 Number of labels and label-node ratio of ALPA-S algorithm on real social networks圖9 ALPA-S算法在真實網(wǎng)絡(luò)上的標(biāo)簽數(shù)及標(biāo)簽節(jié)點比

Fig.10 Iteration number ofALPA-S algorithm on real social networks圖10 ALPA-S算法在真實社會網(wǎng)絡(luò)上的迭代次數(shù)

5 結(jié)束語

由于依靠網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息對社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)進(jìn)行挖掘具有模型簡單、計算效率高和易于應(yīng)用等特點，本文提出了單純依靠社會網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的同步自適應(yīng)標(biāo)簽傳播算法ALPA-S和異步自適應(yīng)標(biāo)簽傳播算法ALPA-A檢測復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。通過對兩種算法的性能分析以及和其他經(jīng)典算法的對比，表明同步算法ALPA-S更適合于檢測不同類型社會網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)和非重疊社區(qū)結(jié)構(gòu)。另外，不需要參數(shù)控制的ALPA-S算法能夠根據(jù)復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息自動調(diào)整初始化時極大團(tuán)中節(jié)點的個數(shù)以及根據(jù)節(jié)點標(biāo)簽個數(shù)自動調(diào)整閾值并剔除無意義的標(biāo)簽，具有良好的自適應(yīng)性。因此其能更好地適應(yīng)沒有先驗知識的真實社會網(wǎng)絡(luò)。另外，本文提出的算法證實了一個社會現(xiàn)象：一個社區(qū)結(jié)構(gòu)（群體）至少包含一個影響力較大的核心群體（極大團(tuán)MC），社區(qū)影響力較弱的群體則圍繞在影響力較大的核心群體的周圍。下一步，考慮將ALPA-S算法進(jìn)行并行實現(xiàn)，從而可以更好地解決大規(guī)模以及超大規(guī)模社會網(wǎng)絡(luò)中的社區(qū)檢測問題。

Fig.11 Graph of visualization result of a community in Power social network圖11 Power中一個社區(qū)的可視化結(jié)果圖