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

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

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

1 引言

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

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

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

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

2 ALPA-S算法

2.1 初始化

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

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

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

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

（2）c←1；

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

（4）c←c+1；

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

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

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

2.2 迭代過程

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

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

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

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

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

（1）t←1。

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

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

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

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

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

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

2.3 終止條件

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

2.4 后期處理

在ALPA-S算法中，標簽的數(shù)量是復雜網(wǎng)絡中不相交極大團的數(shù)量。隨著迭代過程的推進，標簽數(shù)量逐漸減少。當算法終止時，剩余標簽的數(shù)量代表復雜網(wǎng)絡中的社區(qū)個數(shù)，一個標簽代表一個社區(qū)。如果一個節(jié)點擁有至少兩個標簽（即標簽集長度|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 時間復雜度

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

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

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

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

（2）對更新后的節(jié)點標簽進行處理；

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

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

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

3 ALPA-A算法

考慮使用異步標簽傳播方式會使算法更快收斂，提出異步自適應標簽傳播算法（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的標簽及權(quán)重時使用節(jié)點vj最近被更新的結(jié)果。否則使用其在第t-1步的更新結(jié)果。ALPAA與ALPA-S只是算法迭代過程采用的更新規(guī)則不同。盡管兩種算法收斂時的迭代次數(shù)可能不同，但它們的時間復雜度是一致的。

4 實驗

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

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

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

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

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

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

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

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

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

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

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

在式（4）中，m表示復雜網(wǎng)絡的邊數(shù)。ki、kj是節(jié)點i、j的度數(shù)。A是網(wǎng)絡的鄰接矩陣，如果節(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的大小是比較恰當?shù)?。因此，本?jié)對MC的長度進行了限定，分別為|MC|≥3和|MC|≥4兩種情況，并使用ALPA-S算法驗證兩種情況下的社區(qū)檢測質(zhì)量。ALPA-S算法分別在S1、S2、S3和S4仿真網(wǎng)絡數(shù)據(jù)集對應的32個仿真網(wǎng)絡上運行10次，并對社區(qū)檢測結(jié)果的NMI值進行了平均計算，結(jié)果如圖3（a）～圖3（d）所示，其中圖3（a）為仿真網(wǎng)絡數(shù)據(jù)集S1上的結(jié)果，圖3（b）為仿真網(wǎng)絡數(shù)據(jù)集S2上的結(jié)果，圖3（c）為仿真網(wǎng)絡數(shù)據(jù)集S3上的結(jié)果，圖3（d）為仿真網(wǎng)絡數(shù)據(jù)集S4上的結(jié)果。

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

另外，ALPA-S和ALPA-A在仿真網(wǎng)絡中檢測的極大團個數(shù)即是兩種算法初始化時產(chǎn)生的標簽數(shù)，為了證明這種方法極大地降低了算法中的冗余標簽數(shù)以及減少了算法更新時標簽選擇的代價，現(xiàn)以ALPA-S算法為例，使用表1中較大的仿真網(wǎng)絡數(shù)據(jù)集S3和S4對應的16個仿真網(wǎng)絡作為實驗數(shù)據(jù)集驗證ALPA-S算法中產(chǎn)生的標簽數(shù)以及標簽節(jié)點比，實驗結(jié)果如圖4中的（a）和（b）所示。其中，標簽節(jié)點比如式（5）所示。在式（5）中，Cn表示仿真網(wǎng)絡在ALPAS算法初始化時產(chǎn)生的標簽數(shù)c與該仿真網(wǎng)絡節(jié)點數(shù)n的比值，即標簽節(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)絡數(shù)據(jù)集上進行了10次實驗，產(chǎn)生的標簽數(shù)量略有差異。對10次實驗產(chǎn)生的極大團數(shù)求平均值。從圖4（a）、（b）中可以看出，ALPA-S算法在16個仿真網(wǎng)絡上產(chǎn)生的標簽節(jié)點比（label-node ratio）均小于10%，這極大降低了ALPA-S算法迭代時標簽選擇的風險，算法結(jié)果相對更穩(wěn)定。另外，這里應該被提及的是ALPA-S算法和ALPA-A算法在尋找極大團時，當有兩個或更多個影響力相同的鄰接節(jié)點同時符合條件加入一個極大團時，算法隨機選擇其中一個節(jié)點。這種隨機選擇可能導致社區(qū)劃分質(zhì)量的差異。但是，通過實驗結(jié)果分析得知，這種隨機選擇引起的社區(qū)劃分質(zhì)量不穩(wěn)定性誤差范圍在0.1%左右?？梢?，這種隨機選擇并未引起兩種算法社區(qū)檢測質(zhì)量的較大不穩(wěn)定性。被隨機選擇加入極大團忽略的節(jié)點可能最終都沒有被加入到任何一個極大團中，但在后續(xù)的標簽更新過程中，其仍然會和與它有最多關聯(lián)關系的極大團中的節(jié)點擁有同一個標簽，并進而屬于同一個社區(qū)。因此，構(gòu)建極大團時的節(jié)點隨機性選擇問題對兩種算法社區(qū)檢測質(zhì)量的影響較小。

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

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

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

4.3 和其他算法的對比

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

使用32個仿真網(wǎng)絡數(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）算法在稀疏和稠密復雜網(wǎng)絡上的社區(qū)檢測性能。結(jié)果分別如圖7中的（a）～（d）所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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