鄭文萍 車晨浩 錢宇華 王 杰

1(山西大學(xué)大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院 太原 030006) 2(山西大學(xué)計算機與信息技術(shù)學(xué)院 太原 030006) 3(計算智能與中文信息處理教育部重點實驗室(山西大學(xué)) 太原 030006) (wpzheng@sxu.edu.cn)

復(fù)雜網(wǎng)絡(luò)分析在社會學(xué)、傳染病學(xué)和生物學(xué)等領(lǐng)域有著廣泛的應(yīng)用[1-3].通?？梢杂脠DG=(V,E)表示一個復(fù)雜網(wǎng)絡(luò),其中V表示網(wǎng)絡(luò)中個體的集合,E表示個體間聯(lián)系的集合.社區(qū)結(jié)構(gòu)(community structure)是復(fù)雜網(wǎng)絡(luò)的重要特征之一,即一個網(wǎng)絡(luò)可以分成若干社區(qū),社區(qū)內(nèi)節(jié)點之間連接相對緊密,社區(qū)間節(jié)點連接相對稀疏.有效的社區(qū)發(fā)現(xiàn)算法可以發(fā)現(xiàn)社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)、生物網(wǎng)絡(luò)中的蛋白質(zhì)功能模塊等,有助于深入研究各種類型復(fù)雜網(wǎng)絡(luò)的功能模塊及其演化特征,對準(zhǔn)確地理解并分析復(fù)雜系統(tǒng)的拓撲結(jié)構(gòu)及動力學(xué)特性具有十分重要的理論意義和應(yīng)用價值[4-5].

目前復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)方法主要有基于圖劃分的聚類算法[6]、基于譜分析的聚類算法[7]、基于層次的聚類算法[8]和基于密度的聚類算法[9-10]等.Newman提出了一種基于貪心策略的快速社區(qū)發(fā)現(xiàn)算法(fast modularity maximization, FMM)[11],以最優(yōu)化模塊性為目標(biāo)函數(shù)進行社區(qū)合并和更新.Blondel等人提出了BGLL算法[12],隨機選擇一個節(jié)點作為初始社區(qū),迭代選擇使當(dāng)前社區(qū)模塊性增長最大節(jié)點加入當(dāng)前社區(qū)完成社區(qū)擴展過程.由于現(xiàn)實網(wǎng)絡(luò)包含大量的小規(guī)模社區(qū),網(wǎng)絡(luò)社區(qū)內(nèi)部連接數(shù)不一定比社區(qū)之間的連接數(shù)多,導(dǎo)致模塊性不能較好地度量社區(qū)劃分質(zhì)量.Bai等人[13]基于互補熵理論提出了一種度量網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)質(zhì)量的目標(biāo)函數(shù),該函數(shù)綜合考慮社區(qū)內(nèi)緊密程度和社區(qū)間稀疏程度對社區(qū)發(fā)現(xiàn)結(jié)果進行評價,并以公共鄰居數(shù)度量節(jié)點相似性給出了一種圖聚類算法ISCD+.

Raghavan等人提出了標(biāo)簽傳播算法(label pro-pagation algorithm, LPA)[14],該算法中起初每個節(jié)點擁有獨立的類標(biāo)簽,每次迭代中對于每個節(jié)點將其標(biāo)簽更改為其鄰居節(jié)點中出現(xiàn)次數(shù)最多的標(biāo)簽,通過迭代,直到每個節(jié)點的標(biāo)簽與其鄰居節(jié)點中出現(xiàn)次數(shù)最多的標(biāo)簽相同,則達到穩(wěn)定狀態(tài),算法結(jié)束.此時具有相同標(biāo)簽的節(jié)點屬于同一個社區(qū).LPA算法有接近線性時間的復(fù)雜度,但劃分過程中,節(jié)點更新順序與標(biāo)簽傳播過程存在很大的隨機性，使劃分結(jié)果表現(xiàn)了較強的不穩(wěn)定性.Barber等人對LPA算法進行改進提出算法LPAm[15],參照隨機連接定義節(jié)點標(biāo)簽更新方式,使得算法結(jié)果具有較高的模塊性.然而,LPAm算法可能陷入局部最優(yōu)解且結(jié)果存在不穩(wěn)定性.Liu等人提出LPAm+算法[16],在LPAm算法之后引入后處理步驟，合并一些小社區(qū)進一步提高劃分結(jié)果的模塊性.Li等人基于LPA算法提出一種分階段的社區(qū)發(fā)現(xiàn)算法LPA-S[17],依據(jù)節(jié)點間的相似性更新節(jié)點標(biāo)簽,得到初始社區(qū)劃分；再根據(jù)社區(qū)相似性進行社區(qū)合并,使得最終劃分結(jié)果中社區(qū)內(nèi)部連邊具有較高的密度.

以上算法主要針對LPA節(jié)點標(biāo)簽更新過程的不確定性進行了改進，并對劃分結(jié)果進行適當(dāng)處理以緩解過早陷入局部極值的問題.盡管如此，這些算法沒有處理節(jié)點標(biāo)簽更新順序的隨機性，使得劃分結(jié)果仍然存在較大的不穩(wěn)定性.按合理的順序選擇待更新節(jié)點可以提高算法性能并得到穩(wěn)定的社區(qū)劃分結(jié)果.針對此問題，本文提出了一種基于標(biāo)簽傳播的兩階段社區(qū)發(fā)現(xiàn)算法(a two-stage community detection algorithm based on label propagation, LPA-TS)，減少了傳統(tǒng)標(biāo)簽傳播方法在節(jié)點更新和標(biāo)簽傳播過程的隨機性,可以得到穩(wěn)定的計算結(jié)果；通過與一些經(jīng)典算法在8個真實網(wǎng)絡(luò)以及不同參數(shù)情況下LFR benchmark人工網(wǎng)絡(luò)數(shù)據(jù)集上的實驗比較分析，結(jié)果表明LPA-TS算法社區(qū)發(fā)現(xiàn)結(jié)果表現(xiàn)了良好的穩(wěn)定性,且在標(biāo)準(zhǔn)互信息、調(diào)整蘭德系數(shù)、模塊性等方面均表現(xiàn)出較好的性能.

1 背景知識

一個復(fù)雜網(wǎng)絡(luò)可以用圖G=(V,E)來表示,其中節(jié)點集V={v1,v2,…,vn}表示網(wǎng)絡(luò)個體的集合,邊集E代表網(wǎng)絡(luò)個體間聯(lián)系的集合,記作邊ei,j=(vi,vj).令n=|V|且m=|E|.除非特別聲明,本文僅對無向簡單圖進行討論.在圖G中,節(jié)點vi的鄰域NG(vi)定義為NG(vi)={vj|(vi,vj)∈E},其中vj∈NG(vi)稱為節(jié)點vi的鄰居節(jié)點.節(jié)點vi的度為d(vi)=|NG(vi)|,在不引起混淆的情況下,簡記為di.假設(shè)Ω={V1,V2,…,Vk}是V的一種劃分,Vr∈V且|Vr|=nr,稱k為該劃分中的社區(qū)個數(shù).令di(Vr)=|{vj|(vi,vj)∈E且vj∈Vr}|表示節(jié)點vi與社區(qū)Vr內(nèi)節(jié)點的連邊數(shù).

(1)

而弱社區(qū)是指社區(qū)中所有節(jié)點與社區(qū)內(nèi)部節(jié)點的度數(shù)之和大于社區(qū)中所有節(jié)點與社區(qū)外部節(jié)點連接的度數(shù)之和:

(2)

默認取α=2.通常一個社區(qū)應(yīng)該至少表現(xiàn)弱社區(qū)的性質(zhì).

2017年，Bertolero等人定義了節(jié)點的參與系數(shù)[19]，用來刻畫節(jié)點與網(wǎng)絡(luò)中不同社區(qū)連邊的分布情況:

(3)

參與系數(shù)的值越高則表示節(jié)點與較多社區(qū)存在連邊，該節(jié)點對某社區(qū)的歸屬度比較低；相反，值越低表示節(jié)點的連邊情況越集中于少數(shù)社區(qū)，則該節(jié)點對某社區(qū)的歸屬度較高.從具有明顯社區(qū)歸屬的節(jié)點開始進行社區(qū)發(fā)現(xiàn)，有助于提高社區(qū)發(fā)現(xiàn)質(zhì)量，并提高算法穩(wěn)定性.

為了對社區(qū)劃分結(jié)果進行度量，2004年Newman等提出了模塊性[20]的概念，它反映了網(wǎng)絡(luò)社區(qū)內(nèi)部連接的強弱，作為一種社區(qū)劃分的評價標(biāo)準(zhǔn)得到了廣泛使用.將網(wǎng)絡(luò)用鄰接矩陣A來表示，若節(jié)點x與y直接相連，則Ax y=1，否則Ax y=0.模塊性定義為

(4)

為了合理地對復(fù)雜網(wǎng)絡(luò)中的節(jié)點進行社區(qū)發(fā)現(xiàn)，將節(jié)點間相似性作為衡量節(jié)點連接緊密程度的重要標(biāo)準(zhǔn).目前已經(jīng)有一些基于網(wǎng)絡(luò)拓撲特征的相似性度量函數(shù)[21-22].公共鄰居數(shù)(common neighbors, CN)度量[21]認為2個節(jié)點間的公共鄰居節(jié)點越多，則它們在結(jié)構(gòu)上越相似，連接越緊密:

CN(x,y)=|NGx∩NGy|.

(5)

2 一種基于標(biāo)簽傳播的兩階段社區(qū)發(fā)現(xiàn)算法

基于節(jié)點參與系數(shù)與節(jié)點相似性，本文給出一種基于標(biāo)簽傳播的兩階段社區(qū)發(fā)現(xiàn)算法(LPA-TS).算法包括2個主要過程：1)根據(jù)節(jié)點參與系數(shù)定義節(jié)點的更新順序，并更新節(jié)點標(biāo)簽為與其具有最高相似性的鄰居節(jié)點標(biāo)簽，得到社區(qū)的初始劃分結(jié)果；2)將當(dāng)前社區(qū)進行合并，并在目標(biāo)函數(shù)的監(jiān)督下完成社區(qū)劃分的過程.第1階段中首先根據(jù)節(jié)點的參與系數(shù)高低，從低到高確定節(jié)點的更新順序；其次依據(jù)節(jié)點相似性，選擇與當(dāng)前遍歷節(jié)點最相似的鄰居節(jié)點的標(biāo)簽作為當(dāng)前遍歷節(jié)點的標(biāo)簽，得到第1階段的劃分結(jié)果.第2階段中，將社區(qū)作為節(jié)點計算其參與系數(shù)以確定社區(qū)合并順序，最后在目標(biāo)函數(shù)的監(jiān)督下將社區(qū)進行合并得到最終的劃分結(jié)果.

2.1 節(jié)點更新順序

在LPA算法中，不同的節(jié)點更新順序會使得最終的社區(qū)劃分結(jié)果有很大差異.如圖1所示，可以看出，圖1中7個節(jié)點應(yīng)該被分成2個社區(qū).算法初始將每個節(jié)點看作1個單獨社區(qū)，假設(shè)當(dāng)前虛線框住的節(jié)點已經(jīng)被賦予了相同的社區(qū)標(biāo)簽.隨后，若首先選擇節(jié)點v4進行標(biāo)簽更新，有很大可能將節(jié)點v4與節(jié)點{v1,v2,v3}劃分到同一社區(qū)，進而將所有節(jié)點劃分為1個社區(qū).而如果選擇節(jié)點v5進行更新則會有很大可能得到正確的社區(qū)劃分.這是由于節(jié)點v4位于2個社區(qū)的邊界處，對社區(qū)的歸屬度不強，對其首先更新容易將2個社區(qū)合并為1個大社區(qū).

Fig.1 An example network with two communities圖1 具有2個社區(qū)的網(wǎng)絡(luò)示例

可以看出，在節(jié)點標(biāo)簽更新的過程中，如果先更新歸屬度較強的社區(qū)內(nèi)部節(jié)點的標(biāo)簽，會獲得一個更符合實際社區(qū)結(jié)構(gòu)且更穩(wěn)定的劃分結(jié)果.

從參與系數(shù)的定義看，一個節(jié)點的度越低，其社區(qū)歸屬程度越高；而一個節(jié)點的鄰居節(jié)點社區(qū)歸屬越集中，其社區(qū)歸屬程度越高.優(yōu)先選擇參與系數(shù)低的節(jié)點進行更新，可以盡早得到更穩(wěn)定的社區(qū)結(jié)構(gòu)，進而得到更準(zhǔn)確的社區(qū)劃分結(jié)果.如圖1最終得到2個社區(qū)劃分{v1,v2,v3}和{v4,v5,v6,v7}.

2.2 標(biāo)簽傳播

LPA算法在對節(jié)點的標(biāo)簽進行更新時，選取鄰居節(jié)點的標(biāo)簽中出現(xiàn)次數(shù)最多的標(biāo)簽為自身標(biāo)簽，即認為其所有鄰居節(jié)點的重要性相同，并沒有考慮不同鄰居節(jié)點的不同相似性.然而，在同一個社區(qū)中的個體往往具有較高的相似性.如在圖1中，節(jié)點v4、節(jié)點v6和節(jié)點v7具有相同PC值，對于節(jié)點v4，其鄰居節(jié)點的標(biāo)簽出現(xiàn)次數(shù)均為1，則有較大可能將v4劃分入社區(qū){v1,v2,v3}，導(dǎo)致錯誤的劃分結(jié)果.

實際上,對節(jié)點v4而言,社區(qū){v1,v2,v3}，{v6}和{v7}中各有一個節(jié)點與其關(guān)聯(lián)，從圖1中可以看出，由于v4與v6(或v7)有一個公共鄰居節(jié)點，因此相較于節(jié)點v3，v4更有可能與v6(或v7)屬于同一社區(qū).

因此，用CN對節(jié)點間的相似性進行度量，2個節(jié)點間的公共鄰居節(jié)點越多，則它們在結(jié)構(gòu)上越相似，連接越緊密，在標(biāo)簽更新的過程中選擇與其相似性最高的鄰居節(jié)點的標(biāo)簽，可使最終劃分在同一個社區(qū)中的節(jié)點具有較高的相似性，也更符合實際的社區(qū)分布.如在圖1中，節(jié)點v4確定標(biāo)簽時，由于其與節(jié)點v6和節(jié)點v7的相似性高于其他節(jié)點，故標(biāo)簽會確定為節(jié)點v6或節(jié)點v7的標(biāo)簽，得到正確的劃分.但是公共鄰居數(shù)度量節(jié)點相似性在某些特殊情況下并不適用.例如若節(jié)點x和節(jié)點y之間存在連邊,但無公共鄰居節(jié)點，但它們之間的相似性應(yīng)該大于0；特別地，一個懸掛點與其相鄰點之間無公共鄰居節(jié)點，但通常與其相鄰點位于同一社區(qū).基于此，本文對節(jié)點相似性計算為

(6)

2.3 初始社區(qū)發(fā)現(xiàn)過程

根據(jù)節(jié)點更新順序和標(biāo)簽傳播過程，算法給出網(wǎng)絡(luò)初始劃分結(jié)果.首先將網(wǎng)絡(luò)中的每個節(jié)點看作一個獨立社區(qū)，賦予唯一社區(qū)標(biāo)簽；計算節(jié)點的參與系數(shù)PCi(1≤i≤n)，按從低到高的順序依次更新節(jié)點標(biāo)簽.節(jié)點標(biāo)簽更新過程中，考慮當(dāng)前節(jié)點與其鄰居節(jié)點的公共鄰居相似性，選擇相似性最高的鄰居節(jié)點標(biāo)簽作為當(dāng)前節(jié)點的新標(biāo)簽.以上過程迭代進行，直到劃分結(jié)果不再變化或者達到最大迭代次數(shù).算法1給出LPA-TS算法的第1階段即初始社區(qū)發(fā)現(xiàn)過程.

算法1.初始社區(qū)發(fā)現(xiàn)算法(LPA-TS第1階段).

輸入：網(wǎng)絡(luò)G=(V,E)、最大迭代次數(shù)tmax，其中V={v1,v2,…,vn}，A是圖G的鄰接矩陣；

輸出：網(wǎng)絡(luò)的初始劃分結(jié)果L(V)={l1,l2,…,ln}，其中，li表示節(jié)點vi的初始劃分社區(qū)標(biāo)簽.

步驟1.根據(jù)

計算網(wǎng)絡(luò)中節(jié)點vi和vj間的相似性.

步驟3.計算當(dāng)前節(jié)點標(biāo)簽集合中不同的標(biāo)簽數(shù)k=|L(V)|.

步驟4.根據(jù)

計算節(jié)點vi的參與系數(shù).

步驟7.t=t+1.

圖2給出了在Karate網(wǎng)絡(luò)上的初始社區(qū)發(fā)現(xiàn)結(jié)果.其中節(jié)點被初始劃分為4個社區(qū)(用不同形狀表示).可以看出，算法1的初始社區(qū)劃分結(jié)果中，度數(shù)較大節(jié)點由于與鄰居節(jié)點的相似性較高，容易將自身標(biāo)簽傳播給鄰居節(jié)點，從而形成以大度節(jié)點為中心的較大社區(qū).而位于社區(qū)邊緣的一些節(jié)點，由于度數(shù)偏低且與鄰居節(jié)點的相似性小，容易形成一些規(guī)模較小的社區(qū)，如圖2中菱形節(jié)點和三角形節(jié)點構(gòu)成的社區(qū).

Fig.2 Communities of the Karate network discoveredby Step 1 of LPA-TS圖2 LPA-TS第1階段在Karate網(wǎng)絡(luò)的初始社區(qū)發(fā)現(xiàn)結(jié)果

隨著網(wǎng)絡(luò)規(guī)模的增大，特別是網(wǎng)絡(luò)連接比較稀疏時，算法第1階段會得到大量的特別小規(guī)模的社區(qū)，造成對原始網(wǎng)絡(luò)的過劃分.為了得到更準(zhǔn)確的社區(qū)劃分結(jié)果，還需要對初始社區(qū)劃分結(jié)果進行社區(qū)合并.

2.4 社區(qū)合并過程

針對初始社區(qū)發(fā)現(xiàn)過程網(wǎng)絡(luò)過度劃分的問題，首先分析得到的初始社區(qū)劃分結(jié)果中，根據(jù)式(2)依次判斷各初始社區(qū)是否滿足弱社區(qū)的定義.通常情況下，式(2)中的內(nèi)部度系數(shù)α=2，表示一個社區(qū)的內(nèi)部度大于其外部連邊數(shù)則為弱社區(qū).當(dāng)所分析網(wǎng)絡(luò)中包含大量小規(guī)模社區(qū)時，特別是社區(qū)個數(shù)遠大于單個社區(qū)規(guī)模時，一個社區(qū)的內(nèi)部度可能會小于其外部連邊.為更好地反映網(wǎng)絡(luò)的社區(qū)組成，此時，需要根據(jù)網(wǎng)絡(luò)類型適當(dāng)提高式(2)中的內(nèi)部度系數(shù)α.

將不滿足弱社區(qū)定義的初始社區(qū)，與其相鄰的且具有最多關(guān)聯(lián)邊數(shù)的社區(qū)合并為一個社區(qū).在此為基礎(chǔ)上繼續(xù)進行LPA-TS算法第2階段的標(biāo)簽傳播過程.

將以上所得的每個社區(qū)看作一個節(jié)點，社區(qū)之間連邊數(shù)作為2個社區(qū)對應(yīng)節(jié)點連邊的權(quán)重，給出該帶權(quán)無向網(wǎng)絡(luò)中節(jié)點參與系數(shù)的定義方式：

(7)

因此，此處仍然按社區(qū)對應(yīng)節(jié)點的PC值從低到高的順序進行標(biāo)簽更新.在節(jié)點si的標(biāo)簽更新過程中，選擇與其具有最高連邊權(quán)重的鄰居節(jié)點標(biāo)簽作為si的新標(biāo)簽.每次節(jié)點標(biāo)簽的更新都意味著合并2個初始社區(qū).

為了對節(jié)點標(biāo)簽傳播過程進行有效控制，需要從社區(qū)內(nèi)部連接緊密程度以及社區(qū)間連接的稀疏程度同時考慮社區(qū)發(fā)現(xiàn)質(zhì)量，因此本文選擇文獻[13]提出的基于互補熵的評價函數(shù)，對當(dāng)前社區(qū)合并結(jié)果進行評價:

(8)

算法2給出了LPA-TS第2階段社區(qū)合并的具體過程.

算法2.社區(qū)合并過程(LPA-TS第2階段).

輸入：網(wǎng)絡(luò)G=(V,E)，其中V={v1,v2,…,vn}，網(wǎng)絡(luò)的初始劃分結(jié)果L(V)={l1,l2,…,ln}；

輸出：網(wǎng)絡(luò)的最終劃分結(jié)果Ω={V1,V2,…,Vk}.

步驟5.計算當(dāng)前網(wǎng)絡(luò)劃分的評價函數(shù)值F(Ωt+1).

步驟6.若F(Ωt+1)>F(Ωt)，令t=t+1，返回步驟2；否則，算法2結(jié)束，返回Ωt+1為最終結(jié)果.

2.5 時間復(fù)雜度分析

本文提出的基于標(biāo)簽傳播的兩階段社區(qū)發(fā)現(xiàn)算法LPA-TS包括2個主要過程：

1) 根據(jù)參與系數(shù)定義節(jié)點的更新順序，并將節(jié)點標(biāo)簽更新為與其具有最高相似性的鄰居節(jié)點標(biāo)簽，得到社區(qū)的初始劃分結(jié)果；

2) 將初始劃分結(jié)果中的小規(guī)模社區(qū)與其有最多連邊的相鄰社區(qū)進行合并；本文采用基于互補熵的評價函數(shù)F(Ω)作為目標(biāo)函數(shù)對社區(qū)發(fā)現(xiàn)結(jié)果進行判斷，得到F(Ω)值最大的社區(qū)發(fā)現(xiàn)結(jié)果作為算法最終輸出.

算法1中，計算節(jié)點相似性的代價為O(n2)，計算節(jié)點參與系數(shù)的代價為O(n2)；在算法2中，假設(shè)當(dāng)前網(wǎng)絡(luò)中的社區(qū)數(shù)為n′，計算各社區(qū)間的連邊數(shù)的代價為O(n′2)；2階段的標(biāo)簽更新的代價為O(t×(n+n′))，t為算法的迭代次數(shù)，因此算法LPA-TS的總時間復(fù)雜度為O(n2+n′2+t×(n+n′)).

3 實驗結(jié)果與分析

選擇不同參數(shù)情況下的LFR benchmark人工網(wǎng)絡(luò)[23]和8個經(jīng)典真實網(wǎng)絡(luò)用本文算法LPA-TS進行社區(qū)發(fā)現(xiàn)，并選擇LPA,LPAm,LPAm+,LPA-S,BGLL,ISCD+,FMM,Infomap[24]等包括經(jīng)典的標(biāo)簽傳播算法和以模塊性為優(yōu)化目標(biāo)的算法作對比進行性能比較.

3.1 評價指標(biāo)

(9)

(10)

劃分結(jié)果與原始劃分的吻合程度越高，NMI和ARI的值越高.如果劃分結(jié)果與網(wǎng)絡(luò)隨機劃分結(jié)果相差越大，ARI的值更高.

為了對算法劃分結(jié)果的穩(wěn)定性進行評價，本文定義算法的穩(wěn)定系數(shù)σ.對網(wǎng)絡(luò)G，若|V(G)|=n，對第t次計算結(jié)果Ωt構(gòu)造n×n階的矩陣，其元素定義為

(11)

若算法運行T次，可得到計算結(jié)果的方差矩陣S，其元素定義為

(12)

由此，將算法穩(wěn)定系數(shù)σ定義為

(13)

一個算法多次運行結(jié)果的算法穩(wěn)定系數(shù)越低，說明算法劃分結(jié)果越穩(wěn)定.

3.2 人工網(wǎng)絡(luò)實驗

人工網(wǎng)絡(luò)實驗采用在社區(qū)發(fā)現(xiàn)算法性能檢測中廣泛采用的LFR benchmark數(shù)據(jù)集上進行，分別考察網(wǎng)絡(luò)規(guī)模n為1 000或5 000，社區(qū)規(guī)模區(qū)間為10～50或20～100，混合參數(shù)μ為0.05～0.5的各種不同參數(shù)下LFR人工網(wǎng)絡(luò)上本文算法LPA-TS與對比算法的性能比較.所有實驗網(wǎng)絡(luò)節(jié)點平均度為20，最大度為50，節(jié)點度序列滿足指數(shù)為2的冪律分布，社區(qū)規(guī)模序列滿足指數(shù)為1的冪律分布.取各算法在每個網(wǎng)絡(luò)上執(zhí)行30次的結(jié)果取平均值進行比較，結(jié)果如圖3和圖4所示.可以看到，混合參數(shù)較低(μ為0.05～0.3)時，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)比較明顯，各算法都取得了與實際網(wǎng)絡(luò)中社區(qū)分布高度吻合的結(jié)果.隨著μ的增大，網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)明顯性降低，由于在本文LPA-TS算法中，選擇參與系數(shù)較低的節(jié)點進行標(biāo)簽傳播，確保算法在保持社區(qū)發(fā)現(xiàn)質(zhì)量的同時，減少了節(jié)點標(biāo)簽傳播過程中的隨機性，從而使得算法運行結(jié)果比較穩(wěn)定.

Fig.3 Comparison of NMI on LFR benchmark networks圖3 各算法在LFR benchmark網(wǎng)絡(luò)上的NMI比較結(jié)果

Fig.4 Comparison of ARI on LFR benchmark networks圖4 各算法在LFR benchmark網(wǎng)絡(luò)上的ARI比較結(jié)果

實際上，本文也與基于隨機游走的社區(qū)發(fā)現(xiàn)算法Infomap進行了對比實驗.Infomap算法在本文實驗的LFR benchmark網(wǎng)絡(luò)上社區(qū)發(fā)現(xiàn)結(jié)果與初始生成的社區(qū)劃分結(jié)果完全吻合.這是由于LFR benchmark網(wǎng)絡(luò)生成過程中，其社區(qū)內(nèi)部連邊和社區(qū)之間連邊分別采用隨機連接方式產(chǎn)生.這導(dǎo)致網(wǎng)絡(luò)中各社區(qū)內(nèi)部連邊分布比較均勻，2節(jié)點之間的連邊概率與其度數(shù)成正相關(guān)關(guān)系.所以LFR bench-mark網(wǎng)絡(luò)中社區(qū)分布比較平衡，網(wǎng)絡(luò)結(jié)構(gòu)也相對穩(wěn)定.因此，在LFR benchmark網(wǎng)絡(luò)上，本文所提算法LPA-TS和算法LPA-S在各類算法比較中的優(yōu)勢沒有在真實網(wǎng)絡(luò)的實驗結(jié)果表現(xiàn)明顯.

然而，真實網(wǎng)絡(luò)的社區(qū)構(gòu)成更加多樣化，社區(qū)內(nèi)部連接和社區(qū)間連接也體現(xiàn)了很大的非平衡性.因此，我們進一步在經(jīng)典的真實網(wǎng)絡(luò)上對各算法性能進行了比較.

3.3 真實網(wǎng)絡(luò)比較實驗

在本節(jié)中,我們通過在空手道俱樂部(Zachary’s Karate Club)[27]、海豚社交網(wǎng)絡(luò)(Dolphins Social Network)[28]、Polbooks[13]和大學(xué)生足球網(wǎng)絡(luò)(American College Football Network)[29]四個帶標(biāo)簽的真實網(wǎng)絡(luò)以及Les Misérables[30]，NetScience[31]，Email[32]和Yeast[33]四個無標(biāo)簽的真實網(wǎng)絡(luò)上進行實驗以對算法進行評測.數(shù)據(jù)基本情況如表1所示:

Table 1 Real Network Datasets表1 真實網(wǎng)絡(luò)數(shù)據(jù)集

由于LPA-TS算法引入了弱社區(qū)判斷，以適應(yīng)復(fù)雜的真實網(wǎng)絡(luò)中多樣性的社區(qū)變化，使其在真實網(wǎng)絡(luò)上表現(xiàn)良好.算法比較結(jié)果如表2和表3所示，其中每個算法運行30次，取各項指標(biāo)的平均值做比較.評價指標(biāo)k表示算法最終發(fā)現(xiàn)的社區(qū)個數(shù)，Q是模塊性指標(biāo)，time表示算法運行時間，σ是算法穩(wěn)定系數(shù).

表2給出了算法LPA-TS與8種經(jīng)典社區(qū)發(fā)現(xiàn)算法FMM,LPA,BGLL,LPAm,LPAm+,Infomap,ISCD+,LPA-S在有標(biāo)簽網(wǎng)絡(luò)數(shù)據(jù)集的實驗比較結(jié)果.可以看出，當(dāng)網(wǎng)絡(luò)規(guī)模較小時，各算法所發(fā)現(xiàn)的社區(qū)個數(shù)與實際社區(qū)數(shù)吻合得較好，算法穩(wěn)定性也表現(xiàn)良好；隨著網(wǎng)絡(luò)規(guī)模的逐漸增大，本文算法LPA-TS在社區(qū)個數(shù)和結(jié)果穩(wěn)定性方面表現(xiàn)突出.

圖5給出了經(jīng)典LPA算法在Karate網(wǎng)絡(luò)上的3種不同的劃分結(jié)果，由于其在節(jié)點更新順序上的隨機性，LPA對于網(wǎng)絡(luò)的劃分結(jié)果存在較大的不穩(wěn)定性，甚至在劃分過程中會將整個網(wǎng)絡(luò)中的節(jié)點劃分在一個社區(qū)中.

Table 2 Comparison of Real Networks with Labels表2 帶標(biāo)簽真實網(wǎng)絡(luò)實驗結(jié)果對比表

Notes: Bolded part indicates the best result among the 9 algorithms.

Fig.5 Different results of the LPA on Karate network圖5 LPA算法在Karate網(wǎng)絡(luò)上的3種不同的劃分結(jié)果

圖6給出了本文算法LPA-TS在Karate網(wǎng)絡(luò)上的劃分結(jié)果，將該網(wǎng)絡(luò)穩(wěn)定地劃分為2個社區(qū).

圖7給出了本文算法LPA-TS在Dolphins網(wǎng)絡(luò)上的一種劃分結(jié)果，該網(wǎng)絡(luò)表示62只寬吻海豚之間相互聯(lián)系的情況，節(jié)點表示海豚，若2只海豚間存在頻繁聯(lián)系則對應(yīng)節(jié)點間存在邊，Dolphins網(wǎng)絡(luò)中有2個社區(qū)標(biāo)簽.LPA-TS可以得到2種不同的劃分結(jié)果，這2種劃分結(jié)果的區(qū)別僅在于節(jié)點40(圖7中虛線圈出的節(jié)點)的社區(qū)歸屬.

Fig.6 Result of LPA-TS on Karate network圖6 LPA-TS在Karate網(wǎng)絡(luò)上的劃分結(jié)果

Fig.7 Result of LPA-TS on Dolphins network圖7 LPA-TS在Dolphins網(wǎng)絡(luò)上的劃分結(jié)果

Fig.8 Primitive division on Polbooks network圖8 Polbooks網(wǎng)絡(luò)原始劃分

圖8給出了Polbooks網(wǎng)絡(luò)的原始劃分情況.該網(wǎng)絡(luò)節(jié)點表示在Amazon在線書店上銷售的與美國政治相關(guān)的圖書，如2本圖書曾被同一用戶購買過，則對應(yīng)節(jié)點之間存在一條無向邊.這些圖書被分為3類：“自由派”(圓形節(jié)點)、“保守派”(菱形節(jié)點)和“中間派”(方形節(jié)點).可以看到，“自由派”和“保守派”這2個社區(qū)內(nèi)部連接比較緊密，社區(qū)間連邊比較稀疏.而“中間派”節(jié)點代表的圖書沒有明顯的政治傾向，其對應(yīng)的社區(qū)結(jié)構(gòu)也并不明顯，這給社區(qū)發(fā)現(xiàn)算法的結(jié)果準(zhǔn)確性和穩(wěn)定性帶來一定的困難.從表2可以看出，本文算法LPA-TS在NMI,ARI等指標(biāo)上表現(xiàn)更好；與LPA,BGLL,LPAm,LPAm+,LPA-S 五種結(jié)果呈現(xiàn)隨機性的算法相比，LPA-TS的算法穩(wěn)定系數(shù)更低，因此運行結(jié)果比較穩(wěn)定.圖9給出了本文算法LPA-TS在Polbooks網(wǎng)絡(luò)上所得的最終劃分結(jié)果，將Polbooks網(wǎng)絡(luò)劃分為2個社區(qū)，且各社區(qū)內(nèi)部的連邊都比較稠密，社區(qū)間的連接比較稀疏，本文算法得到較為合理的劃分.

Fig.9 Result of LPA-TS on Polbooks network圖9 LPA-TS在Polbooks網(wǎng)絡(luò)上的劃分結(jié)果

Football網(wǎng)絡(luò)是根據(jù)美國大學(xué)足球聯(lián)賽2000年一個賽季的比賽賽程而建立的實際網(wǎng)絡(luò)，共有12個足球聯(lián)盟，每個球隊都屬于某一個聯(lián)盟，因此包含12個社區(qū)標(biāo)簽.若2支隊伍之間進行過比賽，則對應(yīng)節(jié)點間存在連邊.圖10給出了LPA-TS在Football網(wǎng)絡(luò)上的劃分結(jié)果，與真實劃分更為接近.

可以看出,在帶標(biāo)簽的真實網(wǎng)絡(luò)數(shù)據(jù)中,社區(qū)劃分的模塊性并不一定很高，這是因為真實網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)更加多樣化，模塊性不能完全反映這種情況.

表3給出了算法LPA-TS與其他8種經(jīng)典社區(qū)發(fā)現(xiàn)算法在4種無標(biāo)簽真實網(wǎng)絡(luò)上的實驗結(jié)果，分別從劃分結(jié)果的模塊性和穩(wěn)定性2個方面對各算法性能進行比較.可以看出，本文算法LPA-TS的穩(wěn)定系數(shù)較低，說明其具有良好的穩(wěn)定性.

Fig.10 Result of LPA-TS on Football network圖10 LPA-TS在Football網(wǎng)絡(luò)上的劃分結(jié)果

Table 3 Comparison of Real Networks without Labels表3 無標(biāo)簽真實網(wǎng)絡(luò)實驗結(jié)果對比表

Notes: Bolded part indicates the best result among the 9 algorithms.

4 總 結(jié)

本文提出了一種基于標(biāo)簽傳播的兩階段社區(qū)發(fā)現(xiàn)算法，通過節(jié)點的參與系數(shù)確定節(jié)點更新順序，并在標(biāo)簽傳播過程中依據(jù)節(jié)點間相似性更新節(jié)點標(biāo)簽，得到社區(qū)的初始劃分結(jié)果.判斷得到的初始社區(qū)是否滿足弱社區(qū)定義，若不滿足則將其與相鄰連邊最多的社區(qū)進行合并.將初始劃分得到的社區(qū)看作節(jié)點，社區(qū)之間的連邊數(shù)作為節(jié)點間的邊權(quán)重，得到社區(qū)關(guān)系網(wǎng)絡(luò)，并按照參與系數(shù)由低到高的順序合并社區(qū)關(guān)系網(wǎng)絡(luò)中的節(jié)點，得到最終的社區(qū)劃分結(jié)果.

通過與FMM，LPA，BGLL，LPAm，LPAm+，ISCD+，LPA-S等經(jīng)典社區(qū)發(fā)現(xiàn)算法在不同參數(shù)情況下LFR benchmark人工網(wǎng)絡(luò)數(shù)據(jù)集以及真實網(wǎng)絡(luò)上的實驗比較分析，結(jié)果表明:由于LPA-TS算法減少了在節(jié)點更新和標(biāo)簽傳播過程的隨機性，社區(qū)發(fā)現(xiàn)結(jié)果表現(xiàn)了良好的穩(wěn)定性，且在標(biāo)準(zhǔn)互信息、調(diào)整蘭德系數(shù)、模塊性等方面均表現(xiàn)出較好的性能.

實際上，現(xiàn)實復(fù)雜網(wǎng)絡(luò)中存在復(fù)雜多樣的社區(qū)分布情況，如存在大量的小規(guī)模社區(qū)、社區(qū)規(guī)模分布呈現(xiàn)非平衡性、小社區(qū)內(nèi)部連接數(shù)比社區(qū)間連接數(shù)少、網(wǎng)絡(luò)結(jié)構(gòu)的動態(tài)性等特點，這給復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題帶來了多方面的挑戰(zhàn)，未來將針對復(fù)雜網(wǎng)絡(luò)中這些特殊的社區(qū)結(jié)構(gòu)特點，研制有效的社區(qū)發(fā)現(xiàn)算法.