離散Jaya算法的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)①

李劍雄,鮑志強

(華南師范大學(xué) 計算機學(xué)院，廣州 510631)

許多現(xiàn)實世界中的復(fù)雜系統(tǒng)都可以使用復(fù)雜網(wǎng)絡(luò)來描述,例如社交網(wǎng)、生物網(wǎng)、萬維網(wǎng)、交通網(wǎng)等.復(fù)雜網(wǎng)絡(luò)可建模為圖,其中節(jié)點表示網(wǎng)絡(luò)中的對象,邊表示對象間的關(guān)系.大量研究結(jié)果表明:復(fù)雜網(wǎng)絡(luò)通常具有小世界性和無標(biāo)性等統(tǒng)計特性,并呈現(xiàn)出社區(qū)結(jié)構(gòu)等拓?fù)涮匦?一個網(wǎng)絡(luò)可以分成若干社區(qū),社區(qū)內(nèi)部的節(jié)點連接相對緊密,不同社區(qū)之間的節(jié)點連接相對稀疏[1,2].社區(qū)發(fā)現(xiàn)的目的是找出復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu),提取社區(qū)結(jié)構(gòu)中的信息.

來自不同領(lǐng)域的研究中提出了許多不同的社發(fā)現(xiàn)算法,這些算法可大致分為:圖劃分的分割算法[3]、聚類算法[4-6]、基于網(wǎng)絡(luò)動力學(xué)特性的算法[7-9]和基于目標(biāo)函數(shù)的優(yōu)化算法[10-14].其中以模塊度函數(shù)(Modularity,Q)的為目標(biāo)函數(shù)的優(yōu)化算法是目前較為普遍的一類算法.模塊度函數(shù)Q是Newman 提出的評價社區(qū)結(jié)構(gòu)優(yōu)劣的指標(biāo)[6],借助于該函數(shù)可將社區(qū)發(fā)現(xiàn)問題轉(zhuǎn)化為優(yōu)化問題.如Duch[15]提出了基于模塊度的極值優(yōu)化算法,Guimera 等[16]基于模擬退火的GA(Genetic algorithm)算法,2008年Blondel 等[17]提出的BGLL 算法.然而求最優(yōu)模塊度的社區(qū)結(jié)構(gòu)是NP 難問題,常常用啟發(fā)式算法求解.許多啟發(fā)式算法屬于貪心法,一般很難求得滿意的社區(qū)劃分結(jié)果,且需要預(yù)先設(shè)定網(wǎng)絡(luò)的社區(qū)數(shù)目.智能優(yōu)化元啟發(fā)式算法作為社區(qū)發(fā)現(xiàn)問題的一種有效解決手段,目前已被廣泛應(yīng)用求解[18-20].Talbi 等[21]提出了一種求解圖劃分問題的并行遺傳算法,該算法具有超線性加速特性.Bui 等[22]提出了基于圖劃分的預(yù)處理模式從而提高遺傳算法的空間搜索能力.Tasgin等[23]基于模塊度使用了遺傳算法進行社區(qū)發(fā)現(xiàn).Gog 等[24]基于種群中個體的信息分享機制提出了一種協(xié)同進化算法用于社區(qū)發(fā)現(xiàn).Pizzuti[25]提出了GANet 遺傳算法,利用了locus-based 表示法和交叉操作,該方法在操作時只考慮了該點的實際連接關(guān)系,有效的減少了無效搜索.Gong 等[26]提出了一種文化基因算法用于優(yōu)化模塊密度進行社區(qū)發(fā)現(xiàn).Duch 等[15]通過對標(biāo)準(zhǔn)差分進化算法的交叉操作進行離散化,提出了離散差分進化算法用于社區(qū)發(fā)現(xiàn).Change 等[27]采用最大最小蟻群算法,通過信息素的揮發(fā)和路徑的選擇進行社區(qū)的劃分.金弟等[13]通過分析模塊度函數(shù)的局部單調(diào)性,以及改進遺傳算法的變異策略,提出一種基于局部搜索的改進遺傳算法.張英杰等[14]提出了一種基于免疫差分進化算法IDDE (Immune Discrete Differential Evolutiona).Said 等[28]提出了基于聚類協(xié)同系數(shù)的CC-GA (Clustering Coefficient based Genetic Algorithm)算法,該算法可用于稠密網(wǎng)絡(luò)和稀疏網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn).

Jaya 算法[29]是由Rao RV 提出的一種元啟發(fā)式算法,適用于求解連續(xù)型最優(yōu)化問題.與其它元啟發(fā)式算法相比,Jaya 算法簡單,需要輸入的參數(shù)少,只需設(shè)置種群大小和迭代次數(shù).該算法通過離散化,近年來已被應(yīng)用在許多不同的組合優(yōu)化問題上[30,31].本文針對復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題,遵循Jaya 算法的基本思想,提出了一種離散化的算法形式稱作DJaya (Discrete Jaya algorithm),其核心思想是針對種群中個體不同的傾向性,采取不同的更新方式,平衡全局探索性和局部搜索性來提高搜索的有效性.在標(biāo)準(zhǔn)人造網(wǎng)絡(luò)數(shù)據(jù)集GN Benchmark 和幾個典型的真實網(wǎng)絡(luò)算例上的實驗分析表明,DJaya 算法能自動確定社區(qū)的數(shù)目,且在模塊度、互信息等方面表現(xiàn)出良好的性能[32].

1 相關(guān)工作

1.1 模塊度函數(shù)

不同的社區(qū)發(fā)現(xiàn)算法在同一復(fù)雜網(wǎng)絡(luò)上進行社區(qū)劃分時結(jié)果通常是不同的.為了統(tǒng)一評價標(biāo)準(zhǔn),Newman等提出了社區(qū)結(jié)構(gòu)的模塊度函數(shù).模塊度函數(shù)易于理解且計算簡單,被廣泛用來評價社區(qū)劃分質(zhì)量[5].一個社區(qū)結(jié)構(gòu)的模塊度Q定義如下:

其中,ki表示節(jié)點i的 度,kikj/2m表示節(jié)點i與 節(jié)點j之間的連接概率,Aij表示圖的鄰接矩陣,如果節(jié)點i與節(jié)點j有邊相連,則Aij=1,否則Aij=0.ci表示節(jié)點i所屬的社區(qū),如果ci=cj,則δ (ci,cj)=1,否則δ (ci,cj)=0.通常,Q值的范圍是[-0.5,1),越接近于1,則復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯.Q值一般在0.3-0.7 的范圍內(nèi)[2],當(dāng)Q＜0.3時表明網(wǎng)絡(luò)幾乎沒有社區(qū)結(jié)構(gòu).

1.2 基于模塊度的社區(qū)發(fā)現(xiàn)的典型算法

基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)算法有許多,其中包括許多以模塊度為目標(biāo)函數(shù)的算法,其典型的代表如FMM (Fast Modularity Maximization)算法[5]、LPA(Label Propagation Algorithm)算法[33]、BGLL 算法[24]等貪心啟發(fā)式算法,以及近年提出的ACO (Ant Colony Optimization)[28]、LGA (Genetic Algorithm with Local search)[14]、IDDE、CC-GA 等元啟發(fā)式算法.

FMM 算法將圖中每個節(jié)點初始化為一個單獨的社區(qū),然后選擇使模塊度Q的增值最大的社區(qū)進行合并,重復(fù)該步驟,直到網(wǎng)絡(luò)中所有節(jié)點屬于同一個社區(qū).整個過程是自底向上的過程,最終得到一個層次圖.網(wǎng)絡(luò)中節(jié)點對應(yīng)層次圖的最底層的葉子節(jié)點.層次圖中每一層對應(yīng)網(wǎng)絡(luò)的某種劃分,層次圖中所有層次對應(yīng)的劃分中模塊度最大的劃分為網(wǎng)絡(luò)最終劃分.

標(biāo)簽傳播算法LPA 是由Raghavan 等提出的[34],其基本思想是讓每個節(jié)點有一個自己特有的標(biāo)簽,節(jié)點會選擇自己鄰居中出現(xiàn)次數(shù)最多的標(biāo)簽,如果每個標(biāo)簽出現(xiàn)次數(shù)一樣多,就隨機選擇一個標(biāo)簽替換自己原始的標(biāo)簽,如此往復(fù),直到每個節(jié)點標(biāo)簽不再發(fā)生變化,那么持有相同標(biāo)簽的節(jié)點就歸為一個社區(qū).標(biāo)簽傳播算法具有簡單、高效、快速的優(yōu)點,常常和其它算法結(jié)合,用來初始化種群,增加種群的多樣性和精度,加快算法的收斂.

BGLL 算法是一種層次性貪心算法,它是一個兩階段過程.第一階段首先將每一個節(jié)點劃分作為單獨的社區(qū),然后考慮將每個節(jié)點合并到其鄰接點所在的社區(qū)中,執(zhí)行能使模塊度增大的合并.第二階段將第一階段劃分出來的社區(qū)聚合成為一個點后形成新的網(wǎng)絡(luò),再在新的網(wǎng)絡(luò)上重復(fù)以上過程,直到網(wǎng)絡(luò)中的結(jié)構(gòu)不再改變?yōu)橹?

ACO 算法以網(wǎng)絡(luò)的一個隨機社區(qū)劃分作為初始解,通過編碼把初始解作為路徑上的初始信息素,然后利用網(wǎng)絡(luò)的鄰接矩陣作為路徑選擇啟發(fā)函數(shù),采用最大最小蟻群算法不斷對模塊度函數(shù)進行優(yōu)化.迭代一定次數(shù)后,產(chǎn)生的路徑即解碼為最終的社區(qū)劃分.

LGA 算法以模塊度Q為目標(biāo)函數(shù),采用基于社區(qū)標(biāo)識的編碼方式,然后利用標(biāo)簽傳播法初始化種群,采用單路交叉、局部搜索變異LMA 和μ+λ選擇等3 個算子來探測網(wǎng)絡(luò)社區(qū)結(jié)構(gòu).

IDDE 算法的基本思想是先用標(biāo)簽傳播法初始化種群;然后借鑒差分進化算法基本特征,采用隨機單點變異、單路交叉和貪婪選擇策略生成中間種群,最后對執(zhí)行免疫克隆選擇操作,生成下一代種群.該算法融合離散差分進化算法的全局搜索能力和免疫克隆選擇策略的局部搜索能力,增加了算法的魯棒性.

CC-GA 算法通過使用聚類協(xié)同系數(shù)來初始化種群,以模塊度為適應(yīng)度函數(shù),利用遺傳中的統(tǒng)一交叉和提出的變異操作進行更新種群,該算法不需要預(yù)先知道社區(qū)的數(shù)量.可用于稠密和稀疏網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn).

1.3 Jaya 算法

Jaya 算法是近年來出現(xiàn)的一種元啟發(fā)式優(yōu)化算法.Jaya 這個詞在梵語中是勝利的意思.因為該算法力求達到最優(yōu)解從而取得勝利,因此命名為Jaya 算法[30].Jaya 算法中,第一步是隨機初始化規(guī)模大小為NP的種群,后續(xù)每一步不斷迭代,每次迭代中要完成從一個種群更新到下一個種群的任務(wù),直到滿足最大迭代次數(shù)為止.每一代種群要選出最好解和最差解用于更新種群中的每個個體解.種群中個體的更新采用下述公式:

其中,XB(t)和Xw(t)分別表示第t代種群中最好解和最差解,i表示種群中第i個 個體解.r1和r2每個個體更新時產(chǎn)生的0 到1 的隨機數(shù),用作縮放因子試圖增強算法的多樣性.式中+r1×(XB(t)-|Xi(t)|)表明個體X有朝著最優(yōu)個體靠近的趨勢,式中-r2×(Xw(t)-|Xt(t)|)則表明個體X有遠離最差個體的趨勢.在每一代種群個體更新過程中,如果種群中下一代個體Xi(t+1)的目標(biāo)函數(shù)值更優(yōu),則替代上一代個體Xi(t),否則,保持不變.

Jaya 與其它元啟發(fā)式優(yōu)化算法相比,簡單易理解,參數(shù)較少,只需要設(shè)定種群的大小和迭代的次數(shù).Jaya算法的流程圖如圖1.

圖1 Jaya 算法流程圖

2 離散Jaya 的社區(qū)發(fā)現(xiàn)算法

在本節(jié)中,我們主要介紹如何對Jaya 算法進行離散化.主要從社區(qū)的編碼和初始化、離散化策略以及算法偽代碼幾方面展開.

2.1 社區(qū)結(jié)構(gòu)的表示和初始化

社區(qū)結(jié)構(gòu)對應(yīng)網(wǎng)絡(luò)的劃分,其表示方式往往與算法相關(guān)且是影響算法效果的一個關(guān)鍵.社區(qū)發(fā)現(xiàn)的進化類算法中,一個社區(qū)結(jié)構(gòu)對應(yīng)的網(wǎng)絡(luò)劃分可以看作是一個個體.目前有兩種經(jīng)典的個體表示方法[32],一種是基于社區(qū)標(biāo)識符表示法LR (Label-based Representation),另外一種是局部鄰接表示LAR (Locus-based Adjacency Representation).本文采用局部鄰接表示法,在該表示法中,向量的元素值代表該節(jié)點的某個鄰居節(jié)點的節(jié)點標(biāo)識符.如圖2,網(wǎng)絡(luò)局部鄰接表示如表1,其對應(yīng)的網(wǎng)絡(luò)劃分見圖3.

圖2 一個網(wǎng)絡(luò)示例

圖3 表1對應(yīng)的局部鄰接表示所導(dǎo)出的網(wǎng)絡(luò)劃分

根據(jù)上述社區(qū)表示結(jié)構(gòu)方式,本文使用類似標(biāo)簽傳播思想的方法進行種群的初始化.在初始化過程中,首先使網(wǎng)絡(luò)中的每個節(jié)點都隨機選擇其中一個鄰居節(jié)點,每一次迭代中,如果節(jié)點i的鄰居節(jié)點出現(xiàn)的次數(shù)最多,則該鄰居節(jié)點作為節(jié)點i的值;如果鄰居節(jié)點出現(xiàn)的次數(shù)一樣,則隨機選擇一個鄰居節(jié)點.

2.2 離散化策略

Jaya 算法適用于求解連續(xù)性的最優(yōu)化的問題.Jaya 算法的主要思想是通過遠離最差解,靠近最優(yōu)解更新種群.社區(qū)發(fā)現(xiàn)是一個離散型的組合優(yōu)化問題.當(dāng)使用個體向量表示社區(qū)的一個劃分時,該向量中的每一個元素代表一個節(jié)點,如果利用Jaya 算法對個體向量更新,如對個體向量的作差運算,但節(jié)點之間的作差運算并無意義.為了采用Jaya 算法的思想求解社區(qū)結(jié)構(gòu)劃分問題,我們需要對Jaya 算法做離散化處理,為此先引入幾個概念.

(1)傾向性

為了判斷種群中的個體是更靠近最優(yōu)解個體還是更靠近最差解個體,本文提出傾向性判斷公式:

Q(Xbest),Q(Xworst),Q(X)分別表示最優(yōu)個體的模塊度、最差個體的模塊度、當(dāng)前個體的模塊度,bestGap表示當(dāng)前個體模塊度和最優(yōu)模塊度的差值,worstGap表示當(dāng)前個體模塊度和最差模塊度的差值,Gap表示當(dāng)前個體在最優(yōu)個體和最差個體之間的傾向性.當(dāng)Gap＞0,則該個體傾向于最差個體,當(dāng)Gap＜0,則傾向于最優(yōu)個體.

(2)最優(yōu)相似率

最優(yōu)相似率即當(dāng)前個體向量與最優(yōu)解個體向量相同節(jié)點個數(shù)占全部元素的比率,其計算公式如下:

其中,Xd表示當(dāng)前個體,表示最優(yōu)解個體,n表示節(jié)點個數(shù),d表示該個體中元素的序數(shù),Θ表示同或,如果Xd和相等,則結(jié)果為1,否則為0.

(3)模塊度函數(shù)的局部更新

為了使得模塊度函數(shù)最大化,我們定義一種模塊度函數(shù)的局部貪心更新方式.通過依次遍歷該節(jié)點的鄰居節(jié)點,選擇模塊度最大化的鄰居節(jié)點進行替代.第t+1 代的個體更新用式(7)表示如下:

其中,X表示一個個體向量解(向量的元素對應(yīng)圖中的節(jié)點),t表 示第t次 迭代,Q為對應(yīng)式(1)的模塊度函數(shù),Neighbord={n1,n2,···,nk}為 節(jié)點d的鄰居節(jié)點集合.式(7)表示取最大模塊度的鄰居節(jié)點作為下一代個體的節(jié)點更新.

(4)貪心選擇

當(dāng)個體更新后,選取適應(yīng)度較高的個體作為下一代的父種群個體,即貪心選擇.該操作相當(dāng)于遺傳中的“優(yōu)勝劣汰”,同時和Jaya 算法保持了一致的篩選策略,對比非貪心選擇策略,即優(yōu)化后的個體不進行比較直接作為下一代,選用貪心選擇策略保證了下一代種群中每一個個體都至少不會變得更差,從而使解的平均質(zhì)量更優(yōu),加快了收斂速度.

基于上述幾個概念,下面給出Jaya 算法離散化策略,離散化的Jaya 算法稱作DJaya 算法.DJaya 算法通過式(3)～式(5)來判斷種群中每個個體是靠近種群的最優(yōu)解還是最差解,從而對種群中的個體離散化為兩類.①對于種群中更靠近最差解的個體,采用類似標(biāo)簽傳播的方法依次對該個體的各個節(jié)點進行更新操作,該操作提高了較差個體的多樣性和精度,達到了進一步遠離最差解的效果,有利于DJaya 算法的全局探索性.②對于種群中靠近最優(yōu)解的個體,先對該個體向量采用式 (6)計算出最優(yōu)相似率,然后基于相似率對該個體的某些節(jié)點采用式 (7)進行局部更新,該操作有利于加快種群的優(yōu)化速度,使整個種群更加靠近最優(yōu)解,從而有利于增強DJaya 算法的局部開發(fā)性.

DJaya 算法通過判定種群中個體的傾向性來平衡各個階段的全局搜索能力和局部搜索能力,當(dāng)個體靠近最優(yōu)個體解,采取類似標(biāo)簽傳播方法進行更新,相當(dāng)于重新定義初始解,有利于探索出最優(yōu)解,體現(xiàn)了全局搜索能力;當(dāng)算法靠近最有個體解,采取了基于局部函數(shù)的更新方法,進一步優(yōu)化了精英解,加快了算法收斂,體現(xiàn)了局部搜索能力.

(5)隨機抖動

為了更進一步避免算法陷入全局較優(yōu),我們加入了隨機抖動操作,相當(dāng)于遺傳算法中的變異操作,是一種局部開發(fā),有利于增加搜索方向,增大搜索空間.當(dāng)連續(xù)迭代幾次后種群中的個體沒有得到優(yōu)化,則執(zhí)行隨機抖動,即隨機選擇該個體節(jié)點的某個鄰居節(jié)點值替代當(dāng)前個體節(jié)點值.該操作設(shè)置了一個較小的抖動率,一方面保持原始種群的較優(yōu)性,另一方面增加多樣性.

2.3 DJaya 算法流程

綜上,通過選取模塊度為適應(yīng)度函數(shù),采用LAR表示種群的劃分和類似LPA 策略進行初始化,然后在每代種群更新中采用離散化的DJaya 算法進行不斷的迭代優(yōu)化,選取適應(yīng)度高的個體作為下一代的父種群.算法DJaya 的描述如算法1.

算法1.DJaya 算法輸入:G,M,T,R//G表示網(wǎng)絡(luò),M表示種群規(guī)模,T表示最大迭代次數(shù),R表示隨機抖動率輸出:Result// 網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)1.Begin 2.P←LAR 進行表示,并用LPA 初始化父種群P(new)←? 3.//子種群初始化為空集4.Fori= 1:T5.Forj= 1:M6.Gap(j)← 利用式(3)～(5)判斷個體傾向性7.IfGap(j)＞ 0 //靠近最差個體8.P(new)←LPA(j)//類似標(biāo)簽傳播法更新9.Else //靠近最優(yōu)個體10.If rand ()＜ similarRate (j)//滿足最優(yōu)相似率11.P(new)←利用公式(7)更新P(new)←P(new)∪P12.//更優(yōu)個體進入下一代13.Ifrand()＜RP(new)←14.隨機抖動15.End ForP←P(new)16.//生成新的種群17.End ForResult←18.選擇P中適應(yīng)度最高的個體19.End

下面分析DJaya 算法的時間復(fù)雜度.假設(shè)網(wǎng)絡(luò)中G=(V,E)的節(jié)點個數(shù)為n,種群規(guī)模為M,迭代次數(shù)為T.使用局部鄰接表示法初始化種群時,對于每個節(jié)點隨機選擇其中一個節(jié)點值賦值,設(shè)網(wǎng)絡(luò)的節(jié)點平均度為,則該初始化種群的其時間復(fù)雜度為O ();利用DJaya 算法離散策略對種群進行更新時,計算模塊度函數(shù)的時間復(fù)雜度為 O(Mn2),如果個體靠近最差解,則利用類似標(biāo)簽傳播法進行更新,其時間復(fù)雜度為O(T M×(+n2));如果個體靠近優(yōu)解,則采用局部函數(shù)進行更新,其時間復(fù)雜度為因此,DJaya 算法的時間復(fù)雜度為

3 實驗結(jié)果與分析

實驗平臺為Windows 10 系統(tǒng),Intel(R)Core(TM)i5 CPU 1.8 GHz,內(nèi)存8.0 GB.實驗數(shù)據(jù)包括不同參數(shù)情況下的擴展GN Benchmark[33]人工網(wǎng)絡(luò) 和4 個經(jīng)典真實網(wǎng)絡(luò).實驗中將DJaya 算法與LPA,FMM,BGLL等經(jīng)典貪心算法,以及智能算法如ACO、LGA、IDDE、CC-GA 進行比較.為了減少統(tǒng)計誤差,每個算法在每個算例上獨立運行20 次,取平均值作為算法運行的結(jié)果.

按照慣例,針對人工網(wǎng)絡(luò),已知其真實社區(qū)結(jié)構(gòu),實驗中僅比較各算法的標(biāo)準(zhǔn)互信息值;對于真實的網(wǎng)絡(luò),我們比較不同算法的模塊度值[34].

標(biāo)準(zhǔn)互信息(Normalized Mutual Information,NMI)[35]常用來評價算法的劃分結(jié)果與網(wǎng)絡(luò)真實劃分結(jié)果的吻合程度.對于網(wǎng)絡(luò)的的兩種劃分A和B,它們之間的互信息定義如下:

其中,N表示節(jié)點個數(shù).CA表示劃分A中網(wǎng)絡(luò)的社區(qū)數(shù)目,CB表示劃分B中網(wǎng)絡(luò)的社區(qū)數(shù)目,Ci,表示第i行元素和,C,j表示第j列元素之和,Ci,j表示劃分A中的社區(qū)i和劃分B中的社區(qū)j兩者之間的交集中含有的節(jié)點數(shù)目.如果A=B,則NMI值為1,如果A劃分和B劃分完全不同,則NMI值為0.

3.1 人工網(wǎng)絡(luò)比較實驗

為了分析DJaya 算法的優(yōu)化性能,我們在擴展GN Benchmark 上進行了實驗分析.該人工網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)已知,它含有128 個節(jié)點,共劃分為4 個不同的社區(qū),每個社區(qū)有32 個節(jié)點,社區(qū)中每個節(jié)點的平均度數(shù)為16,如表2.網(wǎng)絡(luò)中的混合參數(shù)u主要用于確定某一社區(qū)中任意一個節(jié)點與其他社區(qū)的節(jié)點之間共享邊的數(shù)量,當(dāng)混u＜ 0.5 時,網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)較為明顯,但隨著u的增大,網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)將變得越來越模糊,性能一般的算法難以檢測出網(wǎng)絡(luò)中存在的社區(qū)結(jié)構(gòu),從而可以區(qū)分不同算法的性能,比較結(jié)果如圖4.

表2 人工網(wǎng)絡(luò)的參數(shù)(GN benchmark)

由圖4可見,當(dāng)u＜0.35時候,各個算法的NMI值達到了1,都能準(zhǔn)確找出社區(qū)結(jié)構(gòu);當(dāng)u=0.4,BGLL、ACO 算法的NMI開始下降;當(dāng)u=0.45,LGA、IDDE、DJaya 算法能找到和真實社區(qū)完全一樣的社區(qū)結(jié)構(gòu),相比其它算法,它們較為穩(wěn)定;當(dāng)u=0.5,此時網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)已經(jīng)非常模糊,DJaya 算法仍能準(zhǔn)確劃分接近80%的社區(qū)結(jié)構(gòu),表明DJaya 算法的一定優(yōu)越性,總體來說DJaya 算法在人工網(wǎng)絡(luò)上優(yōu)于其它算法.

圖4 各種算法劃分精度的比較

3.2 真實網(wǎng)絡(luò)比較實驗

真實的復(fù)雜網(wǎng)絡(luò)與人工網(wǎng)絡(luò)相比,有不同的拓?fù)鋵傩?這里采用了4 個被廣泛使用的真實網(wǎng)絡(luò)作為實驗數(shù)據(jù)集,其點數(shù)和邊數(shù)見表3.Karate[36]網(wǎng)絡(luò)是通過對一個美國大學(xué)空手道俱樂部進行觀測而構(gòu)建出的一個社會網(wǎng)絡(luò).Dolphins[37]是由Lusseau 等使用長達7年的時間觀察新西蘭Doubtful Sound 海峽62 只海豚群體的交流情況而得到的海豚社會關(guān)系網(wǎng)絡(luò).Polbooks[6]是由Amazon 上銷售的美國政治相關(guān)書籍頁面上建立起來的網(wǎng)絡(luò).Football[1]網(wǎng)絡(luò)是根據(jù)美國大學(xué)生足球聯(lián)賽而創(chuàng)建的一個復(fù)雜的社會網(wǎng)絡(luò).

表3 4 個真實網(wǎng)絡(luò)數(shù)據(jù)的參數(shù)

表3中,football 真實社區(qū)的劃分效果與DJaya 算法劃分的效果圖分別如圖5和圖6.

如圖5,football 對應(yīng)的真實社區(qū)有12 個,圖6采用DJaya 算法劃分的社區(qū)則有10 個,可以看出DJaya算法合并了一些較小的社區(qū),保持了大部分社區(qū)劃分是和真實社區(qū)一致,文獻[2]認(rèn)為這種劃分是合理的.

表4給出了各種算法在4 個標(biāo)準(zhǔn)真實網(wǎng)絡(luò)算例上所得的模塊度值.對于算例Karate,CC-GA、LGA、DJaya 都達到0.4198 最優(yōu)值[38];在算例Dolphins 上DJaya 算法取得了最高的模塊度值;在算例polbooks上,DJaya 和LGA 都達到了該數(shù)據(jù)集的理論最高值0.5272[39];在算例football上,LGA、IDDE、DJaya 都表現(xiàn)良好,達到了最優(yōu)值[39].綜上所述,在4 個算例上,DJaya 算法展現(xiàn)出較明顯優(yōu)勢.

圖5 真實的football 的社區(qū)(12 個社區(qū))

圖6 DJaya 劃分的football 社區(qū)(10 個社區(qū))

4 總結(jié)

本文提出的DJaya 算法用于求解復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題,該算法采用局部鄰接表示法的編碼方式對種群進行社區(qū)表示,并用標(biāo)簽傳播思想進行初始化,然后借鑒連續(xù)空間Jaya 算法的靠近最優(yōu)解、遠離最差解的基本思想,先判斷種群個體的傾向性,針對靠近最差解采用標(biāo)簽傳播思想更新種群,靠近最優(yōu)解采用局部模塊度函數(shù)更新種群,最后采用貪心選擇策略生成下一代種群.DJaya 算法實現(xiàn)簡單,容易理解,具有全局搜索能力和局部開發(fā)能力.通過在真實網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上的實驗對比發(fā)現(xiàn),該算法具有較好的優(yōu)化能力和魯棒性,達到了較高的社區(qū)發(fā)現(xiàn)精度且自動確定社區(qū)個數(shù).該算法適用于非重疊、靜態(tài)社區(qū),考慮到模塊度作為優(yōu)化函數(shù)的局限性[39],今后將改進算法的目標(biāo)函數(shù),或建立多目標(biāo)優(yōu)化函數(shù),同時考慮擴展算法的適應(yīng)范圍,增大數(shù)據(jù)規(guī)模,應(yīng)用在重疊、動態(tài)社區(qū)發(fā)現(xiàn)問題.

表4 各種算法在不同網(wǎng)絡(luò)中的模塊度對比