一種基于標(biāo)簽傳播的社團(tuán)檢測算法

譚玉玲

(羅定職業(yè)技術(shù)學(xué)院 信息工程系,廣東 羅定 527200)

復(fù)雜網(wǎng)絡(luò)可看作是一個包含大量節(jié)點(diǎn)的無向圖或者有向圖，邊上的權(quán)值是節(jié)點(diǎn)與節(jié)點(diǎn)之間的相似度，相似度高的節(jié)點(diǎn)可最終被劃分進(jìn)入同一個社團(tuán).通過對社團(tuán)的檢測，可以了解到整個復(fù)雜網(wǎng)絡(luò)的發(fā)展趨勢以及整個群體的關(guān)鍵特征，并且有利于了解到網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)并提取出隱藏在復(fù)雜網(wǎng)絡(luò)中的有利信息[1].正是因?yàn)樯鐖F(tuán)檢測在日常生活中應(yīng)用地越來越廣泛，如何精確劃分復(fù)雜網(wǎng)絡(luò)成為社團(tuán)就成了人們關(guān)注的重點(diǎn).

對于傳統(tǒng)的社團(tuán)檢測算法大致可分為圖劃分方法、基于層次聚類的算法、基于進(jìn)化的算法等[2].標(biāo)簽傳播算法是一種經(jīng)典的被廣泛使用的社團(tuán)檢測算法，有著簡單、快速等優(yōu)點(diǎn).文獻(xiàn)[3]提出了最經(jīng)典的GN算法，文獻(xiàn)[4]提出了一種新的標(biāo)簽傳播的社團(tuán)檢測RAK算法，分類效果好且復(fù)雜度較低.文獻(xiàn)[5]對RAK算法進(jìn)行改進(jìn)，引入目標(biāo)函數(shù)，將算法的社團(tuán)檢測變?yōu)橐粋€模塊度最大化的問題.文獻(xiàn)[6]中改進(jìn)了節(jié)點(diǎn)標(biāo)簽的更新方式，但是容易陷入局部最優(yōu).文獻(xiàn)[7]提出了一種基于社團(tuán)核的標(biāo)簽傳播算法，改善了算法性能，但需要提前給出社團(tuán)核數(shù)目，導(dǎo)致檢測結(jié)果可能變得隨機(jī).

已有的標(biāo)簽傳播算法具有很強(qiáng)的隨機(jī)性且其魯棒性較差等問題.本文針對基于標(biāo)簽傳播算法中存在的社團(tuán)檢測結(jié)果不穩(wěn)定的情況，提出了一個基于循環(huán)查找核節(jié)點(diǎn)的標(biāo)簽傳播算法，實(shí)驗(yàn)結(jié)果證明本文所提算法可以有效檢測出社團(tuán)結(jié)構(gòu).

1 社團(tuán)檢測相關(guān)技術(shù)

1.1 標(biāo)簽傳播算法

標(biāo)簽傳播算法是一種基于圖的算法，主要思想是把復(fù)雜網(wǎng)絡(luò)圖中每個節(jié)點(diǎn)都被賦值上一個標(biāo)簽值，若相鄰節(jié)點(diǎn)與一個節(jié)點(diǎn)的相似度大，則把相鄰節(jié)點(diǎn)的標(biāo)簽值替換為該節(jié)點(diǎn)的標(biāo)簽值，具有相同標(biāo)簽的節(jié)點(diǎn)則被認(rèn)為可以規(guī)劃到同一個社團(tuán)中[8].

在實(shí)際生活中，如果A生病了，有可能會傳染給同學(xué)B，此時(shí)同學(xué)B有一個朋友C，C與A并不相識，但是B有可能傳染給C，結(jié)果導(dǎo)致C也生病，此時(shí)A、B、C理論上可被劃到一個社團(tuán)中，因?yàn)槭峭粋€原因生病.標(biāo)簽傳播算法不僅僅適用于小型網(wǎng)絡(luò)，同樣適用于大型復(fù)雜網(wǎng)絡(luò).

節(jié)點(diǎn)的標(biāo)簽被更新為節(jié)點(diǎn)相鄰數(shù)目最多的標(biāo)簽，標(biāo)簽更新的公式如下所示[9]：

li=arg maxa∑t∈Γiσ(lt,a)，

(1)

式(1)中，li表示節(jié)點(diǎn)i的標(biāo)簽，t表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)，a表示更新后的標(biāo)簽，Γ(i)是表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合，lt表示節(jié)點(diǎn)t的標(biāo)簽，當(dāng)lt與a相同時(shí)，σ(lt,a)=1，否則為0.

傳播中標(biāo)簽更新過程如圖1所示.圖中標(biāo)簽為1的節(jié)點(diǎn)的更新過程，由于標(biāo)簽為1的節(jié)點(diǎn)有4個鄰居節(jié)點(diǎn)，標(biāo)簽分別為2，3，3，5，其中有兩個鄰居節(jié)點(diǎn)的標(biāo)簽為3，則標(biāo)簽為1的節(jié)點(diǎn)將會更新為3.

(a)圖為更新標(biāo)簽之前的狀態(tài)

標(biāo)簽傳播算法的基本步驟如下所示.

步驟1：對復(fù)雜網(wǎng)絡(luò)中所有節(jié)點(diǎn)的標(biāo)簽進(jìn)行初始化；

步驟2：將算法的迭代次數(shù)初始化為n=1；

步驟3：將復(fù)雜網(wǎng)絡(luò)中的所有節(jié)點(diǎn)隨機(jī)排列形成T序列；

步驟4：對于T序列中任意一個節(jié)點(diǎn)i,Ti(n)=f(Ti1(n),……,Tim(n),Ti(m+1)(n-1),……,Tik(n-1))；

步驟5：當(dāng)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的標(biāo)簽不再更新時(shí)算法結(jié)束，否則迭代次數(shù)加1，即n=n+1，且返回步驟3.

1.2 社團(tuán)檢測結(jié)果的評價(jià)

對于社團(tuán)檢測來說，最后的結(jié)果是要得到一個社團(tuán)內(nèi)部關(guān)系緊密、社團(tuán)與社團(tuán)之間關(guān)系稀疏的劃分結(jié)果，因此，就要有一些算法評價(jià)標(biāo)準(zhǔn)來判斷劃分結(jié)果的好壞，以算出的值顯示劃分社團(tuán)的精確程度.目前，最常用的兩個算法評價(jià)標(biāo)準(zhǔn)是Newman提出的模塊度Q函數(shù)，傳統(tǒng)的模塊度存在分辨率問題[10].模塊度函數(shù)經(jīng)常被當(dāng)作社團(tuán)檢測的評價(jià)標(biāo)準(zhǔn)，模塊度Q越大，表示復(fù)雜網(wǎng)絡(luò)劃分越精確，所以優(yōu)化模塊度函數(shù)Q值一直是學(xué)者所追求的目標(biāo).對于本文中引用的無向復(fù)雜網(wǎng)絡(luò)，模塊度函數(shù)可以如式(2)表示：

(2)

其中:u表示網(wǎng)絡(luò)中隨機(jī)選擇的一個社團(tuán)，t代表復(fù)雜網(wǎng)絡(luò)中社團(tuán)的總體數(shù)目，l(u)代表社團(tuán)u內(nèi)邊的條數(shù)，m表示所有社團(tuán)即整個網(wǎng)絡(luò)的所有邊的條數(shù).

2 基于循環(huán)核心節(jié)點(diǎn)標(biāo)簽傳播的社團(tuán)檢測算法

2.1 算法的改進(jìn)思想

標(biāo)簽傳播算法大致可分為標(biāo)簽初始化階段、標(biāo)簽傳播階段和標(biāo)簽劃分階段3個部分.本文主要是通過對第2部分標(biāo)簽的傳播階段進(jìn)行改進(jìn)，實(shí)現(xiàn)算法對社團(tuán)結(jié)構(gòu)檢測的準(zhǔn)確性等方面的提高,主要采取以下策略：①利用循環(huán)核心節(jié)點(diǎn)查找傳播標(biāo)簽；②在鄰居節(jié)點(diǎn)標(biāo)簽存在相同數(shù)量的情況下，只對核心節(jié)點(diǎn)進(jìn)行賦值標(biāo)簽，其他節(jié)點(diǎn)從其靠近的核心節(jié)點(diǎn)獲取標(biāo)簽.

(1)循環(huán)查找核節(jié)點(diǎn)思想描述

在不同的復(fù)雜網(wǎng)絡(luò)中，都會存在一個與其他節(jié)點(diǎn)關(guān)系緊密且包含主要信息的一個節(jié)點(diǎn)，該節(jié)點(diǎn)被稱為核心節(jié)點(diǎn)[12].核心節(jié)點(diǎn)是網(wǎng)絡(luò)中最有影響力的節(jié)點(diǎn)，從該節(jié)點(diǎn)發(fā)出或者接受的信息也極其重要，在一個復(fù)雜網(wǎng)絡(luò)中，核心節(jié)點(diǎn)可能會存在很多個，每個社團(tuán)會有一個核心節(jié)點(diǎn)，核心節(jié)點(diǎn)的發(fā)展可能會影響這個網(wǎng)絡(luò)的發(fā)展趨勢，所以只有抓住核心節(jié)點(diǎn)的趨勢，才能夠掌握整個網(wǎng)絡(luò)的走向.通過循環(huán)查找核心節(jié)點(diǎn)，利用核心節(jié)點(diǎn)強(qiáng)大的關(guān)聯(lián)力，向核心節(jié)點(diǎn)周圍進(jìn)行標(biāo)簽傳播，如此可以大大降低算法的復(fù)雜度，提高算法的效率.

本文首先查找每個節(jié)點(diǎn)在鄰居中節(jié)點(diǎn)度最大的點(diǎn)作為核心節(jié)點(diǎn)，將核心節(jié)點(diǎn)作為潛在社團(tuán)的中心，并將標(biāo)簽傳播給它的鄰居，逐步形成社團(tuán).由于每個核心節(jié)點(diǎn)對鄰居節(jié)點(diǎn)的影響程度不同，所以還需要計(jì)算核心節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的相似程度.

(2)降低標(biāo)簽傳播隨機(jī)性思想描述

當(dāng)對節(jié)點(diǎn)進(jìn)行標(biāo)簽初始化后，則會從一個節(jié)點(diǎn)開始進(jìn)行標(biāo)簽傳播，當(dāng)節(jié)點(diǎn)與節(jié)點(diǎn)之間邊上的權(quán)值越大時(shí)，該節(jié)點(diǎn)的標(biāo)簽就會傳播到權(quán)值大的邊所連接的相鄰節(jié)點(diǎn)上，該節(jié)點(diǎn)的標(biāo)簽值就會覆蓋鄰居節(jié)點(diǎn)的標(biāo)簽值，即鄰居節(jié)點(diǎn)的標(biāo)簽更新.在理想狀態(tài)下，每一次迭代過程中，與一個節(jié)點(diǎn)連接的所有的邊中有且僅有一條邊上的權(quán)值最大，即只存在一個鄰居節(jié)點(diǎn)會成為該節(jié)點(diǎn)的傳播候選節(jié)點(diǎn).然而，有時(shí)候會出現(xiàn)與該節(jié)點(diǎn)連接的多條邊上的權(quán)值均相等的情況，此時(shí)就會出現(xiàn)多個節(jié)點(diǎn)成為該節(jié)點(diǎn)的傳播候選節(jié)點(diǎn).目前存在的很多算法在遇到這種情況時(shí)會在傳播候選節(jié)點(diǎn)中隨機(jī)選擇一個節(jié)點(diǎn)進(jìn)行標(biāo)簽傳播，這就是標(biāo)簽傳播算法的隨機(jī)性.這種隨機(jī)性大大增加了算法的復(fù)雜程度，也影響了算法最后劃分社團(tuán)的準(zhǔn)確性.在標(biāo)簽的傳播過程和選擇過程中，當(dāng)幾個節(jié)點(diǎn)的標(biāo)簽值相同時(shí)，標(biāo)簽劃分也是隨機(jī)的，這一方面也大大增加了算法的復(fù)雜程度.

所以本文算法從傳播和選擇的隨機(jī)性進(jìn)行改進(jìn)，降低這兩個部分的隨機(jī)性.在標(biāo)簽傳播初始化階段，循環(huán)查找到核心節(jié)點(diǎn)后，只對核心節(jié)點(diǎn)賦值標(biāo)簽，周圍其余的節(jié)點(diǎn)只從其靠近的核心節(jié)點(diǎn)獲取標(biāo)簽，加入社團(tuán).

2.2 改進(jìn)算法總體描述

(1)改進(jìn)算法總體框架描述

圖2 算法總體框架

(2) 網(wǎng)絡(luò)預(yù)劃分算法描述

輸入：網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n，網(wǎng)絡(luò)拓?fù)湫畔ⅲ?/p>

輸出：預(yù)劃分的結(jié)果f1.

步驟1：初始化網(wǎng)絡(luò)中所有節(jié)點(diǎn)標(biāo)簽：1, 2,……,n,其中n表示網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)；

步驟2：根據(jù)網(wǎng)絡(luò)拓?fù)湫畔⒂?jì)算節(jié)點(diǎn)及其鄰居的節(jié)點(diǎn)度；

步驟3：選擇網(wǎng)絡(luò)中相互連接的節(jié)點(diǎn)度最大的節(jié)點(diǎn)作為核節(jié)點(diǎn)，初始化核節(jié)點(diǎn)集合；

步驟4：計(jì)算核節(jié)點(diǎn)與其鄰居的相似度Fs，當(dāng)Fs高于某閾值，將該鄰居節(jié)點(diǎn)標(biāo)簽改為該核節(jié)點(diǎn)標(biāo)簽，否則鄰居節(jié)點(diǎn)標(biāo)簽保持不變；

步驟5：若此時(shí)迭代未結(jié)束，則整理未改變標(biāo)簽的節(jié)點(diǎn)作為新的網(wǎng)絡(luò)，轉(zhuǎn)向步驟2，否則轉(zhuǎn)向步驟6；

步驟6：輸出預(yù)劃分結(jié)果f1.

(3) 基于標(biāo)簽傳播算法的預(yù)劃分優(yōu)化

輸入：網(wǎng)絡(luò)預(yù)劃分結(jié)果f1，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n，網(wǎng)絡(luò)拓?fù)湫畔ⅲ?/p>

輸出：預(yù)劃分的結(jié)果f2；

步驟1：整理網(wǎng)絡(luò)預(yù)劃分結(jié)果中的節(jié)點(diǎn)標(biāo)簽；

步驟2：根據(jù)網(wǎng)絡(luò)拓?fù)湫畔⒅饌€搜索節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的標(biāo)簽；

步驟3：選擇節(jié)點(diǎn)鄰居中數(shù)目最多的標(biāo)簽，將該標(biāo)簽更新為此節(jié)點(diǎn)的標(biāo)簽；

步驟4：根據(jù)是否所有節(jié)點(diǎn)標(biāo)簽達(dá)到穩(wěn)定不再變化，或者根據(jù)迭代次數(shù)判斷更新是否結(jié)束，若結(jié)束，輸出劃分結(jié)果f2，否則返回步驟3.

(4)算法隨機(jī)性的改進(jìn)

初始化時(shí)，對核心節(jié)點(diǎn)賦值，稱為點(diǎn)值，復(fù)雜網(wǎng)絡(luò)中其他節(jié)點(diǎn)不賦值.

步驟1：計(jì)算所有節(jié)點(diǎn)的點(diǎn)值；

步驟3：找出部分的點(diǎn)值極值點(diǎn)的節(jié)點(diǎn)后，對該節(jié)點(diǎn)進(jìn)行賦值標(biāo)簽值；

步驟4：迭代次數(shù)初始化n=1；

步驟5：更新節(jié)點(diǎn)數(shù)量初始化s=0，在極值節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)j，將節(jié)點(diǎn)j的標(biāo)簽更新為鄰居節(jié)點(diǎn)中極值最大的那個節(jié)點(diǎn)的標(biāo)簽值.如果節(jié)點(diǎn)j的標(biāo)簽值更新，則s=s+1；

步驟6：如果s>0，則n=n+1，并跳轉(zhuǎn)至步驟5.

3 算法驗(yàn)證與分析

3.1 對比算法與測試網(wǎng)絡(luò)

為了驗(yàn)證本文算法在人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)下的實(shí)驗(yàn)結(jié)果，選取了7種典型算法進(jìn)行對比.對比算法如下: LPA算法[11]、LPAm算法[12]、MIGA算法[13]、GN算法[14]、Meme-net算法[15]、MOEA/D算法[16]以及GA算法[17].LPA是標(biāo)準(zhǔn)的標(biāo)簽傳播算法；MIGA算法是一種基于模塊度的改進(jìn)遺傳算法，通過優(yōu)化模塊度函數(shù)獲得較優(yōu)的社團(tuán)檢測結(jié)果；GN算法通過計(jì)算邊界數(shù)將邊移除從而分解網(wǎng)絡(luò)，得到網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)；Meme-Net算法是一種協(xié)同的遺傳算法，并采用爬山法作為局部搜索方法；MOEA/D算法基于多目標(biāo)進(jìn)化算法的社團(tuán)檢測；GA算法是一種檢測網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的遺傳算法，該方法引入社團(tuán)得分的概念，并通過最大化社團(tuán)得分獲得最佳的網(wǎng)絡(luò)劃分.算法參數(shù)設(shè)置與文獻(xiàn)中推薦的保持一致.

本文測試網(wǎng)絡(luò)如下：Karate網(wǎng)絡(luò)空手道俱樂部的復(fù)雜網(wǎng)絡(luò)；Football網(wǎng)絡(luò)美國大學(xué)足球隊(duì)的復(fù)雜網(wǎng)絡(luò)；還有Dolphin網(wǎng)絡(luò)新西蘭海豚的復(fù)雜網(wǎng)絡(luò).本文采用了模塊度函數(shù)Q值算法評價(jià)標(biāo)準(zhǔn)，最后使用Q值與其他算法的Q值結(jié)果進(jìn)行對比.

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

各種算法在空手道Karate復(fù)雜網(wǎng)絡(luò)上的Q值結(jié)果比較檢測如圖3所示.

圖3 空手道Karate的Q值結(jié)果比較圖

由圖3可知，本文算法在空手道Karate復(fù)雜網(wǎng)絡(luò)上的Q值是0.4198，與其中3種算法結(jié)果相同，略高于剩下兩種算法，所以本文的算法在空手道Karate復(fù)雜網(wǎng)絡(luò)上的結(jié)果是可行的.

各種算法在美國大學(xué)足球隊(duì)Football復(fù)雜網(wǎng)絡(luò)上的Q值結(jié)果比較如圖4所示.

由圖4可知，本文算法在美國大學(xué)足球隊(duì)Football復(fù)雜網(wǎng)絡(luò)上的Q值是0.6034，高于其中四種算法，所以本文的算法在美國大學(xué)足球隊(duì)Football復(fù)雜網(wǎng)絡(luò)上的結(jié)果是可行的.

各種算法在新西蘭海豚Dolphin復(fù)雜網(wǎng)絡(luò)上的Q值結(jié)果比較如圖5所示.

圖4 美國大學(xué)足球隊(duì)Football的Q值結(jié)果比較圖

圖5 新西蘭海豚Dolphin的Q值結(jié)果比較圖

由圖5可知，本文算法在新西蘭海豚Dolphin復(fù)雜網(wǎng)絡(luò)上的Q值是0.5276，略高于其他5種算法，所以本文的算法在新西蘭海豚Dolphin復(fù)雜網(wǎng)絡(luò)上的結(jié)果是可行的.

各種算法在以上3個復(fù)雜網(wǎng)絡(luò)模型的Q值結(jié)果最優(yōu)值總結(jié)如表1所列.

4 結(jié)論

本文提出了一種改進(jìn)的標(biāo)簽傳播社團(tuán)檢測算法，使用循環(huán)查找核心節(jié)點(diǎn)的方法，增加社團(tuán)檢測結(jié)果的多樣性.在標(biāo)簽傳播過程中，減少隨機(jī)性的影響，結(jié)果表明了算法的有效性.今后的研究將進(jìn)一步考慮算法的時(shí)間復(fù)雜度，設(shè)計(jì)更優(yōu)秀的社團(tuán)檢測算法.

表1 最優(yōu)值總結(jié)