孫奕菲，姚若俠，焦李成

(1.陜西師范大學(xué)a.物理學(xué)與信息技術(shù)學(xué)院，b.計(jì)算機(jī)科學(xué)學(xué)院，西安710119;2.西安電子科技大學(xué)智能感知與圖像理解教育部重點(diǎn)實(shí)驗(yàn)室，西安710071)

基于Memetic算法和關(guān)聯(lián)學(xué)習(xí)的社會(huì)網(wǎng)絡(luò)聚類(lèi)分析

孫奕菲1a，姚若俠1b，焦李成2

(1.陜西師范大學(xué)a.物理學(xué)與信息技術(shù)學(xué)院，b.計(jì)算機(jī)科學(xué)學(xué)院，西安710119;2.西安電子科技大學(xué)智能感知與圖像理解教育部重點(diǎn)實(shí)驗(yàn)室，西安710071)

針對(duì)社會(huì)網(wǎng)絡(luò)系統(tǒng)中的社會(huì)屬性知識(shí)沒(méi)有被充分挖掘，網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法學(xué)習(xí)能力弱的問(wèn)題，提出了一種Memetic關(guān)聯(lián)學(xué)習(xí)算法(MRLA)。研究了新算法的基本原理和各個(gè)算子，實(shí)現(xiàn)了社會(huì)屬性信息的有效利用。新算法充分結(jié)合基于Memetic計(jì)算的準(zhǔn)確性和基于社會(huì)關(guān)聯(lián)學(xué)習(xí)的快速性，以3個(gè)真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集作為測(cè)試集，實(shí)驗(yàn)結(jié)果表明MRLA算法能夠有效實(shí)現(xiàn)社會(huì)網(wǎng)絡(luò)的聚類(lèi)分析。

社會(huì)網(wǎng)絡(luò)；聚類(lèi)；Memetic算法；強(qiáng)弱關(guān)聯(lián)學(xué)習(xí)

0 引言

作為交叉學(xué)科的典范，復(fù)雜網(wǎng)絡(luò)理論不僅為解決各領(lǐng)域優(yōu)化問(wèn)題提供了新視角和新方法，同時(shí)其本身所具有的豐富內(nèi)涵，也是科學(xué)研究的對(duì)象。復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)分析是其中一個(gè)重要的研究?jī)?nèi)容，這當(dāng)中復(fù)雜網(wǎng)絡(luò)聚類(lèi)問(wèn)題，也稱(chēng)為復(fù)雜網(wǎng)絡(luò)社團(tuán)挖掘(社團(tuán)檢測(cè)，社區(qū)挖掘，社區(qū)檢測(cè))吸引了廣大研究學(xué)者的注意，并取得了很好的研究成果[1-5]。通過(guò)復(fù)雜網(wǎng)絡(luò)聚類(lèi)分析，可以對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、功能特征、預(yù)測(cè)行為等方面進(jìn)行有效的探測(cè)和指導(dǎo)[6]。

當(dāng)前，復(fù)雜網(wǎng)絡(luò)聚類(lèi)算法多是通過(guò)研究網(wǎng)絡(luò)的節(jié)點(diǎn)連接情況來(lái)探測(cè)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，而研究對(duì)象的實(shí)際意義、歷史背景等社會(huì)因素并未得到有效利用，造成了這些重要信息的資源浪費(fèi)。社會(huì)網(wǎng)絡(luò)中相關(guān)的社會(huì)學(xué)理論很好地描述總結(jié)了網(wǎng)絡(luò)中的節(jié)點(diǎn)關(guān)系與行為特征，因此以社會(huì)學(xué)理論為基礎(chǔ)通過(guò)相關(guān)算法的有效設(shè)計(jì)應(yīng)用來(lái)研究社會(huì)網(wǎng)絡(luò)中的結(jié)構(gòu)信息，指導(dǎo)社團(tuán)的檢測(cè)挖掘，有利于探索發(fā)現(xiàn)和理解應(yīng)用社團(tuán)結(jié)構(gòu)及其更深層次上的社會(huì)意義。

Memetic算法最早是由英國(guó)Newcastle大學(xué)的Moscato P教授于1989年提出[7]?；贒awkins提出的meme，“文化基因”一詞演化為Memetic，常被直接譯為密母算法，或是文化基因算法。Memetic算法是基于種群全局搜索和個(gè)體局部搜索的結(jié)合體，它代表的是一種算法框架，可以采用不同的搜索策略構(gòu)成各種Memetic算法[8]?；谄涮赜械乃阉鳈C(jī)制，密母算法的搜索效率優(yōu)于傳統(tǒng)進(jìn)化算法等單一模式的自然計(jì)算方法。

本文在Memetic算法的框架下，基于社會(huì)科學(xué)計(jì)算中的強(qiáng)弱關(guān)聯(lián)屬性理論設(shè)計(jì)了全新的局部關(guān)聯(lián)學(xué)習(xí)算子，構(gòu)造了Memetic關(guān)聯(lián)學(xué)習(xí)算法(Memetic Relationship Learning Algorithm，MRLA)來(lái)挖掘社會(huì)網(wǎng)絡(luò)的聚類(lèi)結(jié)構(gòu)。針對(duì)3個(gè)現(xiàn)實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。

1 基于Memetic算法和強(qiáng)弱關(guān)聯(lián)學(xué)習(xí)的社會(huì)網(wǎng)絡(luò)聚類(lèi)

1.1 社會(huì)網(wǎng)絡(luò)聚類(lèi)研究

社會(huì)網(wǎng)絡(luò)通常認(rèn)為是社會(huì)科學(xué)研究的范疇，但自從這個(gè)概念被人類(lèi)學(xué)家Barnes首次于1954年提出之后，隨著交叉學(xué)科的蓬勃發(fā)展，它成為各學(xué)科研究的重要對(duì)象[9]。社會(huì)網(wǎng)絡(luò)分析根源于物理學(xué)中的適應(yīng)性網(wǎng)絡(luò)，作為一種應(yīng)用性很強(qiáng)的社會(huì)學(xué)研究方法，它從整個(gè)種群的動(dòng)力學(xué)角度來(lái)分析考察其中的個(gè)體的連接關(guān)系與結(jié)構(gòu)特性。

作為復(fù)雜網(wǎng)絡(luò)的重要分支，社會(huì)網(wǎng)絡(luò)包含3個(gè)基本元素：角色，邊，以及關(guān)聯(lián)。角色，相當(dāng)于網(wǎng)絡(luò)的節(jié)點(diǎn)，在社會(huì)網(wǎng)絡(luò)中被賦予具體的內(nèi)涵，可以是人，物或事件本身。邊用來(lái)描述角色間的直接或間接關(guān)系。而關(guān)聯(lián)代表各角色間的相互影響程度和關(guān)系。

依據(jù)矩陣代數(shù)，概率論，計(jì)算機(jī)技術(shù)等，針對(duì)社會(huì)網(wǎng)絡(luò)研究問(wèn)題，廣大研究者發(fā)展出多種定量分析的方法，這當(dāng)中以社會(huì)網(wǎng)絡(luò)為研究對(duì)象的結(jié)構(gòu)分析得到大力發(fā)展[10]。許多針對(duì)不包含任何物理含義的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)分析的方法被拿來(lái)直接應(yīng)用到社會(huì)網(wǎng)絡(luò)中，雖然這些方法對(duì)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)挖掘也取得不錯(cuò)的研究成果，但是，社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)所特有的社會(huì)信息等背景知識(shí)均被完全拋棄，沒(méi)有有效利用，造成這部分知識(shí)的損失。本文的主要工作就是利用社會(huì)網(wǎng)絡(luò)中特有的信息來(lái)為算法的優(yōu)化搜索提供啟發(fā)式幫助。

1.2 Memetic算法

Memetic算法是近幾年新興并迅速發(fā)展的一種全局優(yōu)化算法[11]，它借用人類(lèi)文化基因進(jìn)化的思想，基于個(gè)體信息的選擇、利用和改造等機(jī)制，實(shí)現(xiàn)信息的傳播。從本質(zhì)而言，Memetic算法被認(rèn)為是一種全局搜索和局部搜索相結(jié)合的算法機(jī)制。作為一種針對(duì)復(fù)雜優(yōu)化問(wèn)題的通用系統(tǒng)，它提供的是一種算法框架，一個(gè)計(jì)算理念，簡(jiǎn)單將其看作混合遺傳算法、局部搜索或者拉馬克進(jìn)化算法都是片面的理解。在這個(gè)框架下，設(shè)計(jì)不同的搜索策略構(gòu)成各異的Memetic算法可以解決不同的優(yōu)化問(wèn)題[12]。

表1 Memetic算法流程Tab.1 Memetic algorithm

Memetic算法強(qiáng)調(diào)的是個(gè)體學(xué)習(xí)與局部搜索，作為算法的核心，它們直接關(guān)系到算法的性能。局部搜索策略可以采用模擬退火、爬山搜索、禁忌搜索等各種數(shù)學(xué)方法，也可以設(shè)計(jì)基于人工智能的各種算子作為局部搜索策略。表1給出一般Memetic算法的流程。

在Memetic算法中，當(dāng)種群中的個(gè)體分布廣泛遠(yuǎn)離最優(yōu)解時(shí)，全局優(yōu)化是算法的主要算子；當(dāng)個(gè)體收斂至最優(yōu)解附近時(shí)，就側(cè)重局部搜索。在算法中融入社會(huì)科學(xué)計(jì)算中的相關(guān)算子作為個(gè)體學(xué)習(xí)能力的強(qiáng)化補(bǔ)充，就構(gòu)成了Memetic社會(huì)學(xué)習(xí)算法。

1.3 社會(huì)科學(xué)計(jì)算中的強(qiáng)弱關(guān)聯(lián)屬性理論

社會(huì)網(wǎng)絡(luò)中依據(jù)節(jié)點(diǎn)的社會(huì)屬性，存在許多相關(guān)社會(huì)學(xué)理論。這其中典型的代表有強(qiáng)弱關(guān)聯(lián)屬性理論[13]，核心邊緣理論[14]，二級(jí)傳播理論[15]等。這些理論概括了社會(huì)網(wǎng)絡(luò)中存在的關(guān)系與網(wǎng)絡(luò)個(gè)性行為間的辯證內(nèi)涵，對(duì)深度刻畫(huà)社會(huì)網(wǎng)絡(luò)的屬性特征有重要作用。因此以社會(huì)學(xué)理論為出發(fā)點(diǎn)來(lái)研究復(fù)雜網(wǎng)絡(luò)中的局部結(jié)構(gòu)特征，指導(dǎo)社團(tuán)發(fā)現(xiàn)過(guò)程，將以節(jié)點(diǎn)實(shí)際社會(huì)關(guān)系及背景為著眼點(diǎn)，有益于發(fā)現(xiàn)和挖掘結(jié)合社會(huì)網(wǎng)絡(luò)實(shí)際情況的社團(tuán)結(jié)構(gòu)。本文主要考慮社會(huì)網(wǎng)絡(luò)中的強(qiáng)弱關(guān)聯(lián)現(xiàn)象，基于強(qiáng)弱關(guān)聯(lián)屬性構(gòu)造局域?qū)W習(xí)算子，進(jìn)而設(shè)計(jì)社會(huì)學(xué)習(xí)Memetic優(yōu)化算法。

強(qiáng)弱關(guān)聯(lián)屬性理論是由美國(guó)社會(huì)學(xué)家Granovetter M.在關(guān)聯(lián)強(qiáng)度的概念下提出[13]。他在研究人們找工作的過(guò)程中發(fā)現(xiàn)，往往都是平時(shí)聯(lián)系不多的人會(huì)提供對(duì)新工作有幫助的信息，而并非親人或身邊的朋友?；谶@一發(fā)現(xiàn)，他提出針對(duì)關(guān)聯(lián)強(qiáng)度的4個(gè)衡量角度：互動(dòng)時(shí)間、互惠次數(shù)、情感深淺和關(guān)系疏密，進(jìn)而將人們之間的關(guān)系屬性分為強(qiáng)關(guān)聯(lián)和弱關(guān)聯(lián)兩大類(lèi)。

強(qiáng)弱關(guān)聯(lián)屬性理論內(nèi)容如下所述。假設(shè)a，b，c三個(gè)體，其存在連接關(guān)系我們用符號(hào)∪來(lái)表示，若有a∪b，a∪c的關(guān)聯(lián)程度比較強(qiáng)，則b∪c存在關(guān)聯(lián)的概率就大，并且很可能是強(qiáng)關(guān)聯(lián)；若有a∪b，a∪c關(guān)聯(lián)較弱，則b∪c存在關(guān)聯(lián)的概率就小?？梢岳斫膺@里的關(guān)聯(lián)對(duì)應(yīng)于節(jié)點(diǎn)組成的社團(tuán)之間的連接情況，那么，強(qiáng)關(guān)聯(lián)有助于增加局域內(nèi)聚集度，弱關(guān)聯(lián)有助于維護(hù)整體結(jié)構(gòu)?；诖死碚摽芍蹶P(guān)聯(lián)在劃分社團(tuán)結(jié)構(gòu)中有重要作用。針對(duì)具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)而言，節(jié)點(diǎn)間的弱關(guān)聯(lián)是連通二社團(tuán)的中介，相當(dāng)于局部意義的“橋”，相應(yīng)地，強(qiáng)關(guān)聯(lián)則代表社團(tuán)內(nèi)部各節(jié)點(diǎn)的緊密連接。因此，在此理論中，將關(guān)聯(lián)的強(qiáng)弱對(duì)應(yīng)于社團(tuán)結(jié)構(gòu)中連接邊的多少。關(guān)聯(lián)強(qiáng)時(shí)，對(duì)應(yīng)的連接邊便多，此時(shí)即為一個(gè)社團(tuán)結(jié)構(gòu)的內(nèi)部；關(guān)聯(lián)弱時(shí)，相當(dāng)于節(jié)點(diǎn)間連接邊少，此時(shí)為各社團(tuán)之間的情況。

2 Memetic關(guān)聯(lián)學(xué)習(xí)算法

基于上述基礎(chǔ)理論，在免疫M(jìn)emetic算法的大框架下，結(jié)合社會(huì)科學(xué)計(jì)算中的強(qiáng)弱關(guān)聯(lián)屬性理論設(shè)計(jì)全新的局部關(guān)聯(lián)學(xué)習(xí)算子，在此基礎(chǔ)上構(gòu)造Memetic關(guān)聯(lián)學(xué)習(xí)算法(Memetic Relationship Learning Algorithm，MRLA)來(lái)挖掘社會(huì)網(wǎng)絡(luò)的聚類(lèi)結(jié)構(gòu)。

2.1 MRLA編碼方式

針對(duì)社會(huì)網(wǎng)絡(luò)問(wèn)題，MRLA算法采用直接編碼方式，網(wǎng)絡(luò)G的劃分相當(dāng)于一個(gè)整數(shù)字符串，即為種群中的一個(gè)個(gè)體，記為：

(1)

其中ai表示節(jié)點(diǎn)i的類(lèi)別標(biāo)記，n為網(wǎng)絡(luò)規(guī)模，有ai∈[1,n]，具有相同類(lèi)別標(biāo)記的節(jié)點(diǎn)可以認(rèn)為是處于同一社區(qū)內(nèi)。這種方式編碼產(chǎn)生的算法結(jié)果表示社團(tuán)的數(shù)目，因此不需提前指定網(wǎng)絡(luò)的社團(tuán)數(shù)目。當(dāng)ai=n時(shí)，每個(gè)節(jié)點(diǎn)各自為一個(gè)社團(tuán)，是社團(tuán)結(jié)構(gòu)的最底層。另外需指出的是，不同的編碼可能代表相同的社團(tuán)劃分，這是由于社團(tuán)結(jié)構(gòu)只與類(lèi)別標(biāo)記有關(guān)，相同的標(biāo)記屬于同一類(lèi)，而與標(biāo)記具體的數(shù)字無(wú)關(guān)。

2.2 MRLA親和度函數(shù)設(shè)計(jì)

MRLA采用模塊度函數(shù)作為算法的親和度函數(shù)，如式(2)所示。雖然本文研究對(duì)象是社會(huì)網(wǎng)絡(luò)拓?fù)?，但是它本質(zhì)上也可以抽象為節(jié)點(diǎn)和連接邊表示的復(fù)雜網(wǎng)絡(luò)，因此復(fù)雜網(wǎng)絡(luò)的社團(tuán)分析方法對(duì)于它都是適用的。在原有理論的基礎(chǔ)上，考慮社會(huì)網(wǎng)絡(luò)中特有的社會(huì)學(xué)屬性，設(shè)計(jì)相應(yīng)的局部學(xué)習(xí)算子，來(lái)加以利用這些常常被拋棄的有效信息。下面具體介紹免疫基因算子和局部關(guān)聯(lián)學(xué)習(xí)算子。

(2)

2.3 MRLA進(jìn)化算子設(shè)計(jì)

(3)

2.4 Memetic關(guān)聯(lián)學(xué)習(xí)策略

基于計(jì)算社會(huì)學(xué)中的強(qiáng)弱關(guān)聯(lián)理論，在同一社團(tuán)結(jié)構(gòu)中的各節(jié)點(diǎn)連接緊密，其屬性也都基本相似，我們引入強(qiáng)關(guān)聯(lián)節(jié)點(diǎn)的定義：

定義1 在一個(gè)社會(huì)網(wǎng)絡(luò)的某個(gè)社團(tuán)結(jié)構(gòu)中，大部分節(jié)點(diǎn)都屬于同一個(gè)社團(tuán)，這些屬于同一社團(tuán)的鄰居節(jié)點(diǎn)稱(chēng)為強(qiáng)關(guān)聯(lián)節(jié)點(diǎn)，記為vidomi，它們對(duì)應(yīng)的社團(tuán)類(lèi)別標(biāo)簽稱(chēng)為優(yōu)勢(shì)社團(tuán)策略xidomi。

與之相對(duì)應(yīng)的弱關(guān)聯(lián)節(jié)點(diǎn)定義如下：

定義2 一個(gè)社團(tuán)結(jié)構(gòu)中的節(jié)點(diǎn)存在與社團(tuán)之外的節(jié)點(diǎn)的連接邊，即該節(jié)點(diǎn)的鄰居不全是或者說(shuō)有部分不是強(qiáng)關(guān)聯(lián)節(jié)點(diǎn)時(shí)，此節(jié)點(diǎn)稱(chēng)為弱關(guān)聯(lián)節(jié)點(diǎn)。弱關(guān)聯(lián)節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)有重要意義，它們維系著網(wǎng)絡(luò)的整體結(jié)構(gòu)。舉例而言，網(wǎng)絡(luò)中的hub節(jié)點(diǎn)即為弱關(guān)聯(lián)節(jié)點(diǎn)。

基于上述兩個(gè)定義，MRLA算法的局部關(guān)聯(lián)學(xué)習(xí)策略如下所述：對(duì)被選擇個(gè)體的每一位進(jìn)行關(guān)聯(lián)策略的學(xué)習(xí)，令搜索位的類(lèi)別標(biāo)記等于該位的鄰居中強(qiáng)關(guān)聯(lián)節(jié)點(diǎn)的優(yōu)勢(shì)社團(tuán)策略。引入?yún)?shù)λ表示每個(gè)個(gè)體進(jìn)行關(guān)聯(lián)學(xué)習(xí)策略的次數(shù)，λ越大，執(zhí)行關(guān)聯(lián)學(xué)習(xí)的次數(shù)越多，相應(yīng)地，局部搜索進(jìn)行得越多。這里經(jīng)過(guò)經(jīng)驗(yàn)分析取λ=5。

局部關(guān)聯(lián)學(xué)習(xí)策略充分利用了社會(huì)網(wǎng)絡(luò)中鄰居連接情況的先驗(yàn)知識(shí)，更加符合真實(shí)社會(huì)網(wǎng)絡(luò)的實(shí)際情況。另外，這種搜索以節(jié)點(diǎn)的強(qiáng)關(guān)聯(lián)鄰居為參照物，而不需網(wǎng)絡(luò)的全局信息，大大提高了局部學(xué)習(xí)的效率減少了搜索時(shí)間。局部關(guān)聯(lián)學(xué)習(xí)算子的流程如表2所示。

2.5 MRLA算法流程

基于Memetic算法的框架，結(jié)合社會(huì)網(wǎng)絡(luò)的強(qiáng)弱關(guān)聯(lián)屬性理論設(shè)計(jì)相關(guān)算子，提出Memetic關(guān)聯(lián)學(xué)習(xí)算法，主要流程如表3所示。

表2 局部關(guān)聯(lián)學(xué)習(xí)算法流程Tab.2 Local Relationship Learning Algorithm

表3 MRLA算法流程Tab.3 Memetic Relationship Learning Algorithm

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

本文將MRLA算法應(yīng)用到3個(gè)真實(shí)社會(huì)網(wǎng)絡(luò)中挖掘它們的社團(tuán)結(jié)構(gòu)以驗(yàn)證算法的有效性，分別是寬吻海豚社交網(wǎng)絡(luò)、Zachary空手道俱樂(lè)部網(wǎng)絡(luò)以及2000年美國(guó)大學(xué)足球聯(lián)賽網(wǎng)絡(luò)。實(shí)驗(yàn)中算法參數(shù)設(shè)置如下：種群規(guī)模n=100，增殖規(guī)模上限Nc=5，變異概率pm=0.6，關(guān)聯(lián)學(xué)習(xí)參數(shù)λ=5，針對(duì)3組測(cè)試問(wèn)題，分別獨(dú)立運(yùn)行30次，記錄算法的最優(yōu)結(jié)果平均值。下面分別介紹這3個(gè)網(wǎng)絡(luò)實(shí)驗(yàn)及結(jié)果分析。

3.1 寬吻海豚實(shí)驗(yàn)結(jié)果與分析

寬吻海豚社交網(wǎng)絡(luò)刻畫(huà)的是在新西蘭Doubtful Sound地區(qū)生活的寬吻海豚之間的社會(huì)關(guān)系，由生物學(xué)家Lusseau D.對(duì)62只海豚進(jìn)行1994年到2001年連續(xù)7年的時(shí)間觀察獲得[16]。根據(jù)海豚的不同年齡，他們將其分為二部分，其中二個(gè)海豚之間存在頻繁的接觸關(guān)系則在網(wǎng)絡(luò)中代表海豚的相應(yīng)節(jié)點(diǎn)間賦予一條連接邊，該網(wǎng)絡(luò)存在159條連接邊。

圖1給出寬吻海豚網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果。從圖1a中可以看到該網(wǎng)絡(luò)分為上、下二個(gè)社團(tuán)結(jié)構(gòu)，該社團(tuán)劃分對(duì)應(yīng)的網(wǎng)絡(luò)最大模塊度Q值為Qmax=0.378 703 87，當(dāng)Q為最大值時(shí)，相應(yīng)的網(wǎng)絡(luò)劃分為2個(gè)社團(tuán)。圖1b給出Q值進(jìn)化過(guò)程曲線(xiàn)，可以看到MRLA算法進(jìn)化78代就可以找到Q值最優(yōu)解。為了更形象細(xì)致考察網(wǎng)絡(luò)的結(jié)構(gòu)，圖1c給出該網(wǎng)絡(luò)的聚類(lèi)層次樹(shù)結(jié)構(gòu)?？梢钥吹?，層次樹(shù)的左端對(duì)應(yīng)網(wǎng)絡(luò)各節(jié)點(diǎn)，通過(guò)層次樹(shù)結(jié)構(gòu)逐層合并，就可以得到不同聚類(lèi)尺度的社團(tuán)結(jié)構(gòu)。層次樹(shù)結(jié)構(gòu)可以清晰地刻畫(huà)整個(gè)網(wǎng)絡(luò)的層次結(jié)構(gòu)特性?？梢钥吹剿惴ǐ@得的2個(gè)社團(tuán)結(jié)構(gòu)與Lusseau研究得到的實(shí)際劃分相一致，驗(yàn)證了MRLA算法在社團(tuán)檢測(cè)方面的有效性。

圖1 寬吻海豚網(wǎng)絡(luò)結(jié)構(gòu)實(shí)驗(yàn)結(jié)果Fig.1 The results on dolphin network structure

3.2 Zachary空手道俱樂(lè)部網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果與分析

Zachary空手道俱樂(lè)部網(wǎng)絡(luò)是一個(gè)經(jīng)典社會(huì)網(wǎng)絡(luò)實(shí)例，被廣泛用來(lái)測(cè)試社團(tuán)檢測(cè)算法的性能[17]。該網(wǎng)絡(luò)實(shí)際是美國(guó)一所大學(xué)的某個(gè)空手道俱樂(lè)部，其中有34名成員。Zachary W在兩年時(shí)間內(nèi)通過(guò)觀察成員間關(guān)系得到該網(wǎng)絡(luò)模型。同樣地，網(wǎng)絡(luò)中節(jié)點(diǎn)代表每個(gè)成員，兩節(jié)點(diǎn)間有連接邊表示這兩個(gè)成員存在來(lái)往關(guān)系。在研究觀察過(guò)程中，Zachary發(fā)現(xiàn)俱樂(lè)部管理層與教練因費(fèi)用問(wèn)題產(chǎn)生分歧，最終導(dǎo)致俱樂(lè)部分裂成兩個(gè)以管理層和教練分別為中心的子網(wǎng)絡(luò)。對(duì)該網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如圖2。

圖2a描述了Zachary網(wǎng)絡(luò)的二部分劃分以及四部分劃分。用圓形節(jié)點(diǎn)和方形節(jié)點(diǎn)分別代表分裂的二個(gè)子結(jié)構(gòu)。由實(shí)驗(yàn)結(jié)果可知，這二個(gè)子結(jié)構(gòu)中分別又各自包含2個(gè)社團(tuán)結(jié)構(gòu)，采用不同的顏色給予標(biāo)示，因此4種顏色代表了該網(wǎng)絡(luò)的四社團(tuán)劃分。對(duì)比真實(shí)的Zachary網(wǎng)絡(luò)社團(tuán)情況，只有編號(hào)為10的節(jié)點(diǎn)與實(shí)際情況不符。這是因?yàn)樵摴?jié)點(diǎn)處于不同社團(tuán)的交界處，而且與2個(gè)社團(tuán)的連接強(qiáng)弱關(guān)聯(lián)程度相同，這樣10號(hào)節(jié)點(diǎn)到底歸屬于哪個(gè)社團(tuán)是不能完全確定的?；诖耍琁MRLA算法得到的最終社團(tuán)劃分結(jié)果是可以接受的。

圖2 Zachary俱樂(lè)部網(wǎng)絡(luò)結(jié)構(gòu)實(shí)驗(yàn)結(jié)果Fig.2 The results on Zachary Karate Club network structure

圖2b給出模塊度的進(jìn)化曲線(xiàn)?？梢钥吹剿惴ㄖ恍?9代就可以找到最大模塊度，此時(shí)Qmax=0.418 820 39。同時(shí)，在圖2c給出網(wǎng)絡(luò)的層次樹(shù)結(jié)構(gòu)，可以看到該網(wǎng)絡(luò)節(jié)點(diǎn)從底層起，逐漸聚集形成4個(gè)較大的社團(tuán)，進(jìn)而這4個(gè)社團(tuán)又兩兩合并，形成2大社團(tuán)。這個(gè)結(jié)果與真實(shí)Zachary網(wǎng)絡(luò)的實(shí)際分裂情況一致，也驗(yàn)證了MRLA算法的有效性和正確性。

3.3 美國(guó)大學(xué)足球聯(lián)賽網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果與分析

2000年美國(guó)大學(xué)的某次美式足球聯(lián)賽網(wǎng)絡(luò)是這個(gè)網(wǎng)絡(luò)模型的數(shù)據(jù)來(lái)源，由Girvan和Newman編譯制成[18]。此網(wǎng)絡(luò)包含115個(gè)足球隊(duì)，613條連接邊代表著所連兩隊(duì)存在比賽關(guān)系。這些球隊(duì)被分為12組，比賽按照分組進(jìn)行，每支球隊(duì)平均打7場(chǎng)組內(nèi)比賽，4場(chǎng)組外比賽，由此各球隊(duì)的比賽關(guān)系形成一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)，常常被廣大研究者作為基準(zhǔn)測(cè)試網(wǎng)絡(luò)。本文也利用此網(wǎng)絡(luò)來(lái)檢測(cè)所提算法的正確性。

MRLA算法對(duì)該社會(huì)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如圖3所示。該網(wǎng)絡(luò)具有明顯的社團(tuán)結(jié)構(gòu)。由圖3a可以看到，整個(gè)網(wǎng)絡(luò)包括11個(gè)社團(tuán)結(jié)構(gòu)，這些子結(jié)構(gòu)間又互相連接，關(guān)系復(fù)雜。模塊度函數(shù)Q的進(jìn)化曲線(xiàn)如圖3b，算法只需60代即可求得Qmax=0.595 940 59。

圖3 美式足球聯(lián)賽網(wǎng)絡(luò)結(jié)構(gòu)實(shí)驗(yàn)結(jié)果Fig.3 The results on football league network structure

圖3c展示了足球聯(lián)賽網(wǎng)絡(luò)的層次樹(shù)結(jié)構(gòu)。從圖中可以看到，在整個(gè)結(jié)構(gòu)的最底層包含11個(gè)小社團(tuán)，低層次的社團(tuán)依據(jù)其關(guān)聯(lián)程度逐步合并，直至并為整個(gè)網(wǎng)絡(luò)。層次樹(shù)圖可以清晰地展示整個(gè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)關(guān)系。與真實(shí)足球聯(lián)賽網(wǎng)絡(luò)劃分對(duì)比，可知社團(tuán)結(jié)構(gòu)中節(jié)點(diǎn)集“1，94，5，42，17，105，10，24”(記為社團(tuán)C1)，“12，25，70，29，91，51”(記為社團(tuán)C2)，以及節(jié)點(diǎn)81、節(jié)點(diǎn)37不實(shí)際劃分不同。這是因?yàn)镃1，C2間連接密集，代表這里面的球隊(duì)間進(jìn)行比賽的次數(shù)較多，合并為一個(gè)社團(tuán)。而在圖3c中可知C1與C2都是單獨(dú)的模塊，這也是正確的社團(tuán)劃分結(jié)果。另外，節(jié)點(diǎn)37，43，81，83和91，由于他們之間進(jìn)行比賽較少所以連接邊較少，導(dǎo)致算法將這5個(gè)節(jié)點(diǎn)按照其自身關(guān)聯(lián)狀態(tài)劃分到其他模塊中。這種情況下，結(jié)合實(shí)際網(wǎng)絡(luò)連接情況而言，MRLA算法的社團(tuán)劃分結(jié)果我們認(rèn)為是準(zhǔn)確的。

4 總結(jié)與展望

復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)是其重要的拓?fù)鋵傩灾?，在研究其結(jié)構(gòu)劃分時(shí)通常只關(guān)注由實(shí)際網(wǎng)絡(luò)抽象出來(lái)的節(jié)點(diǎn)及其連接邊之間的關(guān)系，而對(duì)于網(wǎng)絡(luò)本身所代表的社會(huì)屬性等背景知識(shí)沒(méi)有充分利用。本文以社會(huì)網(wǎng)絡(luò)為研究對(duì)象，深入理解網(wǎng)絡(luò)中節(jié)點(diǎn)間的關(guān)聯(lián)屬性特征，受社會(huì)計(jì)算學(xué)中的強(qiáng)弱關(guān)聯(lián)理論啟發(fā)，設(shè)計(jì)了節(jié)點(diǎn)的局部關(guān)聯(lián)學(xué)習(xí)算子，進(jìn)而提出Memetic局部關(guān)聯(lián)學(xué)習(xí)算法。通過(guò)對(duì)三組實(shí)際社會(huì)網(wǎng)絡(luò)模型的測(cè)試，新算法都能夠較快地找到模塊度函數(shù)的最優(yōu)值并進(jìn)行正確的網(wǎng)絡(luò)社團(tuán)劃分，驗(yàn)證了MRLA算法的有效性。今后將進(jìn)一步研究社會(huì)計(jì)算理論在網(wǎng)絡(luò)結(jié)構(gòu)挖掘中的應(yīng)用，為網(wǎng)絡(luò)科學(xué)的結(jié)構(gòu)分析和控制應(yīng)用提供新的技術(shù)選擇。

[1]Newman M E J. Detecting community structure in networks[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2004, 38(2): 321-330.

[2]Lancichinetti A, Fortunato S. Community detection algorithms: a comparative analysis[J]. Physical review E, 2009, 80(5): 056117.

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

[5]李曉佳, 張鵬, 狄增如,等.復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu). 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué). 2008, 5(3): 19-42. Li Xiaojia, Zhang Peng, Di Zengru, et al. Community structure in complex networks[J]. Complex systems and complexity science, 2008, 5(3): 19-42.

[6]Li D Y, Xiao L, Han Y, et al. Network thinking and network intelligence[J]. Web Intelligence Meets Brain Informatics. Springer, 2007, 36-58.

[7]Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memeticalgorithms[J]. Caltech concurrent computation program, C3P Report, 1989, 826: 1989.

[8]Wang S, Wang L. An estimation of distribution algorithm-based memeticalgorithm for the distributed assembly permutation flow-shop scheduling problem[J]. IEEE Transactions on System, Man, Cybernetics, 2016, 46(1):139-149.

[9]Lazer D, Pentland A, Adamic L, et al. Computational social science [J]. Science,2009, 323(1):721-723.

[10] Giles J. Computational social science: making the links [J]. Nature, 2012,488(7412):448-450.

[11] Ong Y S, Lim M H, Chen X. Research frontier-memetic computation—past, present & future[J]. IEEE Computational Intelligence Magazine, 2010, 5(2): 24.

[12] Cai Q, Ma L, Gong M, et al. A survey on network community detection based on evolutionary computation[J]. International Journal of Bio-Inspired Computation, 2016, 8(2): 84-98.

[13] Granovetter M S. The strength of weak ties[J]. American Journal of Sociology, 1973: 1360-1380.

[14] Friedmann J. The world city hypothesis[J]. Development and Change, 1986, 17(1): 69-83.

[15] Guest L. Review of the people′s choice: how the voter makes up his mind in a presidential campaign.[J]. American Journal of Sociology, 1946, 77(51):177-186.

[16] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.

[17] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977: 452-473.

[18] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

(責(zé)任編輯 李進(jìn))

A Social Network Clustering Analysis Algorithm Based on Memetic Algorithm and Relationship Learning

SUN Yifei1a， YAO Ruoxia1b， JIAO Licheng2

(1.a.School of Physics and Information Technology, b.School of Computer Science, Shaanxi Normal University, Xi’an 710119;2.Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education,Xidian University, Xi’an 710071)

In social networks, the property of society has not been fully exploited. Meanwhile, learning ability for network structure optimization is weak. So a new Memetic Relationship Learning Algorithm (MRLA) has been proposed. This paper studied the fundamentals and basic procedure of MRLA, and effectively utilized the social attribute information. The new algorithm integrated the accuracy of Memetic computation and the quickness of social relational learning. The experimental results of three real-world web data sets show the validity and feasibility of the proposed algorithms.

social network； cluster； memetic algorithm； relationship learning

1672-3813(2017)02-0089-08；

10.13306/j.1672-3813.2017.02.013

2016-11-01；

2017-04-14

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(2013CB329402)；國(guó)家自然科學(xué)基金(11471004)；中央高?；究蒲袠I(yè)務(wù)費(fèi)(GK201603014)；陜西師范大學(xué)教學(xué)模式創(chuàng)新與實(shí)踐專(zhuān)項(xiàng)基金(JSJX2016Q014)

孫奕菲(1983-)，女，河北唐山人，博士，講師，主要研究方向?yàn)橛?jì)算智能，復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)挖掘及智能信息處理。

TP18

A