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

鄭文萍 車晨浩 錢宇華 王 杰

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

復(fù)雜網(wǎng)絡(luò)分析在社會(huì)學(xué)、傳染病學(xué)和生物學(xué)等領(lǐng)域有著廣泛的應(yīng)用[1-3].通?？梢杂脠DG=(V,E)表示一個(gè)復(fù)雜網(wǎng)絡(luò),其中V表示網(wǎng)絡(luò)中個(gè)體的集合,E表示個(gè)體間聯(lián)系的集合.社區(qū)結(jié)構(gòu)(community structure)是復(fù)雜網(wǎng)絡(luò)的重要特征之一,即一個(gè)網(wǎng)絡(luò)可以分成若干社區(qū),社區(qū)內(nèi)節(jié)點(diǎn)之間連接相對(duì)緊密,社區(qū)間節(jié)點(diǎn)連接相對(duì)稀疏.有效的社區(qū)發(fā)現(xiàn)算法可以發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)、生物網(wǎng)絡(luò)中的蛋白質(zhì)功能模塊等,有助于深入研究各種類型復(fù)雜網(wǎng)絡(luò)的功能模塊及其演化特征,對(duì)準(zhǔn)確地理解并分析復(fù)雜系統(tǒng)的拓?fù)浣Y(jié)構(gòu)及動(dòng)力學(xué)特性具有十分重要的理論意義和應(yīng)用價(jià)值[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ù)進(jìn)行社區(qū)合并和更新.Blondel等人提出了BGLL算法[12],隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為初始社區(qū),迭代選擇使當(dāng)前社區(qū)模塊性增長(zhǎng)最大節(jié)點(diǎn)加入當(dāng)前社區(qū)完成社區(qū)擴(kuò)展過程.由于現(xiàn)實(shí)網(wǎng)絡(luò)包含大量的小規(guī)模社區(qū),網(wǎng)絡(luò)社區(qū)內(nèi)部連接數(shù)不一定比社區(qū)之間的連接數(shù)多,導(dǎo)致模塊性不能較好地度量社區(qū)劃分質(zhì)量.Bai等人[13]基于互補(bǔ)熵理論提出了一種度量網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)質(zhì)量的目標(biāo)函數(shù),該函數(shù)綜合考慮社區(qū)內(nèi)緊密程度和社區(qū)間稀疏程度對(duì)社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行評(píng)價(jià),并以公共鄰居數(shù)度量節(jié)點(diǎn)相似性給出了一種圖聚類算法ISCD+.

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

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

1 背景知識(shí)

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

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

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

2.1 節(jié)點(diǎn)更新順序

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

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

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

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

2.2 標(biāo)簽傳播

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

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

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

(6)

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

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

步驟1.根據(jù)

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

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

步驟4.根據(jù)

計(jì)算節(jié)點(diǎn)vi的參與系數(shù).

步驟7.t=t+1.

圖2給出了在Karate網(wǎng)絡(luò)上的初始社區(qū)發(fā)現(xiàn)結(jié)果.其中節(jié)點(diǎn)被初始劃分為4個(gè)社區(qū)(用不同形狀表示).可以看出，算法1的初始社區(qū)劃分結(jié)果中，度數(shù)較大節(jié)點(diǎn)由于與鄰居節(jié)點(diǎn)的相似性較高，容易將自身標(biāo)簽傳播給鄰居節(jié)點(diǎn)，從而形成以大度節(jié)點(diǎn)為中心的較大社區(qū).而位于社區(qū)邊緣的一些節(jié)點(diǎn)，由于度數(shù)偏低且與鄰居節(jié)點(diǎn)的相似性小，容易形成一些規(guī)模較小的社區(qū)，如圖2中菱形節(jié)點(diǎn)和三角形節(jié)點(diǎn)構(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ò)連接比較稀疏時(shí)，算法第1階段會(huì)得到大量的特別小規(guī)模的社區(qū)，造成對(duì)原始網(wǎng)絡(luò)的過劃分.為了得到更準(zhǔn)確的社區(qū)劃分結(jié)果，還需要對(duì)初始社區(qū)劃分結(jié)果進(jìn)行社區(qū)合并.

2.4 社區(qū)合并過程

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

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

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

(7)

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

為了對(duì)節(jié)點(diǎn)標(biāo)簽傳播過程進(jìn)行有效控制，需要從社區(qū)內(nèi)部連接緊密程度以及社區(qū)間連接的稀疏程度同時(shí)考慮社區(qū)發(fā)現(xiàn)質(zhì)量，因此本文選擇文獻(xiàn)[13]提出的基于互補(bǔ)熵的評(píng)價(jià)函數(shù)，對(duì)當(dāng)前社區(qū)合并結(jié)果進(jìn)行評(píng)價(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.計(jì)算當(dāng)前網(wǎng)絡(luò)劃分的評(píng)價(jià)函數(shù)值F(Ωt+1).

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 評(píng)價(jià)指標(biāo)

(9)

(10)

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

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

(11)

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

(12)

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

(13)

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

3.2 人工網(wǎng)絡(luò)實(shí)驗(yàn)

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

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

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

3.3 真實(shí)網(wǎng)絡(luò)比較實(shí)驗(yàn)

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

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

由于LPA-TS算法引入了弱社區(qū)判斷，以適應(yīng)復(fù)雜的真實(shí)網(wǎng)絡(luò)中多樣性的社區(qū)變化，使其在真實(shí)網(wǎng)絡(luò)上表現(xiàn)良好.算法比較結(jié)果如表2和表3所示，其中每個(gè)算法運(yùn)行30次，取各項(xiàng)指標(biāo)的平均值做比較.評(píng)價(jià)指標(biāo)k表示算法最終發(fā)現(xiàn)的社區(qū)個(gè)數(shù)，Q是模塊性指標(biāo)，time表示算法運(yùn)行時(shí)間，σ是算法穩(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ù)集的實(shí)驗(yàn)比較結(jié)果.可以看出，當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，各算法所發(fā)現(xiàn)的社區(qū)個(gè)數(shù)與實(shí)際社區(qū)數(shù)吻合得較好，算法穩(wěn)定性也表現(xiàn)良好；隨著網(wǎng)絡(luò)規(guī)模的逐漸增大，本文算法LPA-TS在社區(qū)個(gè)數(shù)和結(jié)果穩(wěn)定性方面表現(xiàn)突出.

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

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

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個(gè)社區(qū).

圖7給出了本文算法LPA-TS在Dolphins網(wǎng)絡(luò)上的一種劃分結(jié)果，該網(wǎng)絡(luò)表示62只寬吻海豚之間相互聯(lián)系的情況，節(jié)點(diǎn)表示海豚，若2只海豚間存在頻繁聯(lián)系則對(duì)應(yīng)節(jié)點(diǎn)間存在邊，Dolphins網(wǎng)絡(luò)中有2個(gè)社區(qū)標(biāo)簽.LPA-TS可以得到2種不同的劃分結(jié)果，這2種劃分結(jié)果的區(qū)別僅在于節(jié)點(diǎn)40(圖7中虛線圈出的節(jié)點(diǎn))的社區(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é)點(diǎn)表示在Amazon在線書店上銷售的與美國(guó)政治相關(guān)的圖書，如2本圖書曾被同一用戶購買過，則對(duì)應(yīng)節(jié)點(diǎn)之間存在一條無向邊.這些圖書被分為3類：“自由派”(圓形節(jié)點(diǎn))、“保守派”(菱形節(jié)點(diǎn))和“中間派”(方形節(jié)點(diǎn)).可以看到，“自由派”和“保守派”這2個(gè)社區(qū)內(nèi)部連接比較緊密，社區(qū)間連邊比較稀疏.而“中間派”節(jié)點(diǎn)代表的圖書沒有明顯的政治傾向，其對(duì)應(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)隨機(jī)性的算法相比，LPA-TS的算法穩(wěn)定系數(shù)更低，因此運(yùn)行結(jié)果比較穩(wěn)定.圖9給出了本文算法LPA-TS在Polbooks網(wǎng)絡(luò)上所得的最終劃分結(jié)果，將Polbooks網(wǎng)絡(luò)劃分為2個(gè)社區(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ù)美國(guó)大學(xué)足球聯(lián)賽2000年一個(gè)賽季的比賽賽程而建立的實(shí)際網(wǎng)絡(luò)，共有12個(gè)足球聯(lián)盟，每個(gè)球隊(duì)都屬于某一個(gè)聯(lián)盟，因此包含12個(gè)社區(qū)標(biāo)簽.若2支隊(duì)伍之間進(jìn)行過比賽，則對(duì)應(yīng)節(jié)點(diǎn)間存在連邊.圖10給出了LPA-TS在Football網(wǎng)絡(luò)上的劃分結(jié)果，與真實(shí)劃分更為接近.

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

表3給出了算法LPA-TS與其他8種經(jīng)典社區(qū)發(fā)現(xiàn)算法在4種無標(biāo)簽真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果，分別從劃分結(jié)果的模塊性和穩(wěn)定性2個(gè)方面對(duì)各算法性能進(jìn)行比較.可以看出，本文算法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)簽真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果對(duì)比表

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

4 總 結(jié)

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

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

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