周春霞,周井泉,常瑞云

(南京郵電大學 電子科學與工程學院，江蘇 南京 210003)

基于Memetic算法的多目標復(fù)雜網(wǎng)絡(luò)社區(qū)檢測

周春霞,周井泉,常瑞云

(南京郵電大學 電子科學與工程學院，江蘇 南京 210003)

文中研究復(fù)雜網(wǎng)絡(luò)社區(qū)檢測機制，提出了一種基于Memetic算法的多目標社區(qū)檢測算法。為了提高種群多樣性、減少搜索空間和提高算法效率,算法采用標簽啟發(fā)式快速傳播的初始化策略，混合交叉，在每個社區(qū)中選擇一個節(jié)點變異等優(yōu)化兩個目標函數(shù)，即Improved Ratio Association (IRA)和Ratio Cut (RC)，將多目標優(yōu)化問題轉(zhuǎn)化成同時最小優(yōu)化這兩個目標函數(shù)；在局部搜索中利用權(quán)重和將兩個目標函數(shù)構(gòu)成一個局部優(yōu)化目標并采用爬山搜索來尋找個體最優(yōu)。針對計算機合成網(wǎng)絡(luò)與兩個經(jīng)典真實網(wǎng)絡(luò)的實驗結(jié)果表明，與四個基于EA的算法和Fast modularity算法相比，基于Memetic算法的多目標復(fù)雜網(wǎng)絡(luò)社區(qū)檢測機制在解決復(fù)雜網(wǎng)絡(luò)社區(qū)檢測問題上具有一定優(yōu)勢。

Memetic算法；混合交叉；局部搜索；多目標；網(wǎng)絡(luò)社區(qū)檢測

1 概 述

由于許多復(fù)雜的系統(tǒng)包括協(xié)作網(wǎng)絡(luò)[1]、萬維網(wǎng)[2]等都可以建模為復(fù)雜網(wǎng)絡(luò)。因此，近年來復(fù)雜網(wǎng)絡(luò)成為人們的關(guān)注熱點。除了許多顯著的性質(zhì)，如小世界性、無尺度性和高聚類系數(shù)外，社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的另一個重要屬性，它將一個復(fù)雜網(wǎng)絡(luò)分成不同的分區(qū)，每一個這樣的分區(qū)稱為一個社區(qū)[3]。定性來看，社區(qū)的定義是網(wǎng)絡(luò)中一些節(jié)點的集合，這些節(jié)點以相互連接的模式存在，在同一分區(qū)的節(jié)點間聯(lián)系密切，不在同一分區(qū)的節(jié)點間聯(lián)系比較稀疏，屬于同一社區(qū)的節(jié)點通常來說會有相同的屬性[4]。因此在復(fù)雜網(wǎng)絡(luò)中進行社區(qū)檢測非常必要。

到目前為止，已經(jīng)開發(fā)了許多網(wǎng)絡(luò)社區(qū)檢測的算法。

一類是基于啟發(fā)式的，這類算法通過基于某些直觀的假設(shè)或啟發(fā)式規(guī)則來找到網(wǎng)絡(luò)的各個社區(qū)，如Girvan-Newman (GN)算法[3]，快速的標簽傳播算法(LPA)[5]等。GN算法不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊，直到網(wǎng)絡(luò)中所有的邊都被移除。邊介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過每條邊的最短路徑數(shù)目，算法彌補了一些傳統(tǒng)算法的不足，能夠從網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行分析；LPA算法首先為每個節(jié)點指派唯一標簽，再將每個節(jié)點的標簽更新為其鄰節(jié)點出現(xiàn)次數(shù)最多的標簽，如果存在多個相同的最多標簽，則隨機選擇一個作為更新值，若干次迭代后密集相連的節(jié)點會收斂于同一標簽，最終，具有相同標簽的節(jié)點歸為一個社區(qū)。LPA算法的優(yōu)點在于不需要任何參數(shù)輸入，而且算法具有線性的時間復(fù)雜度為O(m)，m為網(wǎng)絡(luò)的邊數(shù)。

另一類是基于模塊度的優(yōu)化算法，Newman等通過引入一個衡量網(wǎng)絡(luò)劃分質(zhì)量的指標：標準模塊度(Q)[3]，依據(jù)Q值評價網(wǎng)絡(luò)社區(qū)劃分的優(yōu)劣，從而將社區(qū)檢測轉(zhuǎn)化為一個優(yōu)化問題。典型的算法有Newman快速算法[6]、Fastmodularity算法[7]等。Newman快速算法將每個節(jié)點看作是一個社區(qū)，每次迭代選擇產(chǎn)生最大Q值的兩個社區(qū)合并，直至整個網(wǎng)絡(luò)融合成一個社區(qū)；Fastmodularity算法的基本思想是用貪婪優(yōu)化算法優(yōu)化模塊度這個目標函數(shù)，得到最大的模塊度值即找到了最優(yōu)的網(wǎng)絡(luò)社團劃分。

然而，F(xiàn)ortunato和Barthelemy在文獻[8]中指出以標準模塊度優(yōu)化的算法存在分辨率限制的問題。為了克服這個問題，Pizzuti在文獻[9]中提出以社團得分(CS)為目標函數(shù)來檢測網(wǎng)絡(luò)劃分的算法GA-net。Li等引入了模塊度密度作為指標函數(shù)，通過調(diào)節(jié)參數(shù)能從不同分辨率分析網(wǎng)絡(luò)拓撲結(jié)構(gòu)[10]。但是研究者往往想到將多目標優(yōu)化引用到復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)檢測中。與單目標優(yōu)化問題不同的是，多目標優(yōu)化問題需要同時優(yōu)化多個目標函數(shù)，通常沒有單一的全局最優(yōu)解，而是一系列互不支配的解，稱為Pareto解，多目標優(yōu)化算法的目的正是尋找出一系列互不支配的解[1]。進化算法通過種群中代與代之間相關(guān)聯(lián)的解來實現(xiàn)全局搜索，對于搜索多目標優(yōu)化問題的Pareto最優(yōu)解集非常有效。最近提出的多目標進化社區(qū)檢測方法有MOGA-net[11]、MOCD[12]和MOEA/D-net[13]等。

Memetic算法是在種群的全局搜索基礎(chǔ)上再對個體進行局部搜索，實際上，Memetic算法提出的是一種框架，在這個框架下，采用不同的搜索策略可以構(gòu)成不同的Memetic算法。如全局搜索策略可以采用遺傳算法、免疫算法等，局部搜索策略可以采用爬山搜索、模擬退火、貪婪算法、禁忌搜索、導(dǎo)引式局部搜索等。

文中提出了一種基于Memetic算法的多目標復(fù)雜網(wǎng)絡(luò)社區(qū)檢測機制(MOME)，全局搜索中采用遺傳算法框架；在局部搜索中利用權(quán)重和將兩個目標函數(shù)折合成一個目標并采用爬山搜索來尋找個體最優(yōu)。在遺傳框架中采用標簽啟發(fā)式快速傳播的初始化方式、個體統(tǒng)一標簽后的混合交叉和針對社區(qū)檢測的變異策略，將MOME算法運用在計算機合成網(wǎng)絡(luò)與兩個經(jīng)典真實網(wǎng)絡(luò)，并同時與四個基于EA的算法和Fastmodularity算法進行比較，其在社區(qū)檢測方面更具有競爭力、準確性更高。

2 基于Memetic算法的多目標復(fù)雜網(wǎng)絡(luò)社區(qū)檢測

2.1 社區(qū)的定義

社區(qū)指網(wǎng)絡(luò)中存在的節(jié)點子集，該子集的內(nèi)部節(jié)點之間具有相對緊密的連接，子集內(nèi)部節(jié)點與外部節(jié)點具有相對稀疏的連接。Radicchi等在文獻[14]中基于節(jié)點度的概念給出了社區(qū)結(jié)構(gòu)的定性描述：若S是網(wǎng)絡(luò)G的一個社區(qū)，那么S中節(jié)點i的度為其內(nèi)度與外度之和。其中內(nèi)度是節(jié)點i與內(nèi)其余節(jié)點連接的總數(shù)，外度是節(jié)點i與以外節(jié)點連接的總數(shù),可表示為：

(1)

2.2 目標函數(shù)

Newman等在2002年引進了一個衡量網(wǎng)絡(luò)劃分質(zhì)量的標準模塊度(Q)[3]，將網(wǎng)絡(luò)社區(qū)檢測轉(zhuǎn)化為一個優(yōu)化問題，Q的定義如下：

(2)

然而，F(xiàn)ortunato和Barthelemy在文獻[8]中指出模塊度優(yōu)化存在分辨率限制問題，其主要原因是模塊度中不在一個社區(qū)中包含社區(qū)中節(jié)點總數(shù)的信息。為解決這個主要問題，Li等在文獻[10]中引入了新的指標函數(shù)：模塊度密度(D)。

(3)

式中，第一個求和項表示子圖節(jié)點的內(nèi)度之和與該子圖的節(jié)點數(shù)的比值,等價于RatioAssociation(RA)[15]；第二個求和項表示子圖節(jié)點的外度之和與該子圖的節(jié)點數(shù)的比值，等價于RatioCut(RC)[16]。

從定義知，D值越大，找到的社區(qū)劃分就越準確。即RA越大，社區(qū)內(nèi)節(jié)點間的連接越密切，RC越小社區(qū)間節(jié)點間的連接越稀疏。這兩個互補的項反映了一個好社區(qū)的兩個基本方面，社團內(nèi)連接是密切的而社區(qū)間的聯(lián)系是稀疏的。

文中為了把社區(qū)檢測轉(zhuǎn)化成最小多目標優(yōu)化問題，對RA做了修正，提出了ImprovedRatioAssociation(IRA)，定義為：

(4)

其中，σ為一實數(shù)(文中取值為5)。

通過最小化IRA和RC這兩個目標函數(shù)可以確保社區(qū)內(nèi)連接是密切的而社區(qū)間的聯(lián)系是稀疏的。

(5)

2.3 算法描述

2.3.1 編碼方式

2.3.2 種群的初始化

開始時每個節(jié)點被放到一個不同的社區(qū)中，即xi=i，為了避免所有個體的標簽都是這樣，同時提高種群的多樣性，文中采用了基于標簽傳播的初始化機制。首先初始化每個節(jié)點具有不同的標簽，即xi=i；第二步每個節(jié)點再基于與其有邊連接關(guān)系的鄰居節(jié)點標簽更改其自身的標簽，在這次更改中每個節(jié)點的新標簽是它鄰居節(jié)點標簽中數(shù)量最多的，若鄰居節(jié)點標簽都不一致，那隨機選擇一個來更改；最后一步是將這個過程反復(fù)進行5次。

這樣緊密連接的節(jié)點通過標簽傳播，可以迅速形成一個共同的獨特的標簽，創(chuàng)造的個體具有較高的聚類精度，同時豐富了種群多樣性。

2.3.3 交叉和變異

這種混合交叉操作既體現(xiàn)了繼承性，又同樣具有探索性，使產(chǎn)生的子代個體能夠攜帶兩個父代個體的共同特征。

變異：在變異中，首先根據(jù)個體上節(jié)點的標簽得到社區(qū)結(jié)構(gòu)，其次在每一個社區(qū)中隨機選擇一個節(jié)點，然后將這個節(jié)點的標簽隨機地變?yōu)槠淙我忄従庸?jié)點的標簽。這種變異操作只考慮待變異節(jié)點的鄰居節(jié)點，操作相對簡單，同時又能夠?qū)⒚恳粋€社區(qū)考慮在內(nèi)，縮小了搜索空間，減少了無效搜索，提高了算法效率。

2.3.4 局部搜索

Memetic算法框架是由種群的全局搜索和個體的局部啟發(fā)式搜索結(jié)合而成，其搜索效率在一些領(lǐng)域比傳統(tǒng)遺傳算法快幾個數(shù)量級，并且能夠克服傳統(tǒng)遺傳算法收斂速度慢、容易陷入局部最優(yōu)的缺點。局部搜索是在種群進行全局搜索后的基礎(chǔ)上進行，但是并不是種群中的所有個體都進行局部搜索，在單目標中選擇遺傳操作后適應(yīng)度值最大的個體進行，以適應(yīng)度的值作為局部優(yōu)化函數(shù)，直到尋找到一個局部最優(yōu)的個體，在多目標中首先要確定一個局部優(yōu)化函數(shù)將多個目標通過某種方式結(jié)合在一起，并且將遺傳操作后的Pareto解作為局部搜索對象，通過局部搜索產(chǎn)生Pareto最優(yōu)解。

文中全局搜索采用了遺傳算法的框架，在局部搜索策略中選擇采用爬山法。爬山法是一種常用于局部搜索的優(yōu)化方法，通常從問題當前的一個任意解出發(fā)，試圖通過改變這個解的某個元素來尋求更好解，一旦這個變化產(chǎn)生了一個更好的解，那么這個新解就替代被選擇出來的解，這個過程一直重復(fù)直到?jīng)]有更好的解產(chǎn)生或者達到最大的搜索次數(shù)為止，此時的解就是一個局部最優(yōu)解。

MOME中多目標優(yōu)化算法的局部搜索采用權(quán)重和的方式將兩個不同的目標函數(shù)構(gòu)成局部搜索的優(yōu)化函數(shù)，如式(6)：

(6)

局部搜索策略中選擇爬山搜索，一旦搜索出比當前優(yōu)化函數(shù)值小的解就將搜索出的解代替當前解，這個過程一直重復(fù)直到?jīng)]有更好的解產(chǎn)生或者達到最大的搜索次數(shù)為止，將對應(yīng)的解作為當前代社區(qū)檢測的最優(yōu)解。

3 實驗研究

本節(jié)將MOME應(yīng)用于計算機合成網(wǎng)絡(luò)與已知真實劃分的兩個真實世界網(wǎng)絡(luò)，并且分別與不同算法得到的檢測結(jié)果進行了比較。實驗中使用由LeonDanon等提出的評價指標函數(shù)NormalizedMutualInformation(NMI)[17]作為相似性度量，用來衡量算法檢測的結(jié)果與真實的網(wǎng)絡(luò)劃分之間的相似度。實驗結(jié)果表明，MOME算法能夠有效地檢測出網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，發(fā)現(xiàn)網(wǎng)絡(luò)社區(qū)的層次結(jié)構(gòu)，同時具有多分辨能力。

3.1 人工合成網(wǎng)絡(luò)

使用Lancichinetti提出的基準測試網(wǎng)絡(luò)[18]。該網(wǎng)絡(luò)包含128個節(jié)點，4個社區(qū)，每個社區(qū)有32個節(jié)點，節(jié)點的平均度為16，混合參數(shù)μ控制節(jié)點外度所占的比例，μ越大，節(jié)點和其社區(qū)外節(jié)點的連接比例越大，社區(qū)結(jié)構(gòu)越模糊。實驗中調(diào)節(jié)μ的值，生成μ從0到0.5變化(間隔為0.05)的11個網(wǎng)絡(luò)，并且使用NMI衡量真實網(wǎng)絡(luò)劃分和檢測結(jié)果之間的相似性。針對個網(wǎng)絡(luò)，計算30次獨立運行結(jié)果中最大的NMI的平均值，圖1給出了實驗結(jié)果。

圖1 5種不同算法在人工合成的 11個網(wǎng)絡(luò)上得到的NMI的值

從圖中可以看出，當混合參數(shù)μ<0.35時，代表社區(qū)結(jié)構(gòu)比較明顯，MOME算法能夠發(fā)現(xiàn)網(wǎng)絡(luò)的真實劃分(NMI值為1)，很明顯結(jié)果優(yōu)于GA-net、MOGA-net和MOCD算法；隨著混合參數(shù)逐漸增大，網(wǎng)絡(luò)的社團結(jié)構(gòu)越來越模糊，尋找到真實的社區(qū)結(jié)構(gòu)變得越來越困難，取0.35<μ<0.45，雖然完全檢測出真實的劃分變得有些困難，但NMI的值依然會高于0.85，相比其他算法的優(yōu)勢還是很明顯；當再增大時，社團結(jié)構(gòu)變得更模糊，檢測出真實的劃分變得十分困難，例如，對于混合參數(shù)μ=0.5的網(wǎng)絡(luò)，網(wǎng)絡(luò)社團結(jié)構(gòu)很模糊，任何算法都很難檢測出網(wǎng)絡(luò)的真實劃分。這個實驗說明MOME算法能夠發(fā)現(xiàn)有效的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)信息。

3.2 真實的網(wǎng)絡(luò)

將MOME算法應(yīng)用到兩個真實的世界網(wǎng)絡(luò)上，分別是Zachary空手道俱樂部網(wǎng)絡(luò)[19]和美國大學足球聯(lián)賽網(wǎng)絡(luò)[3]，并與Fast modularity算法得到的檢測結(jié)果進行了比較。

Zachary空手道俱樂部網(wǎng)絡(luò)是Zachary在兩年時間內(nèi)通過觀察一個34個成員的空手道俱樂部得到的[19]。圖2(a)記錄Karate Club真實的社區(qū)劃分結(jié)果，圖2(b)表明了MOME算法在Karate Club上的社區(qū)檢測結(jié)果。

從圖2(b)中可以清楚地看到，MOME算法能夠完全正確地檢測出Karate Club的社區(qū)劃分結(jié)果(對應(yīng)的NMI=1)，同時也顯示了最高的Q值對應(yīng)的社區(qū)結(jié)構(gòu)，很明顯圖2(b)中右圖為左圖的子圖。

美國大學足球聯(lián)賽網(wǎng)絡(luò)是Girvan和Newman編譯的2000年秋季美國IA部大學足球聯(lián)賽常規(guī)賽季比賽網(wǎng)絡(luò)[3]。圖3(a)記錄了Football的真實社區(qū)劃分結(jié)果，圖3(b)表明了MOME算法在Football上檢測結(jié)果。

由于網(wǎng)絡(luò)本身存在復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，很難有一種算法能夠完整地檢測出其真實的社區(qū)劃分。從圖3(b)最大Q值的檢測結(jié)果來看，MOME算法產(chǎn)生了10個社區(qū)，通過觀察發(fā)現(xiàn)錯誤地放置了一些節(jié)點，如：12，25，29，37，43，51,59，60，64，70，81，83，91，98，111。然而從圖3(b)NMI最大值為0.927 3來看，MOME算法依然是有效的。

為了比較，表1中列出了MOME算法和Fastmodularity算法[7]在這兩個網(wǎng)絡(luò)上獨立運行30次得到的平均NMI的值。

表1 MOME算法和Fast modularity算法對網(wǎng)絡(luò)檢測的結(jié)果

圖2 檢測結(jié)果(1)

從表中可以看到，對于Zachary空手道俱樂部網(wǎng)絡(luò)，MOME算法能夠完整地檢測出網(wǎng)絡(luò)的真實劃分，而Fastmodularity算法檢測出的解對應(yīng)的NMI值為0.693，顯然MOME算法要優(yōu)于Fastmodularity算法；對于美國大學足球聯(lián)賽網(wǎng)絡(luò)，由于網(wǎng)絡(luò)本身結(jié)構(gòu)的復(fù)雜性，兩種算法都不能夠完全檢測出其真實的劃分結(jié)果。但從表中對比可以得到，MOME算法在NMI的取值上高于Fastmodularity算法，檢測到的社區(qū)結(jié)構(gòu)更接近于網(wǎng)絡(luò)的真實社區(qū)結(jié)構(gòu)。通過和Fastmodularity算法的比較，可以發(fā)現(xiàn)MOME算法在解決復(fù)雜網(wǎng)絡(luò)社團檢測問題上更精確。

通過以上實驗得出MOME算法在社區(qū)檢測問題上的有效性，其檢測結(jié)果也要優(yōu)于基于EA算法的其他方法，與常見的檢測算法如Fastmodularity算法相比，結(jié)果同樣具有競爭力。

4 結(jié)束語

文中提出了MOME算法，該算法基于快速標簽傳播算法設(shè)計了標簽啟發(fā)式傳播的初始化策略，提高了種群多樣性；在交叉中采用對所有個體統(tǒng)一標簽后的混合交叉策略；變異中在每個社區(qū)中選擇一個節(jié)點進行變異，提高算法效率；最后通過優(yōu)化IRA和RC兩個目標函數(shù)來尋找Pareto解。在局部搜索中利用權(quán)重和將兩個目標函數(shù)構(gòu)成一個局部優(yōu)化目標并采用爬山搜索策略來搜尋個體最優(yōu)。

在人工合成網(wǎng)絡(luò)和真實的世界網(wǎng)絡(luò)上的實驗結(jié)果表明，MOME算法比傳統(tǒng)的基于EA的算法在社區(qū)檢測方面更具有競爭力，與當前比較流行的Fastmodularity算法比較的結(jié)果顯示，MOME算法的準確性更高。所以基于Memetic算法的多目標復(fù)雜網(wǎng)絡(luò)社區(qū)檢測機制在解決復(fù)雜網(wǎng)絡(luò)社區(qū)檢測問題上具有一定優(yōu)勢。

[1]NewmanMEJ.Thestructureofscientificcollaborationnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2001,98:404-409.

[2]BroderA,KumarR,MaghoulF,etal.GraphstructureintheWeb[J].ComputerNetworks,2000,33:309-320.

[3]GirvanM,NewmanMEJ.Communitystructureinsocialandbiologicalnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2002,99:7821-7826.

[4]FortunatoS.Communitydetectioningraphs[J].PhysicsReports-ReviewSectionofPhysicsLetters,2010,486:75-174.

[5]RaghavanUN,AlbertR,KumaraS.Nearlineartimealgorithmtodetectcommunitystructuresinlarge-scalenetworks[J].PhysRevE,2007,76(3):036106.

[6]NewmanMEJ.Fastalgorithmfordetectingcommunitystructureinnetworks[J].PhysicalReviewE,2004,69:066133.

[7]ClausetA.Findinglocalcommunitystructureinnetworks[J].

Physical Review E,2005,72:026132.

[8] Fortunato S,Barthelemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences of the United States of America,2007,104:36-41.

[9] Pizzuti C.GA-Net:a genetic algorithm for community detection in social networks[C]//Proc of PPSN X.[s.l.]:[s.n.],2008:1081-1090.

[10] Li Z,Zhang S,Wang R S,et al.Quantitative function for community detection[J].Physical Review E - Statistical,Nonlinear,and Soft Matter Physics,2008,77:036109.

[11] Pizzuti C.A multiobjective genetic algorithm to find communities in complex networks[J].IEEE Transactions on Evolutionary Computation,2012,16(3):418-430.

[12] Shi C,Yan Z,Cai Y,et al.Multi-objective community detection in complex networks[J].Applied Soft Computing,2012,12(2):850-859.

[13] Gong M,Ma L,Zhang Q,et al.Community detection in networks by using multiobjective evolutionary algorithm with decomposition[J].Physica a-Statistical Mechanics and Its Applications,2012,391:4050-4060.

[14] Radicchi F,Castellano F,Ceccon I,et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658-2663.

[15] Angelini L,Boccaletti S,Marinazzo D,et al.Identification of network modules by optimization of ratio association[J].Chaos,2007,17:023114.

[16] Wei Y C,Cheng C K.Ratio cut partitioning for hierarchical designs[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,1991,10(7):911-921.

[17] Wu F,Huberman B A.Finding communities in linear time:a physics approach[J].The European Physical Journal B-Condensed Matter and Complex Systems,2004,38:331-338.

[18] Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78:046110.

[19] Zachary W W.An information flow model for conflict and fission in small groups[J].J Anthropol Res,1977,33:452-473.

Multi-objective Complex Network Community Detection Based on Memetic Algorithm

ZHOU Chun-xia，ZHOU Jing-quan，CHANG Rui-yun

(College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The complex network community detection mechanism was studied and a multi-objective community detection based on Memetic algorithm was presented.In order to improve the diversity of the population,reduce the search space and raise the efficiency of the algorithm,the initialization strategy of label heuristic fast propagation and hybrid crossover were used in the algorithm and a node was selected in each community for mutation to optimize two objective functions,namely Improved Ratio Association (IRA) and Ratio Cut (RC),which turns the multi-objective optimization problem into minimal optimization of these two objectives at the same time.In local search,the local optimization target is constituted of weights of two objective functions and a hill-climbing strategy is used to find the best individual.Experiments on computer-generated networks and two classic real networks show that compared with four algorithms based on EAs and fast modularity algorithm,multi-objective community detection based on Memetic algorithm has certain advantages in solving complex network community detection problem.

Memetic algorithm;hybrid crossover;local search;multi-objective;network community detection

2015-04-20

2015-08-03

時間：2016-01-04

國家自然科學基金資助項目(61003237,61401225)；江蘇省自然科學基金(BK20140894)

周春霞(1992-)，女，碩士研究生，研究方向為復(fù)雜網(wǎng)絡(luò)的社區(qū)檢測；周井泉，博士，教授，碩士生導(dǎo)師，研究方向為通信網(wǎng)絡(luò)的信息管理和控制。

http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1510.056.html

TP301.6

A

1673-629X(2016)01-0053-05

10.3969/j.issn.1673-629X.2016.01.011