孫奕菲，姚若俠，焦李成

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

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

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

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

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

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

0 引言

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

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

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

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

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

1.1 社會網(wǎng)絡(luò)聚類研究

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

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

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

1.2 Memetic算法

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

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

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

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

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

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

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

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

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

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

2.1 MRLA編碼方式

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

(1)

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

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

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

(2)

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

(3)

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

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

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

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

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

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

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

2.5 MRLA算法流程

基于Memetic算法的框架，結(jié)合社會網(wǎng)絡(luò)的強弱關(guān)聯(lián)屬性理論設(shè)計相關(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 實驗結(jié)果與分析

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

3.1 寬吻海豚實驗結(jié)果與分析

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

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

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

3.2 Zachary空手道俱樂部網(wǎng)絡(luò)實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

4 總結(jié)與展望

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

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

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

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

TP18

A