基于改進(jìn)小生境粒子群的社區(qū)發(fā)現(xiàn)算法*

廣東茂名幼兒師范專科學(xué)校教育技術(shù)與網(wǎng)絡(luò)中心 張金霜 黃旭彬

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

教育虛擬社區(qū)為學(xué)習(xí)者提供了一個(gè)開放的網(wǎng)絡(luò)學(xué)習(xí)空間，學(xué)習(xí)者在這里交流信息、探討問題、擴(kuò)展思路、創(chuàng)新觀念、達(dá)成共識，充分發(fā)揮集體智慧。隨著人工智能和大數(shù)據(jù)技術(shù)的發(fā)展，精準(zhǔn)教育逐步變成現(xiàn)實(shí)，教育虛擬社區(qū)作為精準(zhǔn)教育的載體，在教學(xué)過程中發(fā)揮了重要作用。提升教育虛擬社區(qū)發(fā)現(xiàn)的效率和質(zhì)量，有助于學(xué)習(xí)資源精準(zhǔn)推送，促進(jìn)學(xué)習(xí)者找到興趣相投的學(xué)習(xí)伙伴，增加學(xué)習(xí)者對教育虛擬社區(qū)的粘性。

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

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

1 基于小生境粒子群優(yōu)化算法

1.1 粒子群算法

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

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

基本PSO算法粒子的進(jìn)化方程可描述為：

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

1.2 目標(biāo)函數(shù)

對于社區(qū)劃分結(jié)果的評價(jià)，通常面臨兩種情況，一種是已知真實(shí)的劃分結(jié)果，然后將算法發(fā)現(xiàn)的結(jié)果與真實(shí)結(jié)果相比較，這種情況下可采用互信息量（NMI）值進(jìn)行評價(jià)；另一種更常見的情況是不確定真實(shí)的劃分結(jié)果，沒有任何先驗(yàn)知識，這種情況下需要根據(jù)各社區(qū)節(jié)點(diǎn)連接情況作出評價(jià)，比較著名的評價(jià)指標(biāo)是模塊度（Modularity）。模塊度函數(shù)是一種用于評估社區(qū)劃分好壞的目標(biāo)函數(shù)，其基本思想是比較社區(qū)劃分中，社區(qū)內(nèi)部關(guān)聯(lián)的稠密程度與隨機(jī)網(wǎng)絡(luò)的稠密程度。公式為：

式中，

A

是整個(gè)網(wǎng)絡(luò)對應(yīng)的鄰接矩陣的元素。如節(jié)點(diǎn)i和j有連接，則

A=1

，否則

A=0

；

δ

(

C

,

C

)函數(shù)定義為如果i和j屬于一個(gè)社區(qū)，即

C=C

，則取值為1，否則為0；m是網(wǎng)絡(luò)中邊的總數(shù)。模塊度Q取值范圍在0到1之間，取值越大說明社區(qū)劃分效果越好。

1.3 二進(jìn)制粒子群編碼

標(biāo)準(zhǔn)PSO算法是針對連續(xù)優(yōu)化問題而提出的，而社區(qū)發(fā)現(xiàn)問題的實(shí)質(zhì)是確定網(wǎng)絡(luò)各節(jié)點(diǎn)所屬社區(qū)，即尋找一種最優(yōu)節(jié)點(diǎn)歸屬組合，因此本文采用二進(jìn)制粒子群算法BPSO，粒子編碼采用吳朝恬提出的方案。

設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)

M

，若網(wǎng)絡(luò)劃分為N個(gè)社區(qū)，則粒子所需編碼位置空間為

M*N

。每個(gè)節(jié)點(diǎn)用二進(jìn)制編碼表示，長度為N，例如編碼“010”，表示共有3個(gè)社區(qū)，且該節(jié)點(diǎn)歸屬2號社區(qū)。這種編碼方式可以直觀地確定每個(gè)節(jié)點(diǎn)所屬社區(qū)，并且每個(gè)粒子代表一種社區(qū)發(fā)現(xiàn)結(jié)果，但缺點(diǎn)是需事先定義社區(qū)數(shù)量，占用空間隨社區(qū)數(shù)量變化。

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

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

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

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

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

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

1.5 NIBPSO算法流程

NIBPSO算法求解社區(qū)發(fā)問題的流程如圖1所示。

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

2 實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用了Karate、Dolphin、Football三組經(jīng)典的網(wǎng)絡(luò)數(shù)據(jù)集。其中Karate網(wǎng)絡(luò)包含了34個(gè)節(jié)點(diǎn)和78條邊，Dolphin網(wǎng)絡(luò)包含了62個(gè)節(jié)點(diǎn)和159條邊，F(xiàn)ootball網(wǎng)絡(luò)包含了115個(gè)節(jié)點(diǎn)和616條邊。

2.2 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證NIBPSO算法的有效性，本文將NIBPSO算法與傳統(tǒng)GN、LPA算法進(jìn)行對比，實(shí)現(xiàn)非重疊社區(qū)發(fā)現(xiàn)，得到的模塊度Q值如圖2所示。

圖2 各算法在3個(gè)社區(qū)網(wǎng)絡(luò)測得的模塊度值Fig.2 Modularity values measured by each algorithm in 3 community networks

由圖2可以看出，基于小生境技術(shù)的粒子群NIBPSO算法相較于傳統(tǒng)的GN、LPA算法在三個(gè)真實(shí)網(wǎng)絡(luò)上獲得更好的模塊度Q值，說明該算法是有效的，在解決社區(qū)發(fā)現(xiàn)問題上發(fā)揮了更好的尋優(yōu)作用。

3 結(jié)語

為優(yōu)化社區(qū)發(fā)現(xiàn)，本文以模塊度為目標(biāo)函數(shù)，結(jié)合輪盤賭和小生境兩種手段，提出一種NIBPSO優(yōu)化算法。該算法無需小生境參數(shù)的先驗(yàn)知識，并能有效提高粒子群收斂精度。仿真實(shí)驗(yàn)結(jié)果表明，NIBPSO獲得了更好的模塊度值，社區(qū)發(fā)現(xiàn)效果較好。