基于遺傳算法的大規(guī)模社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

陳永建，周 艷,2，劉超英

(1.肇慶學(xué)院 計(jì)算機(jī)科學(xué)與軟件學(xué)院、大數(shù)據(jù)學(xué)院，廣東 肇慶 526061； 2.西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，陜西 西安 710129)

0 引 言

在社交網(wǎng)絡(luò)中，社區(qū)是一個(gè)重要的結(jié)構(gòu)，社區(qū)內(nèi)的節(jié)點(diǎn)互相具有大量的連接，社區(qū)間的節(jié)點(diǎn)則僅有少量的連接[1-3]。搜索社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)能夠有助于預(yù)測(cè)網(wǎng)絡(luò)的行為、分析網(wǎng)絡(luò)的功能，目前社區(qū)發(fā)現(xiàn)問(wèn)題已經(jīng)成為社交網(wǎng)絡(luò)的研究重點(diǎn)。對(duì)于大規(guī)模社交網(wǎng)絡(luò)，社區(qū)的數(shù)量極大并且社區(qū)之間的連接也較為復(fù)雜，這為大規(guī)模社交網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)算法的準(zhǔn)確率與計(jì)算效率帶來(lái)了困難[4]。

許多研究人員已經(jīng)提出了大量的方案來(lái)解決社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問(wèn)題，其中一部分算法基于網(wǎng)絡(luò)的統(tǒng)計(jì)分析與聚類分析檢測(cè)出連接密集的節(jié)點(diǎn)集合[5]，但這些算法往往需要一些網(wǎng)絡(luò)的先驗(yàn)信息，例如：社區(qū)數(shù)量、網(wǎng)絡(luò)中社區(qū)是否重疊、社區(qū)規(guī)模等等[6]，而這些先驗(yàn)信息在實(shí)際應(yīng)用中往往難以預(yù)知。文獻(xiàn)[7]設(shè)計(jì)了定量描述社區(qū)結(jié)構(gòu)的模塊性Q函數(shù)，隨之出現(xiàn)許多元啟發(fā)式算法將Q函數(shù)作為目標(biāo)函數(shù)，從而檢測(cè)出網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，這些元啟發(fā)式算法包括：模擬退火算法[8]、種群智能算法[9]、遺傳算法與演化算法[10]等。遺傳算法具有較強(qiáng)的全局尋優(yōu)能力，因此將遺傳算法應(yīng)用于社區(qū)發(fā)現(xiàn)問(wèn)題得到了最為廣泛的研究，并且也獲得了較好的效果。文獻(xiàn)[11]為遺傳算法引入了多維染色體與均勻塊交叉算子，能夠較好地刻畫(huà)社區(qū)重疊部分的節(jié)點(diǎn)，但該算法對(duì)于社區(qū)重疊的社交網(wǎng)絡(luò)具好較好的性能，而對(duì)于社區(qū)不重疊的社交網(wǎng)絡(luò)并未表現(xiàn)出優(yōu)勢(shì)。文獻(xiàn)[12]為遺傳算法引入了免疫機(jī)制，該機(jī)制能夠保證種群的多樣性，并且設(shè)計(jì)了新的染色體編碼方案，有效地縮小了種群的搜索空間。文獻(xiàn)[13]為了解決遺傳算法易于陷入局部最優(yōu)與缺乏穩(wěn)定性的問(wèn)題，設(shè)計(jì)了基于網(wǎng)絡(luò)局部信息的節(jié)點(diǎn)-社區(qū)隸屬度機(jī)制，該機(jī)制能夠有效地縮小初始化種群的搜索空間，但該算法的隸屬度機(jī)制主要考慮了社區(qū)內(nèi)部的隸屬度。文獻(xiàn)[14]為遺傳算法引入了強(qiáng)化學(xué)習(xí)機(jī)制，將agent編碼為網(wǎng)絡(luò)的一個(gè)劃分方案，并且設(shè)計(jì)了一系列新的遺傳算子，包括：鄰居節(jié)點(diǎn)競(jìng)爭(zhēng)算子、混合鄰居節(jié)點(diǎn)交叉算子、自適應(yīng)變異算子與自學(xué)習(xí)算子。上述算法對(duì)于遺傳算法的改進(jìn)主要關(guān)注于遺傳算法的種群多樣性、收斂速度以及初始化種群的搜索空間，但如果預(yù)測(cè)出大規(guī)模社交網(wǎng)絡(luò)的社區(qū)數(shù)量，能夠極大地縮小初始化種群的搜索空間，并且能夠提高種群演化的準(zhǔn)確性。

當(dāng)前的社交網(wǎng)絡(luò)中普遍存在社區(qū)重疊的現(xiàn)象，因此許多社區(qū)發(fā)現(xiàn)算法在計(jì)算節(jié)點(diǎn)與社區(qū)隸屬度的過(guò)程中，將重疊社區(qū)作為先驗(yàn)知識(shí)，這類算法[11]無(wú)法適用于非重疊社區(qū)的社交網(wǎng)絡(luò)。本文設(shè)計(jì)了一種基于遺傳算法的社區(qū)發(fā)現(xiàn)算法，采用遺傳算法搜索Q函數(shù)的最優(yōu)解，選擇隨機(jī)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)與鄰接節(jié)點(diǎn)作為初始化種群，并且設(shè)計(jì)了節(jié)點(diǎn)對(duì)社區(qū)的隸屬度計(jì)算方案，通過(guò)設(shè)置合適的閾值能夠控制檢測(cè)的社區(qū)規(guī)模，該方案也能夠預(yù)測(cè)網(wǎng)絡(luò)中的社區(qū)數(shù)量，為社區(qū)的規(guī)模進(jìn)行約束，提高種群演化的準(zhǔn)確性。因?yàn)楸舅惴ǖ纳鐓^(qū)隸屬度計(jì)算方案同時(shí)考慮了節(jié)點(diǎn)的社區(qū)內(nèi)部關(guān)聯(lián)性與外部關(guān)聯(lián)性，因此能夠同時(shí)適用于社區(qū)重疊與社區(qū)不重疊的社交網(wǎng)絡(luò)。

1 背景知識(shí)

1.1 社區(qū)發(fā)現(xiàn)的模塊性

模塊性是社區(qū)發(fā)現(xiàn)研究中應(yīng)用最為廣泛的目標(biāo)函數(shù)，能夠定量地描述社區(qū)的結(jié)構(gòu)，并且形式簡(jiǎn)潔、易于計(jì)算。模塊性表示了網(wǎng)絡(luò)中連接社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)的邊占網(wǎng)絡(luò)總邊數(shù)的比例與一個(gè)隨機(jī)網(wǎng)絡(luò)中連接社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)的邊占網(wǎng)絡(luò)總邊數(shù)比例的差值，模塊性函數(shù)(Q)定義為下式

(1)

式中：M表示網(wǎng)絡(luò)中邊的總數(shù)量，下標(biāo)i與j表示網(wǎng)絡(luò)的兩個(gè)節(jié)點(diǎn)，Ki與Kj分別是第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)的度，參數(shù)aij表示鄰接矩陣第i行、第j列的元素，δ(i,j)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)之間的關(guān)系，如果節(jié)點(diǎn)i與節(jié)點(diǎn)j在同一個(gè)社區(qū)內(nèi)，那么δ(i,j)=1；否則，δ(i,j)=0。對(duì)于社交網(wǎng)絡(luò)的社區(qū)劃分問(wèn)題，Q值越大，表示社區(qū)結(jié)構(gòu)性越強(qiáng)，一般社區(qū)劃分較為明顯的Q值范圍為0.3～0.7。本文的遺傳算法將Q值作為適應(yīng)度函數(shù)。

1.2 基于重疊與非重疊區(qū)域的社區(qū)隸屬度

該文設(shè)計(jì)了一個(gè)基于關(guān)聯(lián)節(jié)點(diǎn)的社區(qū)數(shù)量估計(jì)算法，該估計(jì)算法考慮了網(wǎng)絡(luò)連接的整體結(jié)構(gòu)。采用兩個(gè)參數(shù)描述每個(gè)節(jié)點(diǎn)的社區(qū)隸屬度，分析社區(qū)的重疊部分與非重疊部分。參數(shù)IA(內(nèi)部關(guān)聯(lián)性)表示某個(gè)節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的連接情況，該參數(shù)度量了社區(qū)內(nèi)節(jié)點(diǎn)的內(nèi)部關(guān)聯(lián)性，IA已經(jīng)足以檢測(cè)出社區(qū)的非重疊部分，但難以檢測(cè)出社區(qū)的重疊部分。另一個(gè)參數(shù)EA(外部關(guān)聯(lián)性)度量了網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)在不同社區(qū)之間的作用量，采用生成隨機(jī)模塊模型[15]實(shí)現(xiàn)該參數(shù)。最終，一個(gè)節(jié)點(diǎn)屬于某個(gè)社區(qū)的概率依賴該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量以及該節(jié)點(diǎn)與其它社區(qū)的作用量，將這兩個(gè)度量指標(biāo)定義為節(jié)點(diǎn)的社區(qū)關(guān)聯(lián)度。

考慮一個(gè)一般性的網(wǎng)絡(luò)結(jié)構(gòu)，表示為圖結(jié)構(gòu)G=(V,E)，其中V與E分別表示網(wǎng)絡(luò)的節(jié)點(diǎn)集與邊集合。社區(qū)發(fā)現(xiàn)問(wèn)題可建模為搜索節(jié)點(diǎn)的分組ci，可將ci表示為C=c1∪c2∪…∪ck。

1.2.1 非重疊區(qū)域的內(nèi)部關(guān)聯(lián)性

內(nèi)部關(guān)聯(lián)度(IA)評(píng)估了每個(gè)節(jié)點(diǎn)與其所屬社區(qū)的關(guān)聯(lián)性，具體定義為下式

(2)

式中：N(vi)是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)，P(vj|ci)表示節(jié)點(diǎn)vj對(duì)于社區(qū)ci的社區(qū)傳播概率，該值由邊聚類算法[16]推導(dǎo)而來(lái)，N(vi)等于節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)數(shù)量。

1.2.2 重疊區(qū)域的外部關(guān)聯(lián)性

圖1是重疊社區(qū)與非重疊社區(qū)的網(wǎng)絡(luò)示意圖。通過(guò)模塊模型可檢測(cè)每個(gè)節(jié)點(diǎn)與其它社區(qū)的外部關(guān)聯(lián)度，每個(gè)節(jié)點(diǎn)外部關(guān)聯(lián)度的計(jì)算步驟如下：

步驟1 估計(jì)兩個(gè)社區(qū)之間的作用矩陣；

步驟2 基于鄰居節(jié)點(diǎn)的社區(qū)傳播概率與作用矩陣計(jì)算給定節(jié)點(diǎn)的外部關(guān)聯(lián)度。

圖1 非重疊社區(qū)與重疊社區(qū)的網(wǎng)絡(luò)

2 針對(duì)社區(qū)發(fā)現(xiàn)的遺傳算法

針對(duì)社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問(wèn)題提出了一種遺傳算法，采用模塊性函數(shù)(Q函數(shù))引導(dǎo)遺傳算法的演化過(guò)程，并且設(shè)計(jì)了不同的策略與遺傳算子來(lái)識(shí)別網(wǎng)絡(luò)的社區(qū)。

隨機(jī)初始化策略的網(wǎng)絡(luò)節(jié)點(diǎn)之間缺少關(guān)聯(lián)性導(dǎo)致初始解的質(zhì)量較低，影響了遺傳算法的尋優(yōu)能力與收斂速度。為了解決該問(wèn)題，設(shè)計(jì)了一種初始化方案，將原網(wǎng)絡(luò)圖中連接的相鄰點(diǎn)作為初始化空間，該方案有助于提高算法的收斂速度；然后，采用社區(qū)密度指標(biāo)度量個(gè)體數(shù)據(jù)的結(jié)構(gòu)，從而平衡各個(gè)社區(qū)的規(guī)模。

本文的社區(qū)初始化機(jī)制有以下兩種：

(1)一級(jí)鄰居初始化機(jī)制：圖2是初始化機(jī)制的示意圖，隨機(jī)選擇一個(gè)節(jié)點(diǎn)(圖中為節(jié)點(diǎn)3)，將節(jié)點(diǎn)3與其一級(jí)鄰居納入初始化社區(qū)中，如果達(dá)到預(yù)設(shè)的最大社區(qū)規(guī)模，則結(jié)束搜索過(guò)程。如果節(jié)點(diǎn)3沒(méi)有一級(jí)鄰居，則重復(fù)上述過(guò)程直至達(dá)到預(yù)設(shè)的最大社區(qū)規(guī)模。

(2)二級(jí)鄰居初始化機(jī)制：圖2是初始化機(jī)制的示意圖，隨機(jī)選擇社區(qū)內(nèi)一個(gè)具有一級(jí)鄰居的節(jié)點(diǎn)(圖中為節(jié)點(diǎn)3)，將節(jié)點(diǎn)3的二級(jí)鄰居納入初始化社區(qū)中，如果達(dá)到預(yù)設(shè)的最大社區(qū)規(guī)模，則結(jié)束搜索過(guò)程。如果節(jié)點(diǎn)3沒(méi)有二級(jí)鄰居，則重復(fù)上述過(guò)程直至達(dá)到預(yù)設(shè)的最大社區(qū)規(guī)模。

圖2 一級(jí)鄰居初始化與二級(jí)鄰居初始化

2.1 種群初始化方案

在初始化階段，使用估計(jì)的社區(qū)數(shù)量(1.2小節(jié))計(jì)算每個(gè)社區(qū)的最大規(guī)模，采用平衡初始化機(jī)制計(jì)算最大規(guī)模值：將網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)量除以估計(jì)的社區(qū)數(shù)量，計(jì)算結(jié)果稱為社區(qū)密度，將該值作為初始化種群中每個(gè)社區(qū)的最大規(guī)模值。然后開(kāi)始鄰居社區(qū)初始化程序，如果①一級(jí)鄰居初始化機(jī)制未能達(dá)到最大的社區(qū)規(guī)模，則開(kāi)始②二級(jí)鄰居初始化過(guò)程。圖3(a)是種群初始化的一個(gè)實(shí)例。

圖3 社區(qū)初始化實(shí)例

種群演化的過(guò)程中，兩個(gè)社區(qū)邊界之間的節(jié)點(diǎn)可能發(fā)生遷移，遷移策略是基于邊向最有吸引力目標(biāo)遷移的思想，即給定一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)將遷移至該節(jié)點(diǎn)連接的最大規(guī)模社區(qū)。邊界之間遷移向量的初始化方案，如圖3(b)所示。表1是邊界遷移的產(chǎn)生方法，表1的列表示了社區(qū)1與社區(qū)2，節(jié)點(diǎn)數(shù)量直接與列節(jié)點(diǎn)連接。列遷移向量按照所有社區(qū)計(jì)數(shù)器中的最高值(最多連接數(shù))選擇每個(gè)節(jié)點(diǎn)的最終目標(biāo)社區(qū)。

表1 邊界遷移的產(chǎn)生方案

2.2 基于社區(qū)隸屬度的社區(qū)發(fā)現(xiàn)規(guī)模控制

在許多實(shí)際應(yīng)用中，社區(qū)結(jié)構(gòu)的數(shù)量是已知值，能夠縮小搜索算法的搜索空間；而在其它的多數(shù)場(chǎng)景下，社區(qū)結(jié)構(gòu)的數(shù)量是未知值，但可以估計(jì)出社區(qū)結(jié)構(gòu)的數(shù)量，據(jù)此也可以縮小搜索空間。預(yù)測(cè)或者預(yù)知社交網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的數(shù)量，能夠有效地縮小搜索空間，并且提高算法的性能。

網(wǎng)絡(luò)中的社區(qū)規(guī)模存在巨大的差異，為了滿足可控制的社區(qū)發(fā)現(xiàn)算法，設(shè)計(jì)了基于社區(qū)隸屬度的社區(qū)發(fā)現(xiàn)規(guī)模控制方案。通過(guò)節(jié)點(diǎn)的社區(qū)隸屬度估計(jì)出網(wǎng)絡(luò)中不同規(guī)模的社區(qū)數(shù)量，如果用戶請(qǐng)求搜索大規(guī)模的社區(qū)結(jié)構(gòu)，則可以設(shè)置較大的社區(qū)隸屬度閾值，從而減小網(wǎng)絡(luò)中的目標(biāo)社區(qū)數(shù)量，該機(jī)制能夠有效地縮小遺傳算法的搜索空間；如果用戶請(qǐng)求搜索網(wǎng)絡(luò)中的全部社區(qū)結(jié)構(gòu)，則可以設(shè)置較小的社區(qū)隸屬度閾值。

圖4是社區(qū)隸屬度的計(jì)算方法的流程框架，包含了節(jié)點(diǎn)的內(nèi)部關(guān)聯(lián)性與外部關(guān)聯(lián)性。

圖4 社區(qū)隸屬度算法的流程框架

假設(shè)網(wǎng)絡(luò)由相互關(guān)聯(lián)的社區(qū)組成，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)與社區(qū)具有兩層關(guān)聯(lián)性，第一層是同一個(gè)社區(qū)節(jié)點(diǎn)之間的內(nèi)部關(guān)聯(lián)性，第二層是節(jié)點(diǎn)與其它社區(qū)的外部關(guān)聯(lián)性。該文提出一個(gè)基于概率的隸屬度方法，檢測(cè)出網(wǎng)絡(luò)的社區(qū)數(shù)量。

將每個(gè)節(jié)點(diǎn)vi對(duì)于社區(qū)ci的概率隸屬條件定義為下式

P(vi∈ci)=P(vi∈ci|N(vi)∈ci)+
P(vi∈ci|N(vi)∈c-i)

(3)

P(vi∈ci)=P1(ci).IAci(vi)+p2(ci).EAci(vi)

(4)

(5)

式中：β(ci,cj)是社區(qū)ci與cj之間的作用矩陣。通過(guò)最大似然估計(jì)方法獲得每對(duì)社區(qū)之間的近似作用矩陣

(6)

式中:ρ是已知的稀疏正則化因子，ρ的計(jì)算方法為[17]

(7)

式中：F(vi|ci)=max(P(vi|ci)×P(vj|cj),P(vi|cj)×P(vj|cj))。

圖5是3個(gè)社區(qū)重疊的實(shí)例，節(jié)點(diǎn)v4同時(shí)屬于3個(gè)社區(qū)，根據(jù)式(2)～式(6)可計(jì)算出圖中：ρ=39/53，βc1,c2=1.25，βc1,c3=0.8，βc2,c3=1，EAv4(c1)=53/70，EAv4(c2)=45/70，EAv4(c3)=46/70，IAv4(c1)=2/7，IAv4(c2)=3/7，IAv4(c3)=2/7。計(jì)算出節(jié)點(diǎn)的內(nèi)部關(guān)聯(lián)性與外部關(guān)聯(lián)性之后，最終傳播概率依賴權(quán)重值p1與p2，p1與p2的計(jì)算方法如下

(8)

圖5 3個(gè)社區(qū)重疊的實(shí)例

節(jié)點(diǎn)v4同時(shí)屬于3個(gè)社區(qū)，根據(jù)式(2)～式(6)可計(jì)算出：ρ=39/53，βc1,c2=1.25，βc1,c3=0.8，βc2,c3=1，EAv4(c1)=53/70，EAv4(c2)=45/70，EAv4(c3)=46/70，IAv4(c1)=2/7，IAv4(c2)=3/7，IAv4(c3)=2/7。

2.3 遺傳算子

為了增強(qiáng)遺傳算法對(duì)社交網(wǎng)絡(luò)相關(guān)數(shù)據(jù)結(jié)構(gòu)的尋優(yōu)效果，設(shè)計(jì)了特殊的遺傳算子。

2.3.1 交叉算子

交叉算子基于社區(qū)邊界間節(jié)點(diǎn)的交換而實(shí)現(xiàn)，將目標(biāo)社區(qū)邊界的一個(gè)節(jié)點(diǎn)與當(dāng)前社區(qū)的另一個(gè)節(jié)點(diǎn)進(jìn)行交換，并且目標(biāo)社區(qū)不應(yīng)是當(dāng)前的社區(qū)。第二個(gè)節(jié)點(diǎn)應(yīng)當(dāng)滿足其社區(qū)最優(yōu)的外部關(guān)聯(lián)性(第1.2小節(jié)描述)。通過(guò)選擇外部關(guān)聯(lián)性最優(yōu)的節(jié)點(diǎn)進(jìn)行交叉操作，有助于維護(hù)社區(qū)之間規(guī)模的平衡。圖6是交叉算子的操作實(shí)例，在該實(shí)例中，選擇節(jié)點(diǎn)3作為互換節(jié)點(diǎn)，其目標(biāo)社區(qū)是節(jié)點(diǎn)1，圖6中目標(biāo)社區(qū)的節(jié)點(diǎn)是與源社區(qū)(社區(qū)2)關(guān)聯(lián)性最高的社區(qū)，選擇這兩個(gè)社區(qū)的節(jié)點(diǎn)進(jìn)行交換。列“節(jié)點(diǎn)”列出了外部連接的數(shù)量，選為交換的節(jié)點(diǎn)是具有最多鄰居數(shù)量的節(jié)點(diǎn)：節(jié)點(diǎn)3有3個(gè)外部連接，節(jié)點(diǎn)5有1個(gè)外部連接，選擇節(jié)點(diǎn)5與節(jié)點(diǎn)3交換。

圖6 交叉算子的操作實(shí)例

2.3.2 變異算子

選擇適合變異的節(jié)點(diǎn)集，從該節(jié)點(diǎn)集中隨機(jī)選擇一個(gè)節(jié)點(diǎn)，將該節(jié)點(diǎn)與目標(biāo)社區(qū)的一個(gè)節(jié)點(diǎn)進(jìn)行交換。圖7是變異算子的操作實(shí)例，在該實(shí)例中，目標(biāo)社區(qū)的節(jié)點(diǎn)是與源社區(qū)(社區(qū)2)關(guān)聯(lián)性最高的社區(qū)，選擇這兩個(gè)社區(qū)的節(jié)點(diǎn)進(jìn)行變異操作，關(guān)聯(lián)性最高的社區(qū)能夠提高尋優(yōu)效果。計(jì)算的復(fù)制(reproduction)節(jié)點(diǎn)數(shù)量為2，然后隨機(jī)選擇兩個(gè)復(fù)制節(jié)點(diǎn)，將節(jié)點(diǎn)5復(fù)制為節(jié)點(diǎn)2。

圖7 變異算子的操作實(shí)例

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

將本算法與其它基于遺傳算法的社區(qū)發(fā)現(xiàn)算法以及非基于遺傳算法的社區(qū)發(fā)現(xiàn)算法進(jìn)行了對(duì)比分析，綜合評(píng)估本算法的性能。實(shí)驗(yàn)環(huán)境為PC機(jī)，CPU為Intel Core i7，2.4 GHz主頻，8 GB內(nèi)存。基于Matlab編程實(shí)現(xiàn)本算法。

3.1 性能評(píng)價(jià)指標(biāo)

NMI(標(biāo)準(zhǔn)化互信息)是社區(qū)發(fā)現(xiàn)問(wèn)題中常用的性能評(píng)估指標(biāo)，NMI定義為下式

(9)

式中：網(wǎng)絡(luò)的兩個(gè)部分A與B構(gòu)成了混淆矩陣C，Cij表示屬于A部分中社區(qū)i與B部分中社區(qū)j的節(jié)點(diǎn)數(shù)量，CA與CB分別表示A與B部分的社區(qū)數(shù)量，Ci表示A部分中社區(qū)i的節(jié)點(diǎn)數(shù)量，N表示節(jié)點(diǎn)的總數(shù)量。如果A=B，那么NMI(A,B)=1；如果A與B完全不同，那么NMI(A,B)=0。NMI值越接近1，說(shuō)明算法劃分的社區(qū)結(jié)構(gòu)與最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)越相似。

3.2 參數(shù)配置

目前已經(jīng)具有許多基于遺傳算法的社區(qū)發(fā)現(xiàn)算法，為了評(píng)估本文本算法的有效性，首先將本算法與其它基于遺傳算法的社區(qū)發(fā)現(xiàn)算法進(jìn)行比較，分別為IGA[12]、GAOM[13]、MAGA[14]。

為了確保對(duì)比的公平性，所有的遺傳算法采用相同的參數(shù)設(shè)置，具體見(jiàn)表2。

表2 遺傳算法的仿真實(shí)驗(yàn)參數(shù)

3.3 與基于遺傳算法的社區(qū)發(fā)現(xiàn)算法比較

3.3.1 benchmark數(shù)據(jù)集

采用4個(gè)常用的公開(kāi)社交網(wǎng)絡(luò)數(shù)據(jù)集作為benchmark數(shù)據(jù)集，評(píng)估4個(gè)基于遺傳算法的社區(qū)發(fā)現(xiàn)算法的性能，4個(gè)社交網(wǎng)絡(luò)的描述見(jiàn)表3。

表3 基于遺傳算法的社區(qū)發(fā)現(xiàn)算法benchmark數(shù)據(jù)集

3.3.2 社區(qū)發(fā)現(xiàn)的準(zhǔn)確率結(jié)果與分析

每個(gè)算法對(duì)每個(gè)benchmark數(shù)據(jù)集均獨(dú)立地運(yùn)行50次，統(tǒng)計(jì)每組數(shù)據(jù)的平均值與標(biāo)準(zhǔn)偏差。4個(gè)算法對(duì)4個(gè)數(shù)據(jù)集的社區(qū)劃分準(zhǔn)確性如圖8所示。從圖中可看出，本算法的NMI平均值與標(biāo)準(zhǔn)偏差均優(yōu)于其它3個(gè)基于遺傳算法的社區(qū)發(fā)現(xiàn)算法，隨著社交網(wǎng)絡(luò)規(guī)模的擴(kuò)大，本算法的優(yōu)勢(shì)更加明顯。本算法的標(biāo)準(zhǔn)偏差也明顯地優(yōu)于其它3個(gè)算法，可看出本算法的社區(qū)劃分結(jié)果具有較好的魯棒性。

圖8 4個(gè)算法對(duì)4個(gè)數(shù)據(jù)集的社區(qū)劃分準(zhǔn)確性(NMI值)

數(shù)據(jù)集1的網(wǎng)絡(luò)規(guī)模較小，社區(qū)數(shù)量也僅有3個(gè)，4個(gè)社區(qū)發(fā)現(xiàn)算法的NMI值均較低，遺傳算法對(duì)于這種小規(guī)模數(shù)據(jù)集的迭代次數(shù)較少，并且容易受到初始化種群的影響，因此小規(guī)模數(shù)據(jù)集的性能低于大規(guī)模數(shù)據(jù)集的性能。但是數(shù)據(jù)集4的網(wǎng)絡(luò)規(guī)模約為數(shù)據(jù)集1的4倍，而IGA[12]、GAOM[13]、MAGA[14]這3個(gè)算法的NMI值卻低于數(shù)據(jù)集2與數(shù)據(jù)集3，這顯示了這3個(gè)遺傳算法未能較好地考慮社交網(wǎng)絡(luò)的特點(diǎn)，而本算法設(shè)計(jì)了基于社區(qū)隸屬度的社區(qū)數(shù)量估計(jì)算法，對(duì)于不同規(guī)模的數(shù)據(jù)集均能夠獲得較高的準(zhǔn)確率。

4個(gè)算法對(duì)4個(gè)數(shù)據(jù)集的社區(qū)劃分模塊性結(jié)果(Q函數(shù))如圖9所示。因?yàn)?個(gè)遺傳算法均將Q函數(shù)作為適應(yīng)度函數(shù)，因此Q函數(shù)的結(jié)果直接反映了4個(gè)遺傳算法的最優(yōu)解結(jié)果，可看出4個(gè)算法對(duì)數(shù)據(jù)集1,2,3的模塊性結(jié)果均在[0.3,0.7]之間，而數(shù)據(jù)集4提出的最優(yōu)社區(qū)并未考慮模塊性，所以導(dǎo)致GAOM、MAGA兩個(gè)算法的模塊性結(jié)果小于0.3。

圖9 4個(gè)算法對(duì)4個(gè)數(shù)據(jù)集的社區(qū)劃分模塊性結(jié)果(Q函數(shù))

3.3.3 社區(qū)發(fā)現(xiàn)的時(shí)間效率

時(shí)間效率是遺傳算法的一個(gè)重要指標(biāo)，在此統(tǒng)計(jì)了4個(gè)遺傳算法對(duì)于數(shù)據(jù)集4的計(jì)算時(shí)間，結(jié)果見(jiàn)表4。GAOM算法為了解決遺傳算法易于陷入局部最優(yōu)的問(wèn)題，其變異算子在每輪迭代過(guò)程中均需要計(jì)算網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的局部信息以及社區(qū)隸屬度值，遺傳算法求解大規(guī)模問(wèn)題的迭代次數(shù)往往較多，而GAOM每次迭代的計(jì)算量均較大，嚴(yán)重影響了計(jì)算效率。MAGA是一種基于agent的遺傳算法，該算法的各個(gè)agent均需要完成多個(gè)復(fù)雜的算子，包括：基于分割與合并的鄰居節(jié)點(diǎn)競(jìng)爭(zhēng)算子、混合鄰居節(jié)點(diǎn)交叉算子、自適應(yīng)變異以及自學(xué)習(xí)算子，這些算子計(jì)算量較大，因此MAGA的收斂速度也較慢。IGA通過(guò)免疫機(jī)制約束了遺傳算法的初始化種群，縮小了初始化搜索空間，因此收斂速度較快，計(jì)算速度也較快。本算法將社交網(wǎng)絡(luò)中的鄰居節(jié)點(diǎn)與鄰接節(jié)點(diǎn)納入初始化種群中，并且設(shè)計(jì)了基于社區(qū)隸屬度的社區(qū)數(shù)量估計(jì)算法，有效地減小了網(wǎng)絡(luò)的社區(qū)空間，并且能夠快速地引導(dǎo)種群的演化過(guò)程，本算法獲得了最低的計(jì)算時(shí)間，此外，計(jì)算時(shí)間的標(biāo)準(zhǔn)偏差為0.0077，因此本算法的計(jì)算效率具有較好的穩(wěn)定性。

表4 4個(gè)社區(qū)發(fā)現(xiàn)算法對(duì)于數(shù)據(jù)集的計(jì)算時(shí)間(單位：秒，每組實(shí)驗(yàn)獨(dú)立運(yùn)行50次，統(tǒng)計(jì)平均值與標(biāo)準(zhǔn)偏差)

3.4 與一般社區(qū)發(fā)現(xiàn)算法比較

3.4.1 benchmark數(shù)據(jù)集

因?yàn)楸舅惴ǖ纳鐓^(qū)隸屬度估計(jì)算法考慮了重疊社區(qū)與非重疊社區(qū)，因此本文采用兩種類型的真實(shí)數(shù)據(jù)集評(píng)估本算法的性能，分別見(jiàn)表5與表6，表中給出了重疊社交網(wǎng)絡(luò)與非重疊社交網(wǎng)絡(luò)的結(jié)構(gòu)介紹。10個(gè)數(shù)據(jù)集的網(wǎng)絡(luò)規(guī)模均較大，能夠測(cè)試本算法對(duì)于大規(guī)模社交網(wǎng)絡(luò)的性能。

表5 重疊社區(qū)結(jié)構(gòu)的社交網(wǎng)絡(luò)

表6 非重疊社區(qū)結(jié)構(gòu)的社交網(wǎng)絡(luò)

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

COMBO、NISE是兩個(gè)近期性能較好的社區(qū)發(fā)現(xiàn)算法，并且這兩個(gè)算法同時(shí)支持重疊社區(qū)與非重疊社區(qū)的社交網(wǎng)絡(luò)，因此將本算法與這兩個(gè)算法進(jìn)行比較。首先對(duì)5個(gè)重疊社區(qū)的社交網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，每組實(shí)驗(yàn)獨(dú)立運(yùn)行50次，統(tǒng)計(jì)NMI的平均值與標(biāo)準(zhǔn)偏差，結(jié)果如圖10所示。可看出，本算法對(duì)于數(shù)據(jù)集1,2,3,4的社區(qū)檢測(cè)準(zhǔn)確率均優(yōu)于其它兩個(gè)算法，數(shù)據(jù)集5的最優(yōu)社區(qū)劃分方案并未考慮模塊性，而本算法成功搜索出最優(yōu)的模塊性結(jié)果，但是與數(shù)據(jù)集5提出的最優(yōu)社區(qū)劃分方案仍然有一定的差異，因此本算法對(duì)于數(shù)據(jù)集5的NMI值較低，略低于其它兩個(gè)算法。

圖10 3個(gè)算法的對(duì)于社區(qū)重疊社交網(wǎng)絡(luò)的社區(qū)檢測(cè)NMI結(jié)果

然后對(duì)5個(gè)非重疊社區(qū)的社交網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，每組實(shí)驗(yàn)獨(dú)立運(yùn)行50次，統(tǒng)計(jì)NMI的平均值與標(biāo)準(zhǔn)偏差，結(jié)果如圖11所示?？煽闯?，本算法對(duì)于數(shù)據(jù)集1,2,3,4的社區(qū)檢測(cè)準(zhǔn)確率均明顯地優(yōu)于其它兩個(gè)算法，數(shù)據(jù)集5中包含大量位于社區(qū)邊界的節(jié)點(diǎn)，并且這些節(jié)點(diǎn)與其它社區(qū)的距離均較為接近，3個(gè)社區(qū)發(fā)現(xiàn)算法對(duì)于數(shù)據(jù)集均獲得了較低的NMI值，3個(gè)算法的結(jié)果較為接近。

圖11 3個(gè)算法的對(duì)于社區(qū)不重疊社交網(wǎng)絡(luò)的社區(qū)檢測(cè)NMI結(jié)果

4 結(jié)束語(yǔ)

為了提高大規(guī)模社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的準(zhǔn)確率與計(jì)算效率，設(shè)計(jì)了一種基于遺傳算法的社區(qū)發(fā)現(xiàn)算法，采用遺傳算法搜索Q函數(shù)的最優(yōu)解，選擇隨機(jī)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)與鄰接節(jié)點(diǎn)作為初始化種群，并且設(shè)計(jì)了節(jié)點(diǎn)對(duì)社區(qū)的隸屬度計(jì)算方案，通過(guò)設(shè)置合適的閾值能夠控制檢測(cè)的社區(qū)規(guī)模，該方案也能夠預(yù)測(cè)網(wǎng)絡(luò)中的社區(qū)數(shù)量，為社區(qū)的規(guī)模進(jìn)行約束，提高種群演化的準(zhǔn)確性。因?yàn)楸舅惴ǖ纳鐓^(qū)隸屬度計(jì)算方案同時(shí)考慮了節(jié)點(diǎn)的社區(qū)內(nèi)部關(guān)聯(lián)性與外部關(guān)聯(lián)性，因此能夠同時(shí)適用于社區(qū)重疊與社區(qū)不重疊的社交網(wǎng)絡(luò)。該算法對(duì)于大規(guī)模數(shù)據(jù)集也具有較高的社區(qū)檢測(cè)準(zhǔn)確率。

因?yàn)楸舅惴ㄊ且环N基于社交網(wǎng)絡(luò)模塊性的社區(qū)發(fā)現(xiàn)算法，如果社區(qū)的重疊部分存在密集的連接，則會(huì)影響社區(qū)的模塊性，這為本算法的社區(qū)檢測(cè)準(zhǔn)確率帶來(lái)不利的影響，未來(lái)將重點(diǎn)關(guān)注不滿足社區(qū)模塊性的社交網(wǎng)絡(luò)問(wèn)題。