基于標(biāo)簽傳播的蟻群優(yōu)化算法求解社區(qū)發(fā)現(xiàn)問(wèn)題

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

1(河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院 天津 300401)2(河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室 天津 300401)3(天津商業(yè)大學(xué)信息工程學(xué)院 天津 300314)

0 引 言

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

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

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

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

傳統(tǒng)蟻群算法用一維向量來(lái)存儲(chǔ)解，向量中存放的元素是索引值對(duì)應(yīng)節(jié)點(diǎn)的同社區(qū)節(jié)點(diǎn)編號(hào)。在蟻群的搜索過(guò)程中，隨機(jī)遍歷網(wǎng)絡(luò)，依據(jù)概率公式確定與螞蟻當(dāng)前所在節(jié)點(diǎn)屬于同一社區(qū)的節(jié)點(diǎn)，并構(gòu)造解向量。設(shè)節(jié)點(diǎn)i和節(jié)點(diǎn)j是網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)，螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率公式如下所示：

(1)

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

τij=ρτij+Δτij

(2)

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

但是，傳統(tǒng)蟻群算法的解碼效率低，螞蟻僅依據(jù)兩個(gè)節(jié)點(diǎn)的相似度來(lái)構(gòu)造解向量，導(dǎo)致算法求解精度低、收斂速度慢，更新信息素時(shí)僅在螞蟻?zhàn)哌^(guò)的少數(shù)邊上滯留信息素，在一定程度上限制了蟻群的搜索空間。基于以上幾點(diǎn)不足，本文提出了基于標(biāo)簽傳播的蟻群優(yōu)化算法。

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

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

2.1 解向量的表示

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

圖1 網(wǎng)絡(luò)示例圖及解向量表示

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

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

2.2 解向量的構(gòu)造

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

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

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

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

(3)

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

定義2聚類(lèi)系數(shù)。節(jié)點(diǎn)i的聚類(lèi)系數(shù)定義如下：

(4)

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

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

ψi=ATi×Ci

(5)

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

表1 隨機(jī)轉(zhuǎn)移策略

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

依據(jù)式(5)可以計(jì)算出，節(jié)點(diǎn)2和節(jié)點(diǎn)5的凝聚性度量值均為0.286，節(jié)點(diǎn)1、3、4、6、7、8的凝聚性度量均為0.429，將所有節(jié)點(diǎn)按照凝聚性度量值升序排列，得到螞蟻的轉(zhuǎn)移順序?yàn)閧2,5,1,3,4,6,7,8}，螞蟻按照此順序?yàn)楣?jié)點(diǎn)確定標(biāo)簽，結(jié)果如表2所示。當(dāng)算法執(zhí)行完畢時(shí)，得到兩個(gè)社區(qū)，產(chǎn)生正確的劃分結(jié)果。

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

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

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

(6)

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

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

(7)

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

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

(8)

(9)

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

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

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

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

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

圖2 模塊度變化趨勢(shì)

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

2.4 信息素更新策略

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

(10)

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

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

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

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

3 算法流程與復(fù)雜度分析

3.1 算法流程

算法偽代碼如下：

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

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

1. 初始化算法相關(guān)參數(shù)和解向量；

2. 初始化NodeCoherencyList為空；

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

3. 初始化updat_order為空

/*蟻群轉(zhuǎn)移路徑列表*/

4. For each v∈V do

5. 運(yùn)用式(3)-式(5)填充N(xiāo)odeCoherencyList；

6. 對(duì)NodeCoherencyList升序排序，將對(duì)應(yīng)節(jié)點(diǎn)編號(hào)填充updat_order；

7. For max_t do

/*蟻群迭代次數(shù)*/

8. For ant do

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

9. t=0；

/* t為每只螞蟻的迭代次數(shù)*/

10. If t<5 do

/*每只螞蟻迭代定標(biāo)5次*/

11. For i ∈ updat_order do

12. 初始化i_Candidate_coms列表為空；

/*存放當(dāng)前節(jié)點(diǎn)的候選標(biāo)簽集*/

13. 運(yùn)用式(6)-式(9)計(jì)算每個(gè)標(biāo)簽被選擇的概率；

14. 輪盤(pán)賭策略確定節(jié)點(diǎn)標(biāo)簽；

15. End for

16. t++

17. End if

18. 運(yùn)用式(11)計(jì)算模塊度；

19. End for

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

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

22. End for

3.2 時(shí)間復(fù)雜度

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 評(píng)估方法

4.1.1模塊度

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

(11)

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

4.1.2歸一化互信息

歸一化互信息NMI[17]常作為評(píng)價(jià)指標(biāo)應(yīng)用于社區(qū)發(fā)現(xiàn)領(lǐng)域。在LFR人工基準(zhǔn)網(wǎng)絡(luò)中，用NMI來(lái)衡量真實(shí)社區(qū)劃分與算法檢測(cè)到的社區(qū)劃分之間的相似度。計(jì)算公式如下：

(12)

式中：N代表LFR網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)，A代表網(wǎng)絡(luò)的標(biāo)準(zhǔn)分區(qū)，B代表算法求得的分區(qū)。CA(CB)代表A(B)種分區(qū)對(duì)應(yīng)的社區(qū)總數(shù)。R是表示兩種分區(qū)相似程度的混合矩陣，矩陣元素Rij表示同時(shí)存在于A分區(qū)的社區(qū)i和B分區(qū)的社區(qū)j中的節(jié)點(diǎn)個(gè)數(shù)。Ri.表示矩陣R第i行元素的求和，R.j表示矩陣R第j列元素的求和。NMI(A,B)的取值范圍是[0,1]，當(dāng)兩種分區(qū)完全相同時(shí)，取值為1。NMI取值越大，表示算法的求解精度越高。

4.2 數(shù)據(jù)集

4.2.1真實(shí)網(wǎng)絡(luò)

為了驗(yàn)證BLP_ACO算法提高了求解精度，本文選取6種真實(shí)網(wǎng)絡(luò)用于實(shí)驗(yàn)，這些真實(shí)網(wǎng)絡(luò)是社區(qū)發(fā)現(xiàn)領(lǐng)域常用的數(shù)據(jù)集，具體信息如表3所示。

表3 數(shù)據(jù)集介紹

4.2.2LFR人工基準(zhǔn)網(wǎng)絡(luò)

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

表4 LFR人工基準(zhǔn)網(wǎng)絡(luò)的相關(guān)參數(shù)

表5 LFR人工基準(zhǔn)網(wǎng)絡(luò)描述

4.3 實(shí)驗(yàn)結(jié)果對(duì)比

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

4.3.1真實(shí)網(wǎng)絡(luò)的模塊度對(duì)比

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

表6 模塊度對(duì)比

續(xù)表6

4.3.2LFR人工基準(zhǔn)網(wǎng)絡(luò)的NMI對(duì)比

本次實(shí)驗(yàn)在表5中的LFR人工基準(zhǔn)網(wǎng)絡(luò)上應(yīng)用4種算法，進(jìn)行100次社區(qū)發(fā)現(xiàn)實(shí)驗(yàn)，并對(duì)平均NMI值進(jìn)行比較。對(duì)比結(jié)果如圖4所示，其中橫坐標(biāo)表示不同清晰度的LFR網(wǎng)絡(luò)，縱坐標(biāo)表示NMI值。由圖4中曲線的整體變化趨勢(shì)可知，mu值越大，社區(qū)結(jié)構(gòu)越模糊，算法的求解精度也都明顯下降。

(a) 500S網(wǎng)絡(luò)的NMI對(duì)比

(b) 500B網(wǎng)絡(luò)的NMI對(duì)比

(c) 2000S網(wǎng)絡(luò)的NMI對(duì)比

(d) 2000B網(wǎng)絡(luò)的NMI對(duì)比圖4 LFR基準(zhǔn)網(wǎng)絡(luò)上不同算法的NMI對(duì)比

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

4.3.3收斂速度對(duì)比

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

模塊度增長(zhǎng)如圖5所示，其中橫坐標(biāo)表示蟻群迭代次數(shù)，縱坐標(biāo)表示模塊度。

(a) Karate網(wǎng)絡(luò)的模塊度變化

(b) dolphins網(wǎng)絡(luò)的模塊度變化

(c) polbooks網(wǎng)絡(luò)的模塊度變化

(d) football網(wǎng)絡(luò)的模塊度變化圖5 算法在各網(wǎng)絡(luò)上的模塊度變化

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

運(yùn)行時(shí)間對(duì)比如圖6所示，其中橫坐標(biāo)表示網(wǎng)絡(luò)，縱坐標(biāo)表示運(yùn)行時(shí)間，單位為秒。

圖6 不同網(wǎng)絡(luò)上的運(yùn)行時(shí)間對(duì)比

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

5 結(jié) 語(yǔ)

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