基于影響度的標簽傳播算法 ①

蔡威林， 葛 斌

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

0 引 言

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

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

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

2.2 標簽傳播過程

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

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

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

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

(4)

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

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

(5)

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

2.3 社區(qū)合并

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

(6)

3 實 驗

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

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

3.2 評價標準

1)第一個評價標準為模塊性(Q，Modularity)。模塊性(Q)可以定義為式(7)：

(7)

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

2)第二個評價標準為標準互信息(NMI，Normalized Mutual Information)。NMI定義為式(8)：

(8)

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

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

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

3.3.1 閾值H分析

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

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

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

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

圖2 各算法模塊性Q值

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

圖3 各算法NMI值

4 結(jié) 語

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