基于Memetic算法的多目標復雜網絡社區檢測

周春霞,周井泉,常瑞云

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

基于Memetic算法的多目標復雜網絡社區檢測

周春霞,周井泉,常瑞云

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

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

Memetic算法；混合交叉；局部搜索；多目標；網絡社區檢測

1 概 述

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

到目前為止，已經開發了許多網絡社區檢測的算法。

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

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

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

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

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

2 基于Memetic算法的多目標復雜網絡社區檢測

2.1 社區的定義

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

(1)

2.2 目標函數

Newman等在2002年引進了一個衡量網絡劃分質量的標準模塊度(Q)[3]，將網絡社區檢測轉化為一個優化問題，Q的定義如下：

(2)

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

(3)

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

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

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

(4)

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

通過最小化IRA和RC這兩個目標函數可以確保社區內連接是密切的而社區間的聯系是稀疏的。

(5)

2.3 算法描述

2.3.1 編碼方式

2.3.2 種群的初始化

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

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

2.3.3 交叉和變異

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

變異：在變異中，首先根據個體上節點的標簽得到社區結構，其次在每一個社區中隨機選擇一個節點，然后將這個節點的標簽隨機地變為其任意鄰居節點的標簽。這種變異操作只考慮待變異節點的鄰居節點，操作相對簡單，同時又能夠將每一個社區考慮在內，縮小了搜索空間，減少了無效搜索，提高了算法效率。

2.3.4 局部搜索

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

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

MOME中多目標優化算法的局部搜索采用權重和的方式將兩個不同的目標函數構成局部搜索的優化函數，如式(6)：

(6)

局部搜索策略中選擇爬山搜索，一旦搜索出比當前優化函數值小的解就將搜索出的解代替當前解，這個過程一直重復直到沒有更好的解產生或者達到最大的搜索次數為止，將對應的解作為當前代社區檢測的最優解。

3 實驗研究

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

3.1 人工合成網絡

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

圖1 5種不同算法在人工合成的 11個網絡上得到的NMI的值

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

3.2 真實的網絡

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

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

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

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

由于網絡本身存在復雜的網絡結構，很難有一種算法能夠完整地檢測出其真實的社區劃分。從圖3(b)最大Q值的檢測結果來看，MOME算法產生了10個社區，通過觀察發現錯誤地放置了一些節點，如：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]在這兩個網絡上獨立運行30次得到的平均NMI的值。

表1 MOME算法和Fast modularity算法對網絡檢測的結果

圖2 檢測結果(1)

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

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

4 結束語

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

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

[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-)，女，碩士研究生，研究方向為復雜網絡的社區檢測；周井泉，博士，教授，碩士生導師，研究方向為通信網絡的信息管理和控制。

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