基于進(jìn)化算法的重疊社群結(jié)構(gòu)探測(cè)

張鍇琦，杜海峰, 何曉晨

?

基于進(jìn)化算法的重疊社群結(jié)構(gòu)探測(cè)

張鍇琦1,2，杜海峰1,3, 何曉晨1,3

（1.西安交通大學(xué)公共管理與復(fù)雜性科學(xué)研究中心，陜西西安 710049；2.西安交通大學(xué)管理學(xué)院，陜西西安 710049；3.西安交通大學(xué)公共政策與管理學(xué)院，陜西西安 710049）

Ball等提出的基于概率模型的重疊社群探測(cè)方法（Principled statistical approach for overlapping communities）通過(guò)最大期望求解的方法能夠?qū)Υ笠?guī)模網(wǎng)絡(luò)的重疊社群結(jié)構(gòu)進(jìn)行有效探測(cè)。但由于該方法的優(yōu)化目標(biāo)函數(shù)求解空間相對(duì)復(fù)雜，其采用的爬山優(yōu)化算法難以獲得一個(gè)全局最優(yōu)的社群劃分結(jié)果。針對(duì)該問(wèn)題提出了一種基于進(jìn)化算法的重疊社群探測(cè)方法，通過(guò)設(shè)置不同社群劃分種群并采用競(jìng)爭(zhēng)優(yōu)選的過(guò)程來(lái)獲得對(duì)PSOC目標(biāo)函數(shù)的優(yōu)化。計(jì)算機(jī)生成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)重疊社群結(jié)構(gòu)的探測(cè)實(shí)驗(yàn)表明，所提改進(jìn)算法有效可用，能在獲得較優(yōu)目標(biāo)函數(shù)值的同時(shí)，對(duì)重疊社群結(jié)構(gòu)進(jìn)行準(zhǔn)確劃分。

復(fù)雜網(wǎng)絡(luò)；重疊社群結(jié)構(gòu)；進(jìn)化算法；算法改進(jìn)

0引言

社群結(jié)構(gòu)（Community Structure）有效地揭示了網(wǎng)絡(luò)中具有相對(duì)共性的節(jié)點(diǎn)所形成的社群關(guān)系，而不同社群之間則反映了網(wǎng)絡(luò)的中觀結(jié)構(gòu)關(guān)系特征，因而相關(guān)研究及其應(yīng)用受到了管理學(xué)、生物學(xué)、物理學(xué)等學(xué)科的重視[1-4]。有研究表明，社群結(jié)構(gòu)特征對(duì)于企業(yè)家精神的發(fā)揮存在顯著影響[5]，而社群結(jié)構(gòu)對(duì)于運(yùn)營(yíng)商營(yíng)銷(xiāo)策略的制定也提供了重要的理論支持[6]。

社群結(jié)構(gòu)探測(cè)是社群結(jié)構(gòu)特征結(jié)構(gòu)研究的基礎(chǔ)，而目前的社群探測(cè)方法多是一種硬聚類(lèi)（分類(lèi)）的方法，即探測(cè)結(jié)果的節(jié)點(diǎn)只隸屬于某一個(gè)社群中。但在真實(shí)網(wǎng)絡(luò)中，節(jié)點(diǎn)僅隸屬于一個(gè)社群的情況是不符合現(xiàn)實(shí)情況的，更為常見(jiàn)的是一個(gè)節(jié)點(diǎn)可能分屬于多個(gè)社群，尤其是那些位于社群邊緣與多個(gè)社群保持連接的節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)可能分屬于多個(gè)社群的情況被稱(chēng)為社群的重疊或重疊社群結(jié)構(gòu)（Overlapping Community Structure）[7]。重疊社群結(jié)構(gòu)除了能夠更準(zhǔn)確地反映網(wǎng)絡(luò)宏觀的結(jié)構(gòu)特征，還能夠?qū)W(wǎng)絡(luò)中節(jié)點(diǎn)結(jié)構(gòu)特征通過(guò)隸屬關(guān)系的方式進(jìn)行表達(dá)，例如社會(huì)關(guān)系中社會(huì)成員的多重社會(huì)身份、管理研究中企業(yè)員工分屬不同工作小組的隸屬程度等。因而近些年對(duì)于重疊社群結(jié)構(gòu)的探測(cè)已經(jīng)成為社群結(jié)構(gòu)研究的新熱點(diǎn)[7]。

已有對(duì)于重疊社群結(jié)構(gòu)探測(cè)的方法中，最為通用的是由Palla等所提出的基于-派系的重疊社群識(shí)別的方法——派系過(guò)濾方法（Clique Percolation Method，CPM）[8]。CPM假設(shè)網(wǎng)絡(luò)中存在多個(gè)相鄰的-派系，通過(guò)定義相鄰派系共享節(jié)點(diǎn)的數(shù)量發(fā)現(xiàn)其中存在的重疊的社群結(jié)構(gòu)特征。Palla等在CPM方法之上提出了用于加權(quán)網(wǎng)絡(luò)的CPMw方法和用于有向網(wǎng)絡(luò)的CPMd方法[9,10]。但是CPM方法對(duì)于大規(guī)模網(wǎng)絡(luò)計(jì)算復(fù)雜度高，同時(shí)存在參數(shù)設(shè)定模糊和識(shí)別準(zhǔn)確度較低等問(wèn)題。

Ball等于2011年提出了一種基于概率模型的重疊社群結(jié)構(gòu)探測(cè)方法（Principled Statistical Approach for Overlapping Communities，以下簡(jiǎn)稱(chēng)PSOC算法）[11]。該方法引用概率潛在語(yǔ)義分析（Probabilistic Latent Semantic Analysis，PLSA）模型[12-14]中對(duì)于文本共同主題探測(cè)的思路，構(gòu)建一種包含節(jié)點(diǎn)、邊與社群隸屬關(guān)系的網(wǎng)絡(luò)生成模型，通過(guò)最大期望估計(jì)的方法獲得節(jié)點(diǎn)、邊與社群之間的隸屬關(guān)系，從而實(shí)現(xiàn)大型網(wǎng)絡(luò)重疊社群結(jié)構(gòu)的高效探測(cè)。但是PSOC算法所優(yōu)化的目標(biāo)函數(shù)是一個(gè)復(fù)雜的多峰函數(shù)，PSOC算法所采用的爬山優(yōu)化策略很難獲得該函數(shù)的全局最優(yōu)，從根本上影響了PSOC算法的探測(cè)結(jié)果。同時(shí)PSOC算法所采用的串行算法結(jié)構(gòu)和初始值設(shè)定也影響著算法的探測(cè)效果與效率。

針對(duì)以上問(wèn)題，本文基于PSOC算法提出一種基于混合進(jìn)化算法的重疊社群探測(cè)方法，在進(jìn)行最大期望估計(jì)的求解過(guò)程中引入混合競(jìng)爭(zhēng)的進(jìn)化思想，將優(yōu)化過(guò)程融入到求解過(guò)程中，從而盡可能的獲得全局最優(yōu)解。本文余下的內(nèi)容由四個(gè)部分組成：第二部分是對(duì)PSOC算法的運(yùn)行機(jī)理進(jìn)行分析，探討該算法的特點(diǎn)；第三部分是將混合進(jìn)化算法的思想引入到PSOC算法之中，提出一種新的優(yōu)化求解方法；第四部分是利用計(jì)算機(jī)生成網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)對(duì)本文所提的優(yōu)化方法進(jìn)行測(cè)試，通過(guò)與PSOC算法的對(duì)比對(duì)改進(jìn)算法的有效性和可用性進(jìn)行驗(yàn)證；第五部分是本文的研究結(jié)論，研究局限性與進(jìn)一步工作的簡(jiǎn)單討論。

1基于概率模型的重疊社群結(jié)構(gòu)探測(cè)方法

Ball等在文獻(xiàn)[11]中所提出的針對(duì)重疊社群結(jié)構(gòu)的PSOC方法的本質(zhì)上是一種還原網(wǎng)絡(luò)統(tǒng)計(jì)概率模型。模型通過(guò)一組隱含變量構(gòu)建節(jié)點(diǎn)、邊和社群之間的隸屬關(guān)系。具體的該模型設(shè)定生成網(wǎng)絡(luò)擁有個(gè)節(jié)點(diǎn)和個(gè)社群，設(shè)隱含變量θ表示節(jié)點(diǎn)所屬于社群的概率，而將節(jié)點(diǎn)和節(jié)點(diǎn)之間的邊屬于社群期望表示為θθ。根據(jù)以上設(shè)定，如果隱含變量能夠使得生成網(wǎng)絡(luò)對(duì)原網(wǎng)絡(luò)的還原概率獲得最大，則生成網(wǎng)絡(luò)能夠在還原網(wǎng)絡(luò)的同時(shí)，通過(guò)反映節(jié)點(diǎn)、邊和社群的隸屬關(guān)系，揭示網(wǎng)絡(luò)中存在的重疊社群結(jié)構(gòu)。因而依據(jù)原網(wǎng)絡(luò)鄰接矩陣A，隱含變量條件下生成網(wǎng)絡(luò)的還原概率可以表示為：

對(duì)于上式，采用最大期望估計(jì)方法（EM算法）實(shí)現(xiàn)極大似然估計(jì)方法求解，更表示為：

（2）

其中q()表示在節(jié)點(diǎn)與節(jié)點(diǎn)間的連接邊對(duì)于所有社群，屬于社群的可能性，即，其滿足。形式上不斷優(yōu)化式（2）右部的計(jì)算結(jié)果， 可不斷逼近的最大值。因此，對(duì)于PSOC算法而言，其優(yōu)化的目標(biāo)函數(shù)可表示為

而根據(jù)q()的定義，文獻(xiàn)[11]在對(duì)式（3）求導(dǎo)后將式（2）的最大似然估計(jì)求解便轉(zhuǎn)化為對(duì)θ和q()的求解問(wèn)題。而通過(guò)最大期望估計(jì)方法對(duì)θ和q()的反復(fù)迭代求解，便可獲得問(wèn)題的最終求解。

Ball在實(shí)現(xiàn)上述求解過(guò)程中，主要分為兩個(gè)步驟完成第一步為計(jì)算步驟（Compute Step），其通過(guò)統(tǒng)計(jì)已有節(jié)點(diǎn)與社群之間的連接邊的平均數(shù)量k（）和社群擁有的平均度數(shù)（）來(lái)計(jì)算θ以及相應(yīng)的q()。并用()存儲(chǔ)節(jié)點(diǎn)與社群的關(guān)系矩陣。

第二步為剪枝步驟（Pruning Step），其根據(jù)已計(jì)算的q()來(lái)計(jì)算k’，并實(shí)現(xiàn)對(duì)k的替換修正，以用于后次迭代；同時(shí)剪枝步驟操作還對(duì)最大期望估計(jì)方法的收斂步長(zhǎng)進(jìn)行修正，根據(jù)文獻(xiàn)[11]中的設(shè)定最大期望估計(jì)方法的收斂條件為初始設(shè)定的容忍度值；當(dāng)時(shí)，即認(rèn)為最大期望估計(jì)方法的求解已經(jīng)收斂，停止最大期望估計(jì)方法的迭代，并根據(jù)式（3）計(jì)算相應(yīng)的值。

然而作為一個(gè)優(yōu)化問(wèn)題，由于PSOC算法采用隨機(jī)初始化的方法進(jìn)行最大期望估計(jì)求解，單次最大期望估計(jì)所得的值很難保證其為最優(yōu)解。因此，PSOC算法的優(yōu)化策略是采用一般爬山優(yōu)化策略。具體地PSOC算法對(duì)最大期望估計(jì)方法進(jìn)行多次獨(dú)立執(zhí)行，將多次計(jì)算結(jié)果中最大的值作為算法的最優(yōu)解，并將該值所對(duì)應(yīng)的重疊社群探測(cè)結(jié)果作為最終的劃分結(jié)果。

PSOC算法雖然給出了一套完整的探測(cè)重疊社群結(jié)構(gòu)的重構(gòu)模型和求解方法，但是從已有的算法設(shè)計(jì)來(lái)看，其仍存在需要改進(jìn)之處。首先，正如文獻(xiàn)[11]所指出的，PSOC算法是一個(gè)分類(lèi)方法，初始設(shè)定的社群數(shù)量會(huì)影響到算法最終探測(cè)結(jié)果。

其次，本文研究發(fā)現(xiàn)，對(duì)于給定網(wǎng)絡(luò)，式（3）的目標(biāo)函數(shù)是一個(gè)復(fù)雜的多峰函數(shù)，通過(guò)爬山策略獲得目標(biāo)函數(shù)優(yōu)化的過(guò)程存在易于陷入局部最優(yōu)值的問(wèn)題。圖1是PSOC算法在分析網(wǎng)絡(luò)Zachary時(shí)值優(yōu)化的結(jié)果分布，從1000次求解的結(jié)果來(lái)看值最優(yōu)值的搜索空間十分復(fù)雜，算法的最優(yōu)結(jié)果收到算法迭代次數(shù)影響的可能很大，因而簡(jiǎn)單的爬山優(yōu)化策略難以滿足需求。

圖1 PSOC算法針對(duì)Zachary網(wǎng)絡(luò)1000次迭代求解D值分布

最后，PSOC算法對(duì)于值的求解過(guò)程與優(yōu)化過(guò)程之間存在相對(duì)較弱的依賴性，因而現(xiàn)有優(yōu)化過(guò)程所采用的串行算法結(jié)構(gòu)并不會(huì)有益于值的求解，相反，會(huì)因?yàn)榈螖?shù)而影響到算法的效率。此外，PSOC算法還會(huì)受到較多初始參數(shù)的影響而最終影響探測(cè)效果。

2基于進(jìn)化算法的方法改進(jìn)

根據(jù)對(duì)于PSOC算法機(jī)理分析，PSOC算法利用爬山算法優(yōu)化目標(biāo)函數(shù)的方法很難獲得全局最優(yōu)，并且該算法忽略了求解過(guò)程的隱含并行性，因此，本文采用進(jìn)化算法取代爬山算法完成對(duì)目標(biāo)函數(shù)的優(yōu)化。對(duì)網(wǎng)絡(luò)初始建立個(gè)社群劃分種群，通過(guò)種群個(gè)體τ()之間的交叉引入獨(dú)立算法之間的相互關(guān)系，通過(guò)種群的變異復(fù)制執(zhí)行原算法的迭代修正，通過(guò)適應(yīng)度函數(shù)值對(duì)種群進(jìn)行優(yōu)選，將原有串行算法改為并行求解，在原方法每次獨(dú)立算法之間引入競(jìng)爭(zhēng)關(guān)系，從而獲得對(duì)社群劃分結(jié)果的不斷優(yōu)化和改進(jìn)。同時(shí)引入了克隆選擇過(guò)程來(lái)保持進(jìn)化過(guò)程中的種群多樣性。具體地，本文提出的算法（Evolutionary Algorithm for Overlapping Community，以下簡(jiǎn)稱(chēng)EOC算法）主要包括克隆操作、修正操作、交叉操作、變異操作和競(jìng)爭(zhēng)優(yōu)選操作五個(gè)部分組成。算法通過(guò)隨機(jī)初始化的方式，生成個(gè)包含個(gè)節(jié)點(diǎn)和個(gè)社群的初始社群劃分矩陣，其生成方法與原PSOC算法操作一致。

圖2 變異策略節(jié)點(diǎn)隸屬社群示意圖

對(duì)于一個(gè)還原原網(wǎng)絡(luò)的算法而言，這種調(diào)整要么會(huì)使得結(jié)果更真實(shí)的還原實(shí)際情況，要么會(huì)使得結(jié)果背離實(shí)際情況。但從本文提出的算法整體結(jié)構(gòu)而言，進(jìn)化的策略會(huì)保留更優(yōu)的結(jié)果而剔除背離實(shí)際的結(jié)果，因此變異操作可能會(huì)產(chǎn)生更優(yōu)的結(jié)果而被進(jìn)一步保留，從而在一定程度上縮短了最優(yōu)解的搜索路徑。依據(jù)這一策略，變異操作的具體操作是，對(duì)種群τ（Par）遍歷網(wǎng)絡(luò)中的邊-以p概率選取其作為變異操作對(duì)象，從種群τ(Par)中獲取節(jié)點(diǎn)和節(jié)點(diǎn)對(duì)應(yīng)社群的期望θ和θ，交換θ和θ的值，實(shí)現(xiàn)變異操作。

基于以上算法操作和進(jìn)化算法基本框架，本文所構(gòu)造的改進(jìn)策略算法結(jié)構(gòu)如下：

算法1:EOC算法結(jié)構(gòu) INPUT: Graph G=(V,E), PopNum g,CloneNum n,CrossProb pc, MutationProb pm OUTPUT: Community Partition M 1: FOR each chromosome 2: randomly generateτi(M) 3: ENDFOR 4: WHILE Iteration

算法采用迭代次數(shù)作為算法的停止條件。算法停止后取D所對(duì)應(yīng)的重疊社群劃分結(jié)構(gòu)為算法的最終結(jié)果。算法操作過(guò)程中，交叉操作、變異操作以及修正操作的先后順序理論上不影響算法的最終結(jié)果，但可能在一定程度上影響算法的搜索路徑和搜索效率。

從算法構(gòu)建機(jī)理來(lái)看，如圖3所示，EOC算法事實(shí)上是對(duì)PSOC算法優(yōu)化結(jié)構(gòu)上的一種結(jié)構(gòu)調(diào)整。

圖中兩種算法的計(jì)算步驟和剪枝修正步驟的算法過(guò)程是一致的，而不同的是PSOC算法中每次迭代過(guò)程是獨(dú)立的，EOC算法則將這種獨(dú)立的算法進(jìn)行并行處理，將優(yōu)化過(guò)程融入到求解過(guò)程中，從而解決PSOC算法依靠單純爬山算法容易獲得局部最優(yōu)的問(wèn)題。PSOC算法的單次最大時(shí)間復(fù)雜度為O()，其中是邊的數(shù)量，為設(shè)定社群數(shù)量，而EOC算法的單次時(shí)間復(fù)雜度為O(K)，為設(shè)定種群數(shù)量，為克隆種群數(shù)量，和設(shè)定與PSOC算法相同。從算法復(fù)雜度的角度而言本文所提算法要高于PSOC算法，但當(dāng)固定種群數(shù)量時(shí)算法時(shí)間復(fù)雜度與PSOC算法相仿。EOC算法的收斂性證明與基礎(chǔ)進(jìn)化算法類(lèi)似，此處便不再贅述。

（a）PSOC算法求解過(guò)程簡(jiǎn)圖

（b）EOC算法求解過(guò)程簡(jiǎn)圖

圖3 PSOC算法與EOC算法結(jié)構(gòu)對(duì)比圖

3實(shí)驗(yàn)與討論

實(shí)驗(yàn)包括三個(gè)部分組成：實(shí)驗(yàn)1采用了Ball等對(duì)于PSOC算法進(jìn)行測(cè)試的生成網(wǎng)絡(luò)模型對(duì)EOC算法結(jié)果進(jìn)行測(cè)試，通過(guò)劃分還原效果對(duì)不同設(shè)置下的結(jié)果進(jìn)行測(cè)試。實(shí)驗(yàn)2采用四種真實(shí)網(wǎng)絡(luò)對(duì)PSOC算法和EOC算法的算法性能進(jìn)行比較。實(shí)驗(yàn)3則是對(duì)EOC算法中的參數(shù)對(duì)算法性能的影響進(jìn)行討論。實(shí)驗(yàn)均在Intel（R）Core（TM）2 Quad CPU Q8400 @2.66GHz的PC機(jī)上采用Matlab7.0實(shí)現(xiàn)測(cè)試。試驗(yàn)初始設(shè)定的參數(shù)為社群數(shù)量=20，克隆種群數(shù)量=6，變異概率為p為0.8，交叉概率p為0.1；停止準(zhǔn)則為最大迭代次數(shù)N為100。為消除算法的隨機(jī)性，實(shí)驗(yàn)所得結(jié)果均為100次獨(dú)立運(yùn)算的結(jié)果平均。

3.1生成網(wǎng)絡(luò)實(shí)驗(yàn)

Ball等[11]在對(duì)PSOC算法進(jìn)行測(cè)試的過(guò)程中，提出了一種可控制變量的隨機(jī)生成網(wǎng)絡(luò)，對(duì)算法的還原程度進(jìn)行測(cè)試。根據(jù)其對(duì)于該網(wǎng)絡(luò)模型的設(shè)定，其包含個(gè)節(jié)點(diǎn)。如圖4所示，該網(wǎng)絡(luò)擁有兩個(gè)相互重疊的社群和，用和分別代表社群獨(dú)立擁有的節(jié)點(diǎn)數(shù)量，用表示兩個(gè)社群重疊的節(jié)點(diǎn)數(shù)量，因此有=--。同時(shí)初始設(shè)定每個(gè)節(jié)點(diǎn)度的期望值為。

圖4 生成測(cè)試網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

根據(jù)以上設(shè)定，當(dāng)分別改變以及值時(shí)，將構(gòu)建不同的網(wǎng)絡(luò)結(jié)構(gòu)模型。尤其是當(dāng)值發(fā)生變化時(shí)，網(wǎng)絡(luò)中社群結(jié)構(gòu)的變化尤為明顯。根據(jù)Ball的描述，當(dāng)k→0時(shí)，網(wǎng)絡(luò)類(lèi)似于隨機(jī)網(wǎng)絡(luò)而社群結(jié)構(gòu)十分模糊，此時(shí)算法所探測(cè)的結(jié)果也相對(duì)較差；而隨著值的不斷增加，網(wǎng)絡(luò)中的邊也不斷增加，相應(yīng)的網(wǎng)絡(luò)中存在的兩個(gè)社群結(jié)構(gòu)也逐漸清晰；同時(shí)，由于網(wǎng)絡(luò)模型中事先設(shè)定了重疊社群中的節(jié)點(diǎn)數(shù)量，使得<(-1)/2時(shí)，網(wǎng)絡(luò)始終能區(qū)分出存在兩個(gè)相互重疊的社群。因此，本文在控制值的情況下對(duì)EOC算法進(jìn)行了實(shí)驗(yàn)測(cè)試。設(shè)定測(cè)試網(wǎng)絡(luò)模型規(guī)模=1000，設(shè)==475，=50；設(shè)值從1開(kāi)始以步長(zhǎng)為2共取10組數(shù)據(jù)。實(shí)驗(yàn)采用兩個(gè)指標(biāo)對(duì)算法的還原程度進(jìn)行測(cè)試，其一為Ball原文中的Jaccard指數(shù)，Jaccard指數(shù)是一種區(qū)分?jǐn)?shù)據(jù)重疊程度的指數(shù)。根據(jù)Ball對(duì)于Jaccard指數(shù)的設(shè)定，設(shè)S為網(wǎng)絡(luò)中實(shí)際屬于重疊部分的節(jié)點(diǎn)，設(shè)V為探測(cè)所得的重疊部分的節(jié)點(diǎn)，則Jaccard指數(shù)可以表示為。其二本文采用了一種改進(jìn)的NMI指數(shù)測(cè)量方法[15]來(lái)比較探測(cè)結(jié)果與實(shí)際結(jié)果之間的差異，具體地對(duì)于該網(wǎng)絡(luò)模型設(shè)網(wǎng)絡(luò)重疊部分節(jié)點(diǎn)為一個(gè)獨(dú)立的社群，設(shè)定臨界系數(shù)，比較算法結(jié)果中每個(gè)節(jié)點(diǎn)對(duì)不同社群的期望，當(dāng)時(shí)，則認(rèn)定該節(jié)點(diǎn)屬于兩個(gè)社群重疊的部分；其他情況節(jié)點(diǎn)按較大的期望，劃分其為對(duì)應(yīng)的社群。NMI指數(shù)越接近1，探測(cè)社群結(jié)構(gòu)與實(shí)際社群結(jié)構(gòu)越相似，反之差異越大；在本文中，由于算法探測(cè)所得的社群劃分結(jié)果明顯會(huì)受到的影響，因此NMI值在一定程度上受到的影響而有所差異；本文實(shí)驗(yàn)中設(shè)。經(jīng)計(jì)算，EOC算法和PSOC算法實(shí)驗(yàn)所得的結(jié)果如圖5所示。

（a）NMI結(jié)果對(duì)比圖

（b）Jaccard指數(shù)結(jié)果對(duì)比圖

圖5 生成網(wǎng)絡(luò)結(jié)果對(duì)比圖

圖5表明，兩種算法NMI值和Jaccard值隨著值的增大而不斷提高，說(shuō)明算法隨著社群結(jié)構(gòu)的清晰而探測(cè)結(jié)果不斷優(yōu)化；圖5（a）中，除了在=1時(shí)，EOC算法的結(jié)果差于PSOC算法結(jié)果外，其余情況EOC算法所得的NMI結(jié)果總是優(yōu)于PSOC算法的結(jié)果。圖5（b）則表明，當(dāng)>7時(shí)，EOC算法的結(jié)果都優(yōu)于PSOC算法所得的結(jié)果。綜上所述，在社群結(jié)構(gòu)模糊時(shí)，兩種算法的結(jié)果的探測(cè)結(jié)果都較差；但隨著社群結(jié)構(gòu)的逐漸清晰，兩種算法探測(cè)結(jié)果的還原程度不斷提高，同時(shí)EOC算法相比PSOC算法具有更好的探測(cè)效果。

3.2實(shí)際網(wǎng)絡(luò)實(shí)驗(yàn)

為了比較兩種算法對(duì)于實(shí)際網(wǎng)絡(luò)實(shí)驗(yàn)的探測(cè)效果，本文選取了Zachary、Dolphins、Football以及Polbooks四組網(wǎng)絡(luò)數(shù)據(jù)作為測(cè)試數(shù)據(jù)。選取這些數(shù)據(jù)的原因在于其社群結(jié)構(gòu)數(shù)量已知，能夠更好的比較兩種算法的探測(cè)效果。表1列出了這些實(shí)際網(wǎng)絡(luò)數(shù)據(jù)的基本特征。

表1 實(shí)驗(yàn)測(cè)試網(wǎng)絡(luò)數(shù)據(jù)特征

測(cè)試結(jié)果如表1所示，表中PSOC算法與EOC算法所計(jì)算的值分別用D和D表示，用來(lái)表示兩種算法的差異性，其定義為

當(dāng)0時(shí)，表明兩種算法沒(méi)有明顯的差異性；當(dāng)0時(shí)表示EOC算法探測(cè)效果更優(yōu)，反之則PSOC算法效果更優(yōu)。為了消除隨機(jī)搜索帶來(lái)的結(jié)果的差異性，表2中的所有結(jié)果都是100次運(yùn)算結(jié)果的平均值所得，并給出了相應(yīng)的標(biāo)準(zhǔn)差Std和Std。

表2 實(shí)驗(yàn)測(cè)試結(jié)果

從表2的結(jié)果來(lái)看，對(duì)于4個(gè)網(wǎng)絡(luò)而言在同樣社群數(shù)量設(shè)定情況下，EOC算法所得的結(jié)果都優(yōu)于PSOC算法所得的結(jié)果。并且從標(biāo)準(zhǔn)差的比較來(lái)看，EOC算法所得結(jié)果的標(biāo)準(zhǔn)差小于PSOC算法的結(jié)果標(biāo)準(zhǔn)差，說(shuō)明EOC算法的求解過(guò)程更加穩(wěn)定。

圖6對(duì)比了EOC算法和PSOC算法在上述實(shí)驗(yàn)基礎(chǔ)上對(duì)Zachary網(wǎng)絡(luò)探測(cè)結(jié)果中節(jié)點(diǎn)k的分布情況。Zachary網(wǎng)絡(luò)含有34個(gè)節(jié)點(diǎn)和兩個(gè)社群，因而=1,2..., 34；=1, 2。

圖中橫軸表示Zachary網(wǎng)絡(luò)中的34個(gè)節(jié)點(diǎn)，縱軸表示0-1標(biāo)準(zhǔn)化后節(jié)點(diǎn)的度分別屬于社群1和社群2的數(shù)量k。k的分布極差說(shuō)明了算法在對(duì)節(jié)點(diǎn)探測(cè)其屬于社群的穩(wěn)定性，極差越大算法穩(wěn)定性越差，反之則算法的穩(wěn)定性越好；從結(jié)果來(lái)看，EOC算法在100次探測(cè)過(guò)程中，每個(gè)k的分布都保持在一個(gè)極小的范圍內(nèi)，因而可以認(rèn)為EOC算法探測(cè)的效果是穩(wěn)定的。而對(duì)于PSOC算法，k的分布則普遍存在一定極差，因而其求解過(guò)程并不穩(wěn)定。

3.3參數(shù)影響討論

交叉概率和變異概率是EOC算法中兩個(gè)重要的參數(shù)。作為初始參數(shù)，其是否會(huì)影響算法的最終求解是算法結(jié)果穩(wěn)定性的一項(xiàng)重要評(píng)判標(biāo)準(zhǔn)。由于數(shù)理上很難對(duì)這個(gè)兩個(gè)參數(shù)對(duì)算法的影響進(jìn)行討論，因此本文試圖通過(guò)模擬仿真的方法實(shí)現(xiàn)參數(shù)對(duì)算法的影響討論。在不同交叉概率和變異概率的影響下，本文對(duì)表1中四組網(wǎng)絡(luò)的社群結(jié)構(gòu)探測(cè)結(jié)果進(jìn)行了統(tǒng)計(jì)。圖7（a）顯示了p=0.1，交叉概率c從0.1增至1時(shí)，EOC算法所的社群探測(cè)結(jié)構(gòu)對(duì)應(yīng)最大值的變化情況；圖7（b）顯示了p=0.1時(shí)，變異概率p從0.1增至1時(shí)，對(duì)應(yīng)最大值的變化情況。

從結(jié)果來(lái)看，當(dāng)變異概率p和交叉概率p變化時(shí)，EOC算法所得值均有一定波動(dòng)，但總體變化不大。說(shuō)明EOC算法結(jié)果受到變異概率p和交叉概率p變化的影響并不明顯。但需要說(shuō)明的是，雖然p和p不會(huì)顯著影響EOC算法的求解結(jié)果，但會(huì)影響EOC算法的求解過(guò)程，在一定程度上影響算法的收斂速度。

4結(jié)論與展望

PSOC算法作為一種重疊社群結(jié)構(gòu)探測(cè)方法，依靠還原網(wǎng)絡(luò)結(jié)構(gòu)的概率模型，通過(guò)EM算法對(duì)節(jié)點(diǎn)與社群之間的隸屬期望進(jìn)行估計(jì)求解，形成節(jié)點(diǎn)與社群的隸屬關(guān)系矩陣，從而實(shí)現(xiàn)對(duì)節(jié)點(diǎn)分屬于多個(gè)社群的結(jié)構(gòu)探測(cè)。但是作為一種求解最優(yōu)目標(biāo)函數(shù)的方法，PSOC算法使用的爬山算法并不能有效求解復(fù)雜目標(biāo)函數(shù)求解空間，并且PSOC算法中含有的初始參數(shù)在一定程度上會(huì)影響到算法的最終結(jié)果。因此，本文提出了一種基于進(jìn)化算法思想的優(yōu)化策略來(lái)改進(jìn)PSOC算法。改進(jìn)方法EOC算法以目標(biāo)函數(shù)值為適應(yīng)度函數(shù)，以節(jié)點(diǎn)與社群的隸屬關(guān)系矩陣為進(jìn)化種群，通過(guò)種群之間的交叉、變異、修正、優(yōu)選等操作來(lái)實(shí)現(xiàn)對(duì)目標(biāo)函數(shù)的優(yōu)化，進(jìn)而獲得最優(yōu)的重疊社群結(jié)構(gòu)探測(cè)結(jié)果。從本質(zhì)而言，EOC算法將PSOC算法中的獨(dú)立串行求解過(guò)程改變?yōu)橐环N交互并行求解過(guò)程，使得算法執(zhí)行過(guò)程中不同求解過(guò)程之間可以存在一定的相互影響，進(jìn)而實(shí)現(xiàn)對(duì)目標(biāo)函數(shù)全局最優(yōu)求解的逼近。通過(guò)對(duì)EOC算法和PSOC算法之間的實(shí)驗(yàn)測(cè)試發(fā)現(xiàn)，對(duì)于一般0-1對(duì)稱(chēng)網(wǎng)絡(luò)而言，EOC算法比PSOC算法擁有更優(yōu)的求解效果，并且EOC算法的初始參數(shù)并不會(huì)顯著影響到算法的求解結(jié)果。

本文通過(guò)對(duì)PSOC算法的改進(jìn)探索發(fā)現(xiàn)，重疊社群結(jié)構(gòu)探測(cè)其本質(zhì)是對(duì)于社群間邊緣鄰接節(jié)點(diǎn)的探測(cè)過(guò)程。對(duì)于該類(lèi)節(jié)點(diǎn)的識(shí)別可以有效的區(qū)分出網(wǎng)絡(luò)中的其他社群結(jié)構(gòu)，進(jìn)而實(shí)現(xiàn)對(duì)社群結(jié)構(gòu)的探測(cè)。而如果將重疊社群節(jié)點(diǎn)作為一個(gè)獨(dú)立的社群結(jié)構(gòu)納入到社群結(jié)構(gòu)探測(cè)過(guò)程中，為社群結(jié)構(gòu)探測(cè)提供了一種新的研究思路。同時(shí)，對(duì)于該類(lèi)節(jié)點(diǎn)的研究在社會(huì)網(wǎng)絡(luò)研究中具有十分重要的社會(huì)學(xué)意義，該類(lèi)節(jié)點(diǎn)所提供的隸屬度在一定程度上擴(kuò)充了社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的社會(huì)屬性，為社會(huì)網(wǎng)絡(luò)研究提供了新的研究途徑。然而，EOC算法仍然是一種分類(lèi)算法，對(duì)于未知社群數(shù)量的網(wǎng)絡(luò)而言，算法的結(jié)果顯然很難與實(shí)際情況相符。這也需要在進(jìn)一步的研究工作中予以完善。同時(shí)，就EOC算法的普遍適用性而言，對(duì)于探測(cè)有向網(wǎng)絡(luò)、加權(quán)網(wǎng)絡(luò)等網(wǎng)絡(luò)結(jié)構(gòu)仍需要做進(jìn)一步的研究。

（a）EOC算法節(jié)點(diǎn)k的分布情況

（b）PSOC算法節(jié)點(diǎn)k’的分布情況

圖6 Zachary網(wǎng)絡(luò)社群結(jié)構(gòu)探測(cè)k’分布狀況

(a) 交叉概率pc (b) 變異概率pm

[1] Newman MEJ, Barabàsi AL, Watts DJ. The Structure and Dynamic of Networks [M]. New Jersey: Princeton University Press, 2006.

[2] Newman MEJ. Communities, modules and large-scale structure in networks [J]. Nature Physics, 2012.8: 25-31

[3] 杜海峰,李樹(shù)茁, Marcus W.F.,悅中山,楊緒松.小世界網(wǎng)絡(luò)與無(wú)標(biāo)度網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)研究[J].物理學(xué)報(bào), 2007,12:6886-6893.

[4] Newman MEJ. Modularity and community structure in networks [J]. Proceedings of the National Academy of Sciences of the United States of America (PNAS), 2006, 103(23): 8577-8582

[5] 楊勇,周勤. 集群網(wǎng)絡(luò)、知識(shí)溢出和企業(yè)家精神—基于美國(guó)高科技產(chǎn)業(yè)集群的證據(jù)[J].管理工程學(xué)報(bào),2013, 27(2):32-37.

[6] 彭建平,張業(yè)軍.電信社群網(wǎng)絡(luò)用戶行為特征及演化分析[J].管理工程學(xué)報(bào),2012,26(3):88-95

[7] Fortunato S. Community detection in graphs[J]. Physics Reports, Elsevier B.V., 2010, 486(3-5): 75-174.

[8] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005,435, 814–818

[9] Palla G, Farkas I, Pollner P. Directed network modules [J]. New Journal of Physics, 2007, 9(6): 21.

[10] Farkas I, ábel D, Palla G, et al. Weighted network modules [J]. New Journal of Physics, 2007, 9(6): 19.

[11] Ball Brain, Ball Karrer, Newman MEJ. Efficient and principled method for detecting communities in networks[J].Physical Review E, 2011.84.036103

[12] Hofmann T. Probabilistic latent semantic indexing. In Proceedings of the 22nd Annual International ACM Conference on Research and Development in Information Retrieval[C]. New York: Association of Computing Machinery, 1999. 50–57.

[13] Hofmann T. Unsupervised learning by probabilistic latent semantic analysis [J]. Mach Learn, 2001, 42: 177–196.

[14] Hofmann T. Latent semantic models for collaborative filtering[J]. ACM Trans. Inf. Syst. 2004, 22: 89–115.

[15] Danon L, Guilera AD, Duch J, et al. Comparing community structure identification [J/OL], 2005, http://arxiv.org/abs/cond-mat/0505245v2.

Evolutionary Algorithm for Overlapping Community Structure Detection

ZHANG Kai-qi1,2, DU Hai-feng1, 3, HE Xiao-chen1, 3

(1.Center for Administration and Complexity Science, Xi’an Jiaotong University, Xi’an 710049, China;2. School of Management, Xi’an Jiaotong University, Xi’an 710049，China;3. School of Public Policy and Administration, Xi’an Jiaotong University, Xi’an 710049, China)

Overlapping community structure detection, which has become a new hot spot for the analysis of community structure, can not only reflect the macro-structure of networks more accurately, but also describe the structure of nodes in networks by affiliation expressions. Ball et al once proposed the algorithm of principled statistical approach for overlapping communities (denoted as PSOC), which can efficiently detect the overlapping community structure. However, the climbing optimization algorithm in PSOC may derive the result trapped in local optimum. In addition, the algorithm structure and the initial value of PSOC algorithm adversely affect the detection effectiveness and efficiency of the algorithm.

To solve these problems, we introduce the evolutionary algorithm (denoted as EOC) to replace the climbing algorithm to optimize the objective function. Specifically, we first initially establishcommunities for the network. In addition, we introduce the crossover operator to build the connection among the independent optimizing process in PSOC and the mutation operator to replace the iterative adjusting in PSOC. We transform the original serial algorithm structure into the parallel one. Through the calculation of the fitness functionand the competition among the population, we select the best community division as the result in each iteration. There are two improvements of EOC. Firstly, the heuristic in mutation operator can reduce the searching path for the optimal solution. Secondly, the competition among the population in EOC can lead to the solving process. It no longer depends on the tolerance value and other parameters in PSOC and avoids the result trapped in local optimum.

From the experiment of generation network and actual network, EOC can correctly detect the overlapping community structure and its result is not worse than the result of PSOC. The community division of EOC is more stable than the PSOC. The solving process is not significantly affected by the parameters in EOC but the convergence speed may be affected to some certain extent.

In this paper, we found that the essence of detecting overlapping community structure is the process of detecting nodes at the margin of communities and connect communities. The identification of such nodes can effectively distinguish the other community structures of the network in order to achieve detection of the community structure. If we treat the overlapping community node as an independent community structure integrated into the community structure detection process, it will provide a new method to detect the community structure. Moreover, the study of such nodes has great sociology significance in the analysis of social networks. It expands the social attributes of nodes and provides new method of research in the study of social networks. However, EOC is still a classification algorithm. For social networks with an unknown number of communities, it is difficult to make the result correspond with the practical situation, which needs to be improved in further research study. Meanwhile, directed network structure and weighted network structure should be explored in terms of the general applicability of the EOC algorithm.

complex network; overlapping community structure; evolutionary algorithm; algorithm improvement

中文編輯：杜 ??；英文編輯：Charlie C. Chen

F224.33

A

1004-6062(2016)01-0221-07

10.13587/j.cnki.jieem.2016.01.028

2015-01-23

2015-06-09

國(guó)家社會(huì)科學(xué)基金重點(diǎn)資助項(xiàng)目（12AZD110）；國(guó)家自然科學(xué)基金資助項(xiàng)目（71071128）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目（2011JDGZ08）

張鍇琦（1987—），男，陜西西安人，西安交通大學(xué)管理學(xué)院博士研究生，研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)與社會(huì)網(wǎng)絡(luò)分析、社會(huì)計(jì)算。