基于標簽傳播的蟻群優化算法求解社區發現問題

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

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

0 引 言

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

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

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

1 傳統蟻群算法

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

(1)

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

τij=ρτij+Δτij

(2)

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

但是，傳統蟻群算法的解碼效率低，螞蟻僅依據兩個節點的相似度來構造解向量，導致算法求解精度低、收斂速度慢，更新信息素時僅在螞蟻走過的少數邊上滯留信息素，在一定程度上限制了蟻群的搜索空間。基于以上幾點不足，本文提出了基于標簽傳播的蟻群優化算法。

2 基于標簽傳播的蟻群優化算法

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

2.1 解向量的表示

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

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

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

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

2.2 解向量的構造

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

2.2.1基于節點凝聚性的螞蟻轉移策略

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

定義1節點吸引力。節點i的吸引力定義如下：

(3)

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

定義2聚類系數。節點i的聚類系數定義如下：

(4)

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

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

ψi=ATi×Ci

(5)

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

表1 隨機轉移策略

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

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

表2 基于節點凝聚性的轉移策略

2.2.2基于局部社區規模和社區相似性偏向的螞蟻定標策略

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

(6)

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

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

(7)

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

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

(8)

(9)

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

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

2.3 解向量的優化

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

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

圖2 模塊度變化趨勢

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

2.4 信息素更新策略

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

(10)

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

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

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

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

3 算法流程與復雜度分析

3.1 算法流程

算法偽代碼如下：

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

Output: 社區劃分結果

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

2. 初始化NodeCoherencyList為空；

/*節點凝聚性度量值列表*/

3. 初始化updat_order為空

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

4. For each v∈V do

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

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

7. For max_t do

/*蟻群迭代次數*/

8. For ant do

/*蟻群規模*/

9. t=0；

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

10. If t<5 do

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

11. For i ∈ updat_order do

12. 初始化i_Candidate_coms列表為空；

/*存放當前節點的候選標簽集*/

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

14. 輪盤賭策略確定節點標簽；

15. End for

16. t++

17. End if

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

19. End for

20. 優化蟻群產生的局部最優解，得到L_best；

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

22. End for

3.2 時間復雜度

設網絡節點數為n，邊數為m，節點平均度數為2m/n，蟻群迭代次數為max_t，蟻群規模為ant。BLP_ACO算法主要包括三部分：第一部分為計算節點凝聚性度量值，需要遍歷網絡中的所有節點以及每個節點的所有鄰居節點。因此第一部分的時間復雜度為節點數與節點平均度數的乘積，近似為O(m)。第二部分為蟻群構造解向量，首先遍歷網絡中的所有節點及其鄰居節點，通過計算確定節點標簽，這部分時間復雜度是O(max_t×ant×m)。其次是優化階段，需要遍歷蟻群劃分的初步社區，時間復雜度是O(max_t×p2)，p是蟻群劃分的初步社區個數。因此第二部分的時間復雜度為O(max_t×(ant×m+p2))。第三部分是更新信息素，需要遍歷網絡中所有的邊，并檢測該邊的端點節點是否屬于同一社區。因此第三部分時間復雜度為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語言編程實現，實驗環境是：Window 7系統，Intel Core i5-3230M CPU @2.60 GHz，4 GB內存的PC機。

4.1 評估方法

4.1.1模塊度

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

(11)

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

4.1.2歸一化互信息

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

(12)

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

4.2 數據集

4.2.1真實網絡

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

表3 數據集介紹

4.2.2LFR人工基準網絡

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

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

表5 LFR人工基準網絡描述

4.3 實驗結果對比

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

4.3.1真實網絡的模塊度對比

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

表6 模塊度對比

續表6

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

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

(a) 500S網絡的NMI對比

(b) 500B網絡的NMI對比

(c) 2000S網絡的NMI對比

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

由圖4(a)可知，mu取值在[0.1,0.3]時，4種算法都能挖掘出相對準確的社區結構；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值對應的網絡上，均優于其他算法。由圖4(c)可知，當mu值大于0.7時，MACO算法已經無法挖掘社區結構，IACO與SOCP_LPA算法對應的NMI值也明顯低于BLP_ACO。由圖4(d)可知，只有當mu值為0.55和0.8時，BLP_ACO的準確度略低于SOCP_LPA，在其他mu值對應的網絡上，BLP_ACO均明顯優于其他算法。

4.3.3收斂速度對比

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

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

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

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

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

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

由圖5可知，BLP_ACO在4種網絡上使蟻群迭代一次，產生的解均優于另兩種算法；圖5(a)顯示在karate網絡上，3種算法幾乎都在蟻群第6次迭代時開始收斂，但是MACO與IACO收斂時的模塊度低于BLP_ACO；綜合觀察圖5(b)、圖5(c)和圖5(d)可知，BLP_ACO均在蟻群第3次迭代時開始收斂，另兩種算法達到收斂狀態時需要的蟻群迭代次數明顯多于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不僅在算法達到收斂時需要的蟻群迭代次數少，而且算法運行時間短，與傳統蟻群算法相比，提高了收斂速度。

5 結 語

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