顧軍華 江 帆 武君艷 許馨勻 張素琪

1(河北工業(yè)大學人工智能與數據科學學院 天津 300401)2(河北省大數據計算重點實驗室 天津 300401)3(天津商業(yè)大學信息工程學院 天津 300314)

0 引 言

自然界中各領域都存在復雜的網絡結構，如社交網絡、蛋白質的相互作用網絡等[1]。挖掘這些網絡結構中隱含的信息成為既有難度又有意義的課題[2]。自Newman等[3]提出社區(qū)概念以后，復雜網絡的社區(qū)發(fā)現研究逐漸成為最熱門的課題之一。社區(qū)發(fā)現算法可以對網絡中的社區(qū)結構進行檢測，從而獲得網絡的隱含信息，具有重要的實際意義。目前，挖掘網絡中的社區(qū)結構可以應用多種算法，但這些算法均有不足。比如以GN算法為代表的劃分算法耗時較長；以FN[4]算法為代表的模塊性優(yōu)化算法復雜度過高；標簽傳播算法速度雖快但不穩(wěn)定等。而蟻群算法由于采用了分布式正反饋并行計算機制，具有較強的魯棒性和穩(wěn)定性，自2007年被Liu等[5]首次用于挖掘社區(qū)聚類，進而求得社區(qū)結構以來，被頻繁地應用于社區(qū)發(fā)現領域，但也逐漸發(fā)現蟻群算法存在收斂速度慢，求解精度低的問題。

針對以上問題，He等[6]將蟻群算法與模擬退火及標簽傳播算法結合，提出了MABA算法。它以SABA作為子方法，通過優(yōu)化局部模塊度函數Q，在已獲得的網絡社區(qū)結構上構建一個上層網絡，再將SABA作用于新的上層網絡，如此迭代直到Q值不再增加為止。MABA雖然可以緩解模塊度優(yōu)化帶來的分辨率限制問題，但是算法求解精度較低。Chang等[7]把遺傳算法中染色體解的表達形式應用于蟻群算法，提出MACO算法。每只螞蟻跳躍地選擇出下一個要到達的點編號，以此填充解向量。該方法雖能得到較好的社區(qū)劃分結果，但是解碼步驟耗時嚴重。Mu等[8]對MACO算法進行改進并提出IACO算法。采用基于學習的策略盡可能減少探索階段的冗余計算，但是解碼耗時問題仍然沒有解決。Zhou等[9]提出了antBCO算法，該算法在每個節(jié)點上存儲一個標簽列表作為螞蟻移動的禁忌列表，并在標簽列表上執(zhí)行后處理操作，最終獲得重疊的社區(qū)結構，但是該算法收斂速度慢且時間復雜度高。李有紅等[10]提出ELPA-ACO算法挖掘重疊社區(qū)結構，該算法先應用標簽傳播算法獲得初始信息素和螞蟻初始位置，再結合多種屬性改進螞蟻轉移策略，但標簽傳播產生的初步社區(qū)個數決定最終社區(qū)個數，導致算法適應性較差，求解精度低。因此，上述算法雖有所改進，但仍存在求解精度低和收斂速度慢的問題。

為了使蟻群算法的求解精度和收斂速度得到進一步改善，本文提出一種基于標簽傳播的蟻群優(yōu)化算法(Ant Colony Optimization Algorithm Based on Label Propagation，BLP_ACO)。首先，該算法提出一種新的解向量表達方式，蟻群的任務是通過確定節(jié)點標簽來構造解向量。在解的構造階段提出基于節(jié)點凝聚性的螞蟻轉移策略，降低螞蟻轉移過程中的隨機性，提高算法的求解精度。為使算法快速收斂，將標簽傳播思想引入到蟻群搜索過程，提出一種基于局部社區(qū)規(guī)模和社區(qū)相似性偏向的螞蟻定標策略，結合信息素和啟發(fā)式信息，綜合確定節(jié)點標簽。在解的優(yōu)化階段采用基于模塊度優(yōu)化的合并策略，進一步改善解的質量。最后，更新信息素時在社區(qū)內部的所有邊上滯留信息素。

1 傳統(tǒng)蟻群算法

傳統(tǒng)蟻群算法用一維向量來存儲解，向量中存放的元素是索引值對應節(jié)點的同社區(qū)節(jié)點編號。在蟻群的搜索過程中，隨機遍歷網絡，依據概率公式確定與螞蟻當前所在節(jié)點屬于同一社區(qū)的節(jié)點，并構造解向量。設節(jié)點i和節(jié)點j是網絡中的兩個節(jié)點，螞蟻從節(jié)點i轉移到節(jié)點j的概率公式如下所示：

(1)

式中：vi、vj代表節(jié)點i、節(jié)點j，N(i)代表節(jié)點i的鄰居節(jié)點集，τij(ηij)代表節(jié)點i與節(jié)點j之間的信息素(啟發(fā)式信息)。參數α和β分別為信息素和啟發(fā)式信息的相對重要程度。在蟻群完成一次迭代之后，模仿自然界中信息素揮發(fā)和釋放過程，先對網絡中的信息素減少一定比例，再對當次迭代產生最優(yōu)解的螞蟻走過的路徑滯留信息素，指導后續(xù)螞蟻的行動，體現蟻群算法的正反饋特性[11]。蟻群產生的所有解向量構成解空間，算法最終輸出解空間中的最優(yōu)解。信息素更新過程定義如下：

τij=ρτij+Δτij

(2)

式中：ρ是一個常數，ρ∈(0,1)，1-ρ代表信息素的揮發(fā)率，Δτij為要在節(jié)點i和節(jié)點j之間邊上滯留的信息素。

但是，傳統(tǒng)蟻群算法的解碼效率低，螞蟻僅依據兩個節(jié)點的相似度來構造解向量，導致算法求解精度低、收斂速度慢，更新信息素時僅在螞蟻走過的少數邊上滯留信息素，在一定程度上限制了蟻群的搜索空間?；谝陨蠋c不足，本文提出了基于標簽傳播的蟻群優(yōu)化算法。

2 基于標簽傳播的蟻群優(yōu)化算法

BLP_ACO與傳統(tǒng)蟻群算法的不同主要體現在三個方面：首先，解的表達形式不同。BLP_ACO所采用的解向量表達形式與傳統(tǒng)形式相比，解碼效率高。其次，解向量的構造過程不同。本文在構造階段提出了基節(jié)點凝聚性的螞蟻轉移策略和基于局部社區(qū)規(guī)模和社區(qū)相似性偏向的螞蟻定標策略，提高算法的求解精度，使得算法快速收斂。再次，在解的優(yōu)化階段采用基于模塊度優(yōu)化的合并策略，進一步提高算法精度。最后，信息素更新策略不同。BLP_ACO在社區(qū)內部的所有邊上都滯留信息素，擴大蟻群的搜索空間。

2.1 解向量的表示

目前已有蟻群算法采用的解向量，需要經過復雜度高的深度優(yōu)先或廣度優(yōu)先搜索來解碼，才能得到最終社區(qū)劃分。本著高效易操作的原則，BLP_ACO也采用一維數組來存儲解向量，向量中的元素表示索引值節(jié)點所屬社區(qū)的標簽。兩種表達形式對比如圖1所示。

圖1 網絡示例圖及解向量表示

圖1(a)所示網絡中包含8個節(jié)點，明顯劃分為{1,2,3,4}、{5,6,7,8}兩個子社區(qū)。圖1(b)代表傳統(tǒng)蟻群算法的初始解向量，算法初期設每個節(jié)點屬于不同社區(qū)，因此向量中的元素都用0填充。經過蟻群搜索完成解向量的構造，輸出形式如圖1(c)所示，設索引值從1開始，并與元素值一一對應，即：節(jié)點1與節(jié)點2屬于同一社區(qū)，節(jié)點2與節(jié)點3屬于同一社區(qū)，以此類推。若要得到最終社區(qū)劃分結果，還需通過深度優(yōu)先或廣度優(yōu)先搜索對解向量進行解碼，時間復雜度為O(n2)，當問題規(guī)模較大時，解碼步驟需耗費大量時間。

為了提高解碼效率，BLP_ACO在解向量中存放的元素，表示索引值對應節(jié)點所屬社區(qū)的標簽，如圖1(d)所示。算法初始化每個節(jié)點一個唯一標簽，設向量索引值從1開始。圖1(c)表示算法的輸出解向量，只需遍歷一次解向量，依據元素值對節(jié)點進行分組，就可得到社區(qū)劃分結果，時間復雜度僅為O(n)，與傳統(tǒng)表達形式相比，有效提高了解碼效率。

2.2 解向量的構造

傳統(tǒng)蟻群算法收斂速度慢導致耗時嚴重的問題亟待解決，而Symeon[12]比較了17種常見社區(qū)檢測算法的復雜度和適應社區(qū)規(guī)模的大小，發(fā)現標簽傳播算法(LPA)具有線性時間復雜度，同時實驗證明LPA在5次迭代更新標簽之后開始收斂，此時有至少95%的節(jié)點都劃分到正確社區(qū)[10]。因此BLP_ACO引入標簽傳播思想，提出一種基于節(jié)點凝聚性的螞蟻轉移策略和基于局部社區(qū)規(guī)模和社區(qū)相似性偏向的螞蟻定標策略。同時應用標簽傳播機制和蟻群算法的正反饋機制共同指導螞蟻的搜索行為，使每只螞蟻在構造解的過程中，也對網絡中的節(jié)點迭代確定5次標簽，以改善算法的收斂速度，提高算法的效率和精度。

2.2.1基于節(jié)點凝聚性的螞蟻轉移策略

由于引入的標簽傳播機制自身具有隨機性，會導致算法精度不高。為了避免這一現象，本文提出了基于節(jié)點凝聚性的螞蟻轉移策略，將網絡中的所有節(jié)點按照節(jié)點凝聚性度量值升序排序，作為螞蟻的轉移順序。相關定義如下所示：

定義1節(jié)點吸引力。節(jié)點i的吸引力定義如下：

(3)

式中：di表示節(jié)點i的度數，N是網絡中的節(jié)點總數。節(jié)點吸引力的取值范圍是[0,1)。當節(jié)點i是獨立節(jié)點或者網絡中只有一個節(jié)點時，該節(jié)點吸引力值為0；當節(jié)點i與網絡中其余各點都有邊連接時，該節(jié)點吸引力值趨于1。

定義2聚類系數。節(jié)點i的聚類系數定義如下：

(4)

式中：Ki表示節(jié)點i的鄰居節(jié)點數，Ei表示網絡中真實存在于節(jié)點i的所有鄰居節(jié)點之間的鏈接數，分母部分則表示節(jié)點i的所有鄰居節(jié)點之間所有可能的鏈接數的2倍。聚類系數的取值范圍是[0,1]，當節(jié)點的度數為0、1或其鄰居節(jié)點之間互不相連時，該值為0；當節(jié)點與其鄰居節(jié)點之間構成完全圖時，該值為1。

定義3節(jié)點凝聚性度量。節(jié)點i的凝聚性度量定義如下：

ψi=ATi×Ci

(5)

式中：ATi表示節(jié)點吸引力，Ci表示聚類系數。節(jié)點凝聚性度量值表示為節(jié)點吸引力和聚類系數的乘積，其中節(jié)點吸引力保證了凝聚性強的節(jié)點度數相對較大，因此處于大規(guī)模社區(qū)的可能性較大。聚類系數保證了該節(jié)點所屬社區(qū)的內部連接比較緊密，二者綜合決定節(jié)點凝聚性，ψi的值越大，表明節(jié)點i在網絡中的凝聚性越強。

表1 隨機轉移策略

為了說明基于節(jié)點凝聚性的螞蟻轉移策略能降低蟻群轉移過程中的隨機性，提高算法精度，本文在不考慮信息素的前提下，在圖1(a)所示的網絡示例圖中進行實驗對比。本次實驗使蟻群分別采用隨機轉移策略和基于節(jié)點凝聚性的轉移策略，為其當前所在節(jié)點選擇其鄰居節(jié)點中攜帶個數最多的標簽，當此類標簽存在多個時，則任選其一，直到網絡中的所有節(jié)點都滿足這個條件為止。本實驗中的社區(qū)標簽用{A,B,C,D,E,F,G,H}表示。當蟻群采用隨機轉移策略時，螞蟻轉移順序可以為{2,1,4,3,6,7,8,5}，詳細信息如表1所示。在第①步，每個節(jié)點都被初始化一個唯一標簽，分別為{A,B,C,D,E,F,G,H}；在第②步，確定節(jié)點2的標簽，此時節(jié)點2選取了節(jié)點5的E標簽。依次類推(表中斜體加粗的標簽表示當前步驟為節(jié)點確定的新標簽)，當算法執(zhí)行完畢時，所有節(jié)點都被劃分為一個社區(qū)，顯然這是一種無效劃分。

依據式(5)可以計算出，節(jié)點2和節(jié)點5的凝聚性度量值均為0.286，節(jié)點1、3、4、6、7、8的凝聚性度量均為0.429，將所有節(jié)點按照凝聚性度量值升序排列，得到螞蟻的轉移順序為{2,5,1,3,4,6,7,8}，螞蟻按照此順序為節(jié)點確定標簽，結果如表2所示。當算法執(zhí)行完畢時，得到兩個社區(qū)，產生正確的劃分結果。

表2 基于節(jié)點凝聚性的轉移策略

2.2.2基于局部社區(qū)規(guī)模和社區(qū)相似性偏向的螞蟻定標策略

螞蟻按照基于節(jié)點凝聚性的轉移策略在網絡中移動，并通過為節(jié)點確定標簽來構造解向量。為了使引入的標簽傳播機制和蟻群算法的正反饋機制能有機結合，本文提出一種基于局部社區(qū)規(guī)模和社區(qū)相似性偏向的螞蟻定標策略。螞蟻為節(jié)點i確定標簽m的概率公式定義如下：

(6)

式中：n和m代表節(jié)點標簽，α和β為信息素和啟發(fā)式信息的相對重要程度，τim是節(jié)點i與所有攜帶m標簽的鄰居節(jié)點之間邊上的信息素含量總和；ηim是節(jié)點i與所有攜帶m標簽的鄰居節(jié)點之間的啟發(fā)式信息總和；NLi是節(jié)點i的候選標簽集，存放節(jié)點i的所有鄰居節(jié)點攜帶的標簽種類。

(1) 信息素。信息素τ是螞蟻實現間接通信、完成群體協(xié)作的重要媒介[13]。BLP_ACO將信息素放置在邊上，并被初始化相同含量。隨著蟻群迭代次數的增加，信息素分布越來越不均勻，對后續(xù)螞蟻構造解向量起的指導作用也越來越強。式(6)中信息素τim的計算方式定義如下：

(7)

式中：Ni代表節(jié)點i的鄰居節(jié)點集；label(j)代表節(jié)點j所屬社區(qū)的標簽；τij為分布在節(jié)點i與節(jié)點j之間邊上的信息素含量。

(2) 啟發(fā)式信息。啟發(fā)式信息η是蟻群在搜索過程中使用的先驗性因素，用于輔助蟻群快速準確地作出判斷。BLP_ACO中啟發(fā)式信息的核心內容為節(jié)點間的相似度。“社區(qū)”沒有精準定義，只是社區(qū)內部節(jié)點的相似度要強于社區(qū)之間節(jié)點的相似度。類比于社交網絡中，兩個個體相似度高，不僅指這兩個個體共同朋友多，也說明共同陌生人多。因此，本文采用綜合考慮二者的皮爾遜相關系數[14]來衡量節(jié)點的相似度。兩節(jié)點的皮爾遜相關系數定義如下：

(8)

(9)

式中：Ni表示節(jié)點i的鄰居節(jié)點集；label(j)表示節(jié)點j所屬社區(qū)的標簽；C(i,j)表示皮爾遜相關系數。

綜上所述，螞蟻在衡量某標簽被選擇的概率時，不僅通過信息素借鑒了之前螞蟻產生的優(yōu)質解，也通過啟發(fā)式信息衡量了待定標節(jié)點與所有攜帶該標簽的鄰居節(jié)點構成的局部社區(qū)之間的相似度。同時，信息素與啟發(fā)式信息的求和操作體現了攜帶該標簽的局部社區(qū)規(guī)模，改善了算法的收斂速度和精度。

2.3 解向量的優(yōu)化

蟻群按照上述轉移策略和定標策略，已經可以獲得相對較好的社區(qū)劃分結果，但是為了進一步提高算法的求解精度，借鑒FN算法的思想，提出了基于模塊度優(yōu)化的合并策略。

BLP_ACO在蟻群完成每次迭代之后，采用基于模塊度優(yōu)化的合并策略，對當次迭代產生的最優(yōu)解進行優(yōu)化。本文將FN算法分別應用于社區(qū)發(fā)現領域常用的4種數據集，通過實驗觀察FN算法的特性。模塊度伴隨社區(qū)合并次數增加的變化曲線如圖2所示。

圖2 模塊度變化趨勢

圖2中各橫軸表示社區(qū)合并次數，縱軸表示模塊度的值。算法每次合并使模塊度增量最大或者減小最少的兩個社區(qū)，隨著社區(qū)合并次數的增加，模塊度從一個負值逐漸增至最高點，又在后期合并至一個社區(qū)的過程中迅速降至最低點，曲線在達到峰值之前一直呈現上升趨勢，且只有一個峰值。由于BLP_ACO旨在尋找最優(yōu)社區(qū)劃分，經上述分析，優(yōu)化階段只需要執(zhí)行合并操作至模塊度達到最大時結束，這樣能減少不必要的合并操作，進一步提高算法效率和求解精度。

2.4 信息素更新策略

由于BLP_ACO中蟻群的任務不再是為當前節(jié)點選擇同社區(qū)節(jié)點，而是為節(jié)點確定標簽，信息素應用于標簽的選擇。因此本文將信息素更新策略調整為：在蟻群完成每次迭代之后，運用式(2)更新網絡中的信息素，先對網絡中的信息素揮發(fā)一定比例，再尋找當次迭代產生的最優(yōu)社區(qū)劃分，在社區(qū)內部的所有邊上滯留信息素。BLP_ACO將本次迭代產生的最優(yōu)解對應的模塊度作為信息素的滯留量。定義如下：

(10)

式中：Q()是模塊度函數[15]；L_best代表蟻群本次迭代產生的最優(yōu)解。

為了證明信息素對后續(xù)蟻群的指導作用，本文仍在圖2中的數據集上進行實驗。在數據集的社區(qū)劃分結果中，分別統(tǒng)計社區(qū)內部邊上信息素的平均含量與社區(qū)間邊上信息素的平均含量，對比結果如圖3所示。

圖3 社區(qū)內部與社區(qū)間邊上信息素平均值對比

圖3顯示了BLP_ACO在各數據集上求得近似最優(yōu)社區(qū)劃分時的信息素分布柱狀圖。橫軸表示社區(qū)(其中最后一個表示社區(qū)間)，縱軸表示邊上信息素含量的平均值。從圖中易看出，不同數據集各社區(qū)內部邊上信息素的平均含量基本相當，且明顯高于社區(qū)之間邊上信息素的平均含量。因此，BLP_ACO中的信息素有效指導了螞蟻搜索近似最優(yōu)解的過程。

3 算法流程與復雜度分析

3.1 算法流程

算法偽代碼如下：

Input: G(V,E) /*輸入鄰接矩陣A和算法相關參數*/

Output: 社區(qū)劃分結果

1. 初始化算法相關參數和解向量；

2. 初始化NodeCoherencyList為空；

/*節(jié)點凝聚性度量值列表*/

3. 初始化updat_order為空

/*蟻群轉移路徑列表*/

4. For each v∈V do

5. 運用式(3)-式(5)填充NodeCoherencyList；

6. 對NodeCoherencyList升序排序，將對應節(jié)點編號填充updat_order；

7. For max_t do

/*蟻群迭代次數*/

8. For ant do

/*蟻群規(guī)模*/

9. t=0；

/* t為每只螞蟻的迭代次數*/

10. If t<5 do

/*每只螞蟻迭代定標5次*/

11. For i ∈ updat_order do

12. 初始化i_Candidate_coms列表為空；

/*存放當前節(jié)點的候選標簽集*/

13. 運用式(6)-式(9)計算每個標簽被選擇的概率；

14. 輪盤賭策略確定節(jié)點標簽；

15. End for

16. t++

17. End if

18. 運用式(11)計算模塊度；

19. End for

20. 優(yōu)化蟻群產生的局部最優(yōu)解，得到L_best；

21. 運用式(2)、式(10)依據L_best更新信息素；

22. End for

3.2 時間復雜度

設網絡節(jié)點數為n，邊數為m，節(jié)點平均度數為2m/n，蟻群迭代次數為max_t，蟻群規(guī)模為ant。BLP_ACO算法主要包括三部分：第一部分為計算節(jié)點凝聚性度量值，需要遍歷網絡中的所有節(jié)點以及每個節(jié)點的所有鄰居節(jié)點。因此第一部分的時間復雜度為節(jié)點數與節(jié)點平均度數的乘積，近似為O(m)。第二部分為蟻群構造解向量，首先遍歷網絡中的所有節(jié)點及其鄰居節(jié)點，通過計算確定節(jié)點標簽，這部分時間復雜度是O(max_t×ant×m)。其次是優(yōu)化階段，需要遍歷蟻群劃分的初步社區(qū)，時間復雜度是O(max_t×p2)，p是蟻群劃分的初步社區(qū)個數。因此第二部分的時間復雜度為O(max_t×(ant×m+p2))。第三部分是更新信息素，需要遍歷網絡中所有的邊，并檢測該邊的端點節(jié)點是否屬于同一社區(qū)。因此第三部分時間復雜度為O(maxt×m)。綜上所述，BLP_ACO的時間復雜度為O(max_t×(ant×m+p2))。

4 實驗結果與分析

為了檢測BLP_ACO算法在收斂速度和求解精度方面的性能，本文將BLP_ACO與MACO[7]、IACO[8]和SOCP_LPA[16]算法分別在6種真實網絡和LFR人工基準網絡上進行實驗對比。所有實驗算法均在Spyder工具中使用Python語言編程實現，實驗環(huán)境是：Window 7系統(tǒng)，Intel Core i5-3230M CPU @2.60 GHz，4 GB內存的PC機。

4.1 評估方法

4.1.1模塊度

模塊度是一種衡量社區(qū)劃分質量的量化指標。模塊度[15]的計算公式如下:

(11)

式中：Lc表示社區(qū)c內部的邊數，m表示網絡的邊數，Dc表示社區(qū)c內部節(jié)點的度數總和，L表示全部社區(qū)集合。Q值越接近于1，表示劃分結果越好，與真實網絡劃分越接近。

4.1.2歸一化互信息

歸一化互信息NMI[17]常作為評價指標應用于社區(qū)發(fā)現領域。在LFR人工基準網絡中，用NMI來衡量真實社區(qū)劃分與算法檢測到的社區(qū)劃分之間的相似度。計算公式如下：

(12)

式中：N代表LFR網絡中的節(jié)點總數，A代表網絡的標準分區(qū)，B代表算法求得的分區(qū)。CA(CB)代表A(B)種分區(qū)對應的社區(qū)總數。R是表示兩種分區(qū)相似程度的混合矩陣，矩陣元素Rij表示同時存在于A分區(qū)的社區(qū)i和B分區(qū)的社區(qū)j中的節(jié)點個數。Ri.表示矩陣R第i行元素的求和，R.j表示矩陣R第j列元素的求和。NMI(A,B)的取值范圍是[0,1]，當兩種分區(qū)完全相同時，取值為1。NMI取值越大，表示算法的求解精度越高。

4.2 數據集

4.2.1真實網絡

為了驗證BLP_ACO算法提高了求解精度，本文選取6種真實網絡用于實驗，這些真實網絡是社區(qū)發(fā)現領域常用的數據集，具體信息如表3所示。

表3 數據集介紹

4.2.2LFR人工基準網絡

Lancichinetti等[18]提出的LFR人工基準網絡是一種常用于社區(qū)發(fā)現研究中的模擬網絡。生成該網絡的算法可以調整參數，使得生成的人工基準網絡具有不同的規(guī)模和清晰度。LFR人工基準網絡的相關參數介紹如表4所示，其中混合參數mu是處于[0,1]之間的數，該數值越大，表明生成網絡的社區(qū)結構越不清晰，算法越難檢測出準確的社區(qū)結構。用于本次實驗的4組LFR網絡的詳細介紹如表5所示，其中每組對應15個mu值不同的網絡，mu的取值范圍是[0.1,0.8]。在相同節(jié)點數量的網絡500S(2000S)和500B(2000B)中，后者的每個社區(qū)中包含的節(jié)點數量相對較多。

表4 LFR人工基準網絡的相關參數

表5 LFR人工基準網絡描述

4.3 實驗結果對比

該算法設置螞蟻迭代次數max_t=10，螞蟻只數ant=10，概率選擇公式中信息素與啟發(fā)式信息的權重因子α=1、β=2，信息素滯留率ρ=0.8，信息素參照MMAS[19]的模型控制在[0.1,6.0]之間。

4.3.1真實網絡的模塊度對比

本文在表3中的數據集上應用4種算法，進行100次社區(qū)發(fā)現實驗，并對模塊度的平均值與最高值進行比較。對比結果如表6所示，其中每個網絡對應兩行數據，第一行是平均模塊度值，第二行是最高模塊度值，加粗斜體數據為每行的最優(yōu)值。由表6可知，BLP_ACO在前5種網絡都取得最好結果，尤其在karate和email網絡上明顯優(yōu)于其他算法。雖在較大規(guī)模的CA-GrQc網絡上沒有取得最優(yōu)值，但也僅次于最優(yōu)值，但與最優(yōu)相值差較少。因此，BLP_ACO算法具有較高的求解精度。

表6 模塊度對比

續(xù)表6

4.3.2LFR人工基準網絡的NMI對比

本次實驗在表5中的LFR人工基準網絡上應用4種算法，進行100次社區(qū)發(fā)現實驗，并對平均NMI值進行比較。對比結果如圖4所示，其中橫坐標表示不同清晰度的LFR網絡，縱坐標表示NMI值。由圖4中曲線的整體變化趨勢可知，mu值越大，社區(qū)結構越模糊，算法的求解精度也都明顯下降。

(a) 500S網絡的NMI對比

(b) 500B網絡的NMI對比

(c) 2000S網絡的NMI對比

(d) 2000B網絡的NMI對比圖4 LFR基準網絡上不同算法的NMI對比

由圖4(a)可知，mu取值在[0.1,0.3]時，4種算法都能挖掘出相對準確的社區(qū)結構；mu取值在[0.3,0.5]時，BLP_ACO與SOCP_LPA的NMI值不相上下，當mu的值大于0.6時，BLP_ACO的NMI值明顯高于其他算法。由圖4(b)可知，當mu的值在0.7和0.8之間時，BLP_ACO算法略低于SOCP_LPA，但在其他mu值對應的網絡上，均優(yōu)于其他算法。由圖4(c)可知，當mu值大于0.7時，MACO算法已經無法挖掘社區(qū)結構，IACO與SOCP_LPA算法對應的NMI值也明顯低于BLP_ACO。由圖4(d)可知，只有當mu值為0.55和0.8時，BLP_ACO的準確度略低于SOCP_LPA，在其他mu值對應的網絡上，BLP_ACO均明顯優(yōu)于其他算法。

4.3.3收斂速度對比

本文將模塊度函數作為目標函數，當函數值趨于穩(wěn)定時，算法達到收斂狀態(tài)。為了證明BLP_ACO與傳統(tǒng)蟻群算法相比，提高了收斂速度，本次實驗將BLP_ACO、MACO和IACO在4種網絡上進行社區(qū)發(fā)現，分別觀察模塊度隨蟻群迭代次數增長的變化趨勢和蟻群迭代10次的運行時間。為了保證實驗結果的科學性，3種算法中的相關參數取值均相同，算法在每個網絡上重復實驗100次，求得平均模塊度和平均運行時間。

模塊度增長如圖5所示，其中橫坐標表示蟻群迭代次數，縱坐標表示模塊度。

(a) Karate網絡的模塊度變化

(b) dolphins網絡的模塊度變化

(c) polbooks網絡的模塊度變化

(d) football網絡的模塊度變化圖5 算法在各網絡上的模塊度變化

由圖5可知，BLP_ACO在4種網絡上使蟻群迭代一次，產生的解均優(yōu)于另兩種算法；圖5(a)顯示在karate網絡上，3種算法幾乎都在蟻群第6次迭代時開始收斂，但是MACO與IACO收斂時的模塊度低于BLP_ACO；綜合觀察圖5(b)、圖5(c)和圖5(d)可知，BLP_ACO均在蟻群第3次迭代時開始收斂，另兩種算法達到收斂狀態(tài)時需要的蟻群迭代次數明顯多于BLP_ACO，且收斂時的模塊度低于BLP_ACO，尤其在polbooks和football網絡上相差較多。

運行時間對比如圖6所示，其中橫坐標表示網絡，縱坐標表示運行時間，單位為秒。

圖6 不同網絡上的運行時間對比

由圖6可知，BLP_ACO在不同網絡上的運行時間均明顯低于MACO與IACO，由于在polbooks和football網絡上，BLP_ACO分別需要1.69 s和2.08 s就運行完畢，而MACO由于其解碼步驟時間復雜度較高，在兩種數據集上的運行時間均超過100 s，IACO雖在MACO的基礎上做了改進，但是仍然沒有解決解碼效率低的問題，在這兩種網絡上的運行時間分別達到83.25 s和110.32 s，與BLP_ACO算法相差較大。因此，BLP_ACO不僅在算法達到收斂時需要的蟻群迭代次數少，而且算法運行時間短，與傳統(tǒng)蟻群算法相比，提高了收斂速度。

5 結 語

本文針對蟻群算法收斂速度慢和求解精度低的問題，提出一種基于標簽傳播的蟻群優(yōu)化算法。首先，該算法提出一種新的解向量表達方式，提高解碼效率。其次，在解的構造階段提出一種基于節(jié)點凝聚性的蟻群轉移策略，降低蟻群轉移過程中的隨機性，提高算法精度。為使算法快速收斂，提出一種基于局部社區(qū)規(guī)模和社區(qū)相似性偏向的螞蟻定標策略，結合標簽傳播思想和蟻群算法的正反饋特性，共同指導螞蟻為節(jié)點確定標簽。最后，在解的優(yōu)化階段提出基于模塊度優(yōu)化的合并策略，進一步改善算法的解。與目前效果較好的蟻群算法和改進的標簽傳播算法相比，BLP_ACO在收斂速度和求解精度方面均有明顯提升。