蔡威林， 葛 斌

(安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

0 引 言

近年來(lái)，社區(qū)檢測(cè)越來(lái)越引起研究者的關(guān)注，許多社交網(wǎng)絡(luò)社區(qū)檢測(cè)算法被提出。LPA算法[1]是經(jīng)典的社區(qū)檢測(cè)算法之一。但其算法結(jié)果不穩(wěn)定，易出現(xiàn)社區(qū)劃分錯(cuò)誤的情況。

針對(duì)這些問(wèn)題，許多學(xué)者對(duì)標(biāo)準(zhǔn)LPA算法進(jìn)行了改進(jìn)。Xie等人[2]提出了一種標(biāo)簽傳播算法SLPA，每次迭代所更新的標(biāo)簽之后，使用存儲(chǔ)列表來(lái)存放得到新的迭代序列。Xing等人[3]提出了一種新的基于節(jié)點(diǎn)影響的社區(qū)檢測(cè)標(biāo)簽傳播算法NIBLPA，該算法通過(guò)改進(jìn)標(biāo)簽更新的節(jié)點(diǎn)順序和最大節(jié)點(diǎn)數(shù)包含多個(gè)標(biāo)簽時(shí)的標(biāo)簽選擇機(jī)制來(lái)提高LPA算法的性能。Zhang等人[4]提出了一種基于標(biāo)簽影響的社區(qū)檢測(cè)標(biāo)簽傳播算法，將節(jié)點(diǎn)重要性考慮在標(biāo)簽傳播中。Xu等人[5]提出TNS-LPA算法，采取兩級(jí)鄰域相似性度量，根據(jù)節(jié)點(diǎn)重要性異步更新標(biāo)簽，提高了算法的性能。Zhang等人[6]提出了一種基于節(jié)點(diǎn)權(quán)重的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)標(biāo)簽傳播策略。它選擇在網(wǎng)絡(luò)中具有更大影響力的核心節(jié)點(diǎn)。Deng等人[7]提出用模糊C均值隸屬度向量修正每個(gè)社區(qū)中多樣性較大的標(biāo)簽。李等人[8]提出節(jié)點(diǎn)與其鄰居間的關(guān)系以及節(jié)點(diǎn)間的雙向作用,利用節(jié)點(diǎn)重要性和相似性指標(biāo)衡量鄰居對(duì)節(jié)點(diǎn)的影響,以此來(lái)計(jì)算節(jié)點(diǎn)標(biāo)簽作用力的標(biāo)簽傳播算法。Ma等人[9]提出通過(guò)相似度通過(guò)結(jié)合灰色相關(guān)度和Jaccard指數(shù)來(lái)改進(jìn)標(biāo)簽傳播方法。楊等人[10]提出選取高影響力的種子節(jié)點(diǎn)，將相似度作為節(jié)點(diǎn)間連接強(qiáng)度，提高了社區(qū)檢測(cè)算法的準(zhǔn)確度。

提出基于影響力的社區(qū)檢測(cè)算法D-LPA(Degree, Label Propagation Algorithm)。首先計(jì)算利用節(jié)點(diǎn)間權(quán)重定義影響度，將影響度作為節(jié)點(diǎn)迭代的依據(jù)，鄰居相似度作為更新節(jié)點(diǎn)的約束條件，社區(qū)再通過(guò)合并得出最終的社區(qū)結(jié)構(gòu)。

1 社區(qū)發(fā)現(xiàn)相關(guān)概念

一個(gè)復(fù)雜的網(wǎng)絡(luò)可以建模為一個(gè)圖G=(V,E)，V={v1,v2,…,vn}代表節(jié)點(diǎn)的集合，E={e1,e2,…,en}代表節(jié)點(diǎn)之間的邊。

根據(jù)節(jié)點(diǎn)標(biāo)簽在初始社區(qū)的變化，定義節(jié)點(diǎn)間權(quán)重公式為式(1)：

(1)

式(1)中Te(i)表示節(jié)點(diǎn)vi的鄰居中發(fā)生標(biāo)簽變化的個(gè)數(shù)，di表示節(jié)點(diǎn)vi的度。

其次，考慮到節(jié)點(diǎn)自身和其鄰居節(jié)點(diǎn)總體變化，定義節(jié)點(diǎn)權(quán)重指數(shù)為式(2)：

(2)

式(2)中Ci為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合。

結(jié)合基于節(jié)點(diǎn)權(quán)重指數(shù)的結(jié)果，定義節(jié)點(diǎn)間權(quán)重為式(3)：

(3)

2 影響度社區(qū)選擇

D-LPA算法由以下幾個(gè)階段組成：網(wǎng)絡(luò)社區(qū)初始劃分、標(biāo)簽傳播過(guò)程和社區(qū)合并。

2.1 網(wǎng)絡(luò)社區(qū)初始劃分

對(duì)于網(wǎng)絡(luò)的初始劃分需要兩步： 第一步確定種子節(jié)點(diǎn)。社交網(wǎng)絡(luò)中社區(qū)劃分基本圍繞一個(gè)或多個(gè)中心節(jié)點(diǎn)構(gòu)成。種子節(jié)點(diǎn)的個(gè)數(shù)設(shè)為閾值H。

第二步選擇初始社區(qū)。在社交網(wǎng)絡(luò)中將數(shù)字編號(hào)作為初始標(biāo)簽賦予種子節(jié)點(diǎn)。如果種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)沒(méi)有初始標(biāo)簽，則分配與種子節(jié)點(diǎn)相同的初始標(biāo)簽。當(dāng)所有節(jié)點(diǎn)都獲得初始標(biāo)簽時(shí)，初始社區(qū)劃分結(jié)束。

2.2 標(biāo)簽傳播過(guò)程

經(jīng)過(guò)初始社區(qū)劃分，存在一些明顯錯(cuò)誤的社區(qū)劃分結(jié)構(gòu)。LPA算法在標(biāo)簽傳播過(guò)程中采取的隨機(jī)迭代順序，因此每次生成的社區(qū)結(jié)果可能會(huì)不同，導(dǎo)致數(shù)據(jù)波動(dòng)結(jié)果不準(zhǔn)確。因此提出全新的節(jié)點(diǎn)迭代方法。

首先，在網(wǎng)絡(luò)社區(qū)初始劃分之后，按照社區(qū)中節(jié)點(diǎn)個(gè)數(shù)的多少將節(jié)點(diǎn)集Nm倒序排列。

然后，將每個(gè)社區(qū)內(nèi)節(jié)點(diǎn)集合中的節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)的影響度從大到小排列，節(jié)點(diǎn)i的影響度Di定義為式(4)：

Di=α|di|+(1-α)∑i，j∈CiAW(i,j)

(4)

式(4)中α是調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點(diǎn)之間的權(quán)重比例，一般在網(wǎng)絡(luò)中設(shè)置為0.5。

在傳播過(guò)程中，根據(jù)節(jié)點(diǎn)相似度判斷節(jié)點(diǎn)之間的是否可以進(jìn)行標(biāo)簽傳播。選擇鄰居節(jié)點(diǎn)中相似程度最高的節(jié)點(diǎn)標(biāo)簽進(jìn)行更新，當(dāng)出現(xiàn)多個(gè)相似度最高的標(biāo)簽時(shí)，選擇其中節(jié)點(diǎn)影響度Di值最高的節(jié)點(diǎn)標(biāo)簽。節(jié)點(diǎn)相似度定義為式(5)：

(5)

式(5)中Ci，Cj為節(jié)點(diǎn)i，j的鄰居節(jié)點(diǎn)集合。

2.3 社區(qū)合并

經(jīng)過(guò)兩個(gè)階段之后的社交網(wǎng)絡(luò)，社區(qū)劃分初步形成，但網(wǎng)絡(luò)中依舊存在一些分配到不相似社區(qū)的錯(cuò)誤節(jié)點(diǎn)，因此社區(qū)合并過(guò)程可以進(jìn)一步提高D-LPA算法社區(qū)劃分的準(zhǔn)確性。根據(jù)社區(qū)中種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)相似程度定義出社區(qū)間的相似度，可以表示為式(6)：

(6)

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集

選取了三個(gè)具有真實(shí)社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，包括 Karate 網(wǎng)絡(luò)(43個(gè)節(jié)點(diǎn)，78條邊)，Dolphins 網(wǎng)絡(luò)(62個(gè)節(jié)點(diǎn)，159條邊)和 Footballs 網(wǎng)絡(luò)(115個(gè)節(jié)點(diǎn)，613條邊)，它們均屬于社區(qū)結(jié)構(gòu)較為明顯的網(wǎng)絡(luò)結(jié)構(gòu)。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

1)第一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)為模塊性(Q，Modularity)。模塊性(Q)可以定義為式(7)：

(7)

其中，di，dj表示節(jié)點(diǎn)i,j的度數(shù)，如果節(jié)點(diǎn)i,j在同一個(gè)社區(qū)，則函數(shù)δ(i,j)等于1，否則函數(shù)等于0。當(dāng)所有節(jié)點(diǎn)都?xì)w屬同一個(gè)社區(qū)的時(shí)候，Q=0。

2)第二個(gè)評(píng)價(jià)標(biāo)準(zhǔn)為標(biāo)準(zhǔn)互信息(NMI，Normalized Mutual Information)。NMI定義為式(8)：

(8)

式(8)中|A|和|B|分別是分區(qū)A和B中社區(qū)數(shù)。Oi和Oj分別表示矩陣的第1行元素之和和第1列元素之和，Oij表示同時(shí)屬于團(tuán)體A共和團(tuán)體B的公共節(jié)點(diǎn)的數(shù)量。

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

對(duì)提出的D-LPA算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，并對(duì)比LPA,SLPA,NIBLPA三種標(biāo)簽傳播算法的實(shí)驗(yàn)結(jié)果進(jìn)行分析實(shí)驗(yàn)數(shù)據(jù)。

3.3.1 閾值H分析

在圖1中縱坐標(biāo)表示模塊值，橫坐標(biāo)表示種子節(jié)點(diǎn)占網(wǎng)絡(luò)中總節(jié)點(diǎn)的比例。對(duì)比三個(gè)數(shù)據(jù)集在不同比例下的模塊值，發(fā)現(xiàn)當(dāng)取值為網(wǎng)絡(luò)節(jié)點(diǎn)的20%時(shí)，三個(gè)網(wǎng)絡(luò)都取到了最大值。

圖1 算法在真實(shí)數(shù)據(jù)集上的閾值H

3.3.2 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果與分析

在圖2中，D-LPA算法模塊性Q的曲線均在其他算法的曲線之上，明顯高于對(duì)比的三種算法，得到了更加清晰的社區(qū)分布。

圖2 各算法模塊性Q值

在圖3中，三個(gè)真實(shí)網(wǎng)絡(luò)，D-LPA算法NMI值的結(jié)果與其他算法相近。但在Dolphins網(wǎng)絡(luò)中，結(jié)果低于其他三種算法。因?yàn)檎鎸?shí)的Dolphins網(wǎng)絡(luò)社區(qū)劃分將社區(qū)分為兩個(gè)，模塊性較低。所以在保證模塊性的前提下進(jìn)行了更細(xì)致的社區(qū)劃分，故導(dǎo)致NMI值低于其他三種算法。

圖3 各算法NMI值

4 結(jié) 語(yǔ)

提出了一種基于節(jié)點(diǎn)影響力標(biāo)簽傳播算法D-LPA。網(wǎng)絡(luò)初始劃分中，選擇節(jié)點(diǎn)度高的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，并采取影響度Di進(jìn)行初始社區(qū)劃分，且設(shè)置閾值H判斷種子節(jié)點(diǎn)數(shù)量。標(biāo)簽傳播過(guò)程中，通過(guò)節(jié)點(diǎn)權(quán)重確定標(biāo)簽迭代順序，再根據(jù)鄰居節(jié)點(diǎn)之間的相似性作為標(biāo)簽更新策略。社區(qū)合并過(guò)程中，種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)相似度進(jìn)行社區(qū)合并。在真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)分析，D-LPA 算法表現(xiàn)良好，明顯優(yōu)于同類(lèi)型其他算法。