譚玉玲

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

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

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

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

1 社團檢測相關技術

1.1 標簽傳播算法

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

在實際生活中，如果A生病了，有可能會傳染給同學B，此時同學B有一個朋友C，C與A并不相識，但是B有可能傳染給C，結果導致C也生病，此時A、B、C理論上可被劃到一個社團中，因為是同一個原因生病.標簽傳播算法不僅僅適用于小型網絡，同樣適用于大型復雜網絡.

節(jié)點的標簽被更新為節(jié)點相鄰數目最多的標簽，標簽更新的公式如下所示[9]：

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

(1)

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

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

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

標簽傳播算法的基本步驟如下所示.

步驟1：對復雜網絡中所有節(jié)點的標簽進行初始化；

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

步驟3：將復雜網絡中的所有節(jié)點隨機排列形成T序列；

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

步驟5：當網絡中所有節(jié)點的標簽不再更新時算法結束，否則迭代次數加1，即n=n+1，且返回步驟3.

1.2 社團檢測結果的評價

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

(2)

其中:u表示網絡中隨機選擇的一個社團，t代表復雜網絡中社團的總體數目，l(u)代表社團u內邊的條數，m表示所有社團即整個網絡的所有邊的條數.

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

2.1 算法的改進思想

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

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

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

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

(2)降低標簽傳播隨機性思想描述

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

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

2.2 改進算法總體描述

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

圖2 算法總體框架

(2) 網絡預劃分算法描述

輸入：網絡節(jié)點數n，網絡拓撲信息；

輸出：預劃分的結果f1.

步驟1：初始化網絡中所有節(jié)點標簽：1, 2,……,n,其中n表示網絡中節(jié)點數；

步驟2：根據網絡拓撲信息計算節(jié)點及其鄰居的節(jié)點度；

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

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

步驟5：若此時迭代未結束，則整理未改變標簽的節(jié)點作為新的網絡，轉向步驟2，否則轉向步驟6；

步驟6：輸出預劃分結果f1.

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

輸入：網絡預劃分結果f1，網絡節(jié)點數n，網絡拓撲信息；

輸出：預劃分的結果f2；

步驟1：整理網絡預劃分結果中的節(jié)點標簽；

步驟2：根據網絡拓撲信息逐個搜索節(jié)點的鄰居節(jié)點的標簽；

步驟3：選擇節(jié)點鄰居中數目最多的標簽，將該標簽更新為此節(jié)點的標簽；

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

(4)算法隨機性的改進

初始化時，對核心節(jié)點賦值，稱為點值，復雜網絡中其他節(jié)點不賦值.

步驟1：計算所有節(jié)點的點值；

步驟3：找出部分的點值極值點的節(jié)點后，對該節(jié)點進行賦值標簽值；

步驟4：迭代次數初始化n=1；

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

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

3 算法驗證與分析

3.1 對比算法與測試網絡

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

本文測試網絡如下：Karate網絡空手道俱樂部的復雜網絡；Football網絡美國大學足球隊的復雜網絡；還有Dolphin網絡新西蘭海豚的復雜網絡.本文采用了模塊度函數Q值算法評價標準，最后使用Q值與其他算法的Q值結果進行對比.

3.2 實驗結果與分析

各種算法在空手道Karate復雜網絡上的Q值結果比較檢測如圖3所示.

圖3 空手道Karate的Q值結果比較圖

由圖3可知，本文算法在空手道Karate復雜網絡上的Q值是0.4198，與其中3種算法結果相同，略高于剩下兩種算法，所以本文的算法在空手道Karate復雜網絡上的結果是可行的.

各種算法在美國大學足球隊Football復雜網絡上的Q值結果比較如圖4所示.

由圖4可知，本文算法在美國大學足球隊Football復雜網絡上的Q值是0.6034，高于其中四種算法，所以本文的算法在美國大學足球隊Football復雜網絡上的結果是可行的.

各種算法在新西蘭海豚Dolphin復雜網絡上的Q值結果比較如圖5所示.

圖4 美國大學足球隊Football的Q值結果比較圖

圖5 新西蘭海豚Dolphin的Q值結果比較圖

由圖5可知，本文算法在新西蘭海豚Dolphin復雜網絡上的Q值是0.5276，略高于其他5種算法，所以本文的算法在新西蘭海豚Dolphin復雜網絡上的結果是可行的.

各種算法在以上3個復雜網絡模型的Q值結果最優(yōu)值總結如表1所列.

4 結論

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

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