基于改進小生境粒子群的社區發現算法*

廣東茂名幼兒師范專科學校教育技術與網絡中心 張金霜 黃旭彬

社區發現對增加教育虛擬社區用戶粘性，提高學習者學習成效具有積極作用。為解決傳統社區發現算法在復雜網絡結構不清晰時劃分效果不佳的問題，提出一種基于小生境的二進制粒子群優化算法NIBPSO。算法將每個粒子編碼作為社區發現的一種解，以模塊度作為優化函數。在粒子迭代過程中，選取粒子的鄰域最優替代全局最優，同時根據粒子各維度的速度，采用輪盤賭算法確定粒子中各節點的社區歸屬。通過控制粒子信息傳播速度和范圍，能有效解決粒子陷入局部最優，提高了社區發現效果。實驗表明，該算法獲得較好的社區發現結果。

教育虛擬社區為學習者提供了一個開放的網絡學習空間，學習者在這里交流信息、探討問題、擴展思路、創新觀念、達成共識，充分發揮集體智慧。隨著人工智能和大數據技術的發展，精準教育逐步變成現實，教育虛擬社區作為精準教育的載體，在教學過程中發揮了重要作用。提升教育虛擬社區發現的效率和質量，有助于學習資源精準推送，促進學習者找到興趣相投的學習伙伴，增加學習者對教育虛擬社區的粘性。

現實生活中，許多復雜系統都被抽象成復雜網絡形式，如社交網絡、論文引文網絡、生物網絡等。復雜網絡內部可劃分為多個社區，社區內部的節點聯系更加緊密，而社區間關系較為稀疏。社區發現仍是目前復雜網絡研究熱點之一，社區劃分的好壞影響社區價值的挖掘。在研究初期，有學者將社區發現理解為圖分割問題、聚類問題等，提出了各種社區發現算法，比較有代表性的包括GN分裂算法、LPA標簽傳播算法、隨機游走算法、層次聚類算法、Fast Unfolding算法等。2003年Newman等人提出模塊度函數，用于評價社區劃分質量，此后不少學者將社區發現問題轉為目標優化問題，采用啟發式算法進行研究。遺傳算法、蟻群算法、蜂群算法等一系列仿生算法對于解決NP問題具有重要意義，其中粒子群優化算法就是一個典型的群仿生智能算法，對于解決這類優化問題有著較高的效率和準確性，廣泛應用于社區發現。

為進一步優化社區發現質量，解決粒子群算法收斂過快，容易陷入局部最優等問題，本文提出了基于小生境的二進制粒子群算法NIBPSO。該算法結合了輪盤賭和小生境兩種技術，可以有效地控制粒子的收斂速度，并保持粒子信息向下一代傳遞，更利于獲得全局最優解。仿真結果證明，該方法相較于傳統社區發現算法能獲得更好的模塊度值。

1 基于小生境粒子群優化算法

1.1 粒子群算法

粒子群優化算法PSO模擬鳥群覓食群體行為，將鳥群中每只鳥抽象為一個沒有重量和體積的粒子，每個粒子包含一個速度矢量，該矢量確定粒子的飛行方向和距離。粒子的位置信息代表搜索空間的一個解，通過待求解問題的目標函數，評價每個粒子當前解的好壞。

PSO算法對于求解組合優化問題具有良好的效果，具有模型設計簡單，控制參數較少，魯棒性好，運行速度快等優點，但存在收斂過程容易陷入局部最優的問題，因此需要結合具體研究內容，改進算法尋優過程，綜合利用PSO算法局部搜索和全局搜索能力。

基本PSO算法粒子的進化方程可描述為：

式中，x(t)是當前粒子位置；v(t)為粒子i第j維第t代的運動速度；C和C為加速度常數；r和r為[0,1]之間的隨機數；P(t)是粒子個體最優位置，P(t)是粒子群的全局最優位置。從式(1)和式(2)可以看出，粒子參考個體最優和全局最優，對其速度和位置進行更新，使得粒子最終向個體最優和全局最優靠攏，以達到最優解。

1.2 目標函數

對于社區劃分結果的評價，通常面臨兩種情況，一種是已知真實的劃分結果，然后將算法發現的結果與真實結果相比較，這種情況下可采用互信息量（NMI）值進行評價；另一種更常見的情況是不確定真實的劃分結果，沒有任何先驗知識，這種情況下需要根據各社區節點連接情況作出評價，比較著名的評價指標是模塊度（Modularity）。模塊度函數是一種用于評估社區劃分好壞的目標函數，其基本思想是比較社區劃分中，社區內部關聯的稠密程度與隨機網絡的稠密程度。公式為：

式中，

A

是整個網絡對應的鄰接矩陣的元素。如節點i和j有連接，則

A=1

，否則

A=0

；

δ

(

C

,

C

)函數定義為如果i和j屬于一個社區，即

C=C

，則取值為1，否則為0；m是網絡中邊的總數。模塊度Q取值范圍在0到1之間，取值越大說明社區劃分效果越好。

1.3 二進制粒子群編碼

標準PSO算法是針對連續優化問題而提出的，而社區發現問題的實質是確定網絡各節點所屬社區，即尋找一種最優節點歸屬組合，因此本文采用二進制粒子群算法BPSO，粒子編碼采用吳朝恬提出的方案。

設網絡節點數

M

，若網絡劃分為N個社區，則粒子所需編碼位置空間為

M*N

。每個節點用二進制編碼表示，長度為N，例如編碼“010”，表示共有3個社區，且該節點歸屬2號社區。這種編碼方式可以直觀地確定每個節點所屬社區，并且每個粒子代表一種社區發現結果，但缺點是需事先定義社區數量，占用空間隨社區數量變化。

在粒子初始化階段，為保證解的多樣性，可采用等概率輪盤賭算法隨機生成粒子中各節點歸屬取值。

在粒子位置更新階段，由于每次計算時，粒子各維度的結果不會正好是0或1，因此需要對結果進行修正。首先對數據進行歸一化處理，然后根據歸一化結果判定節點所屬社區，可采用兩種判定方式：一種是選擇維度取值最大的對應位置，作為節點所屬社區結果；另一種是繼續采用輪盤賭算法，根據各維度取值的大小，決定選中該維度的概率。維度選定后，該維度對應位置編碼設置為1，其他維度對應位置編碼設置為0。本文采用基于速度維度概率的輪盤賭算法，這種處理方式能更大程度上保持粒子信息向下一代傳遞。

1.4 基于小生境的粒子群算法

小生境（Niche）是來自生物學的一個概念，指的是生物總是與自己相同的物種生活在一起，這些生物賴以生存的環境資源稱為小生境。

在基本PSO算法中，粒子通過全局最優解直接作用于信息更新，在這個過程容易出現因信息傳播過快，導致算法陷入局部最優。為克服這個問題，本文借用小生境思想，對粒子更新策略做如下調整：每個粒子僅與其相鄰的k個粒子進行直接交互，而與其他粒子做間接交互。修改后的PSO算法進化方程如下：

由式(4)可知，原式(1)中的P(t)被替換成了P(t)，P(t)表示與粒子i相鄰的k個粒子中的最優解，k值決定了小生境的范圍。通過這樣的機制減緩粒子信息傳播的速度，有效防止粒子群算法過早收斂，同時也允許不同鄰域的最優共存。隨著迭代進行，粒子會向不同的區域聚集，形成各個小生境。迭代完成后，P(t)形成的群體會趨于穩定，最終得到全局最優解。

1.5 NIBPSO算法流程

NIBPSO算法求解社區發問題的流程如圖1所示。

圖1 NIBPSO算法流程Fig.1 NIBPSO algorithm flow

2 實驗分析

2.1 實驗數據集

實驗采用了Karate、Dolphin、Football三組經典的網絡數據集。其中Karate網絡包含了34個節點和78條邊，Dolphin網絡包含了62個節點和159條邊，Football網絡包含了115個節點和616條邊。

2.2 實驗結果

為了驗證NIBPSO算法的有效性，本文將NIBPSO算法與傳統GN、LPA算法進行對比，實現非重疊社區發現，得到的模塊度Q值如圖2所示。

圖2 各算法在3個社區網絡測得的模塊度值Fig.2 Modularity values measured by each algorithm in 3 community networks

由圖2可以看出，基于小生境技術的粒子群NIBPSO算法相較于傳統的GN、LPA算法在三個真實網絡上獲得更好的模塊度Q值，說明該算法是有效的，在解決社區發現問題上發揮了更好的尋優作用。

3 結語

為優化社區發現，本文以模塊度為目標函數，結合輪盤賭和小生境兩種手段，提出一種NIBPSO優化算法。該算法無需小生境參數的先驗知識，并能有效提高粒子群收斂精度。仿真實驗結果表明，NIBPSO獲得了更好的模塊度值，社區發現效果較好。