基于網(wǎng)絡(luò)層加權(quán)的多層復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)算法

邰昌鴻，劉向陽(yáng)

(河海大學(xué) 理學(xué)院，江蘇 南京 211100)

0 引 言

多層網(wǎng)絡(luò)是由多個(gè)圖(稱(chēng)為層)組成的網(wǎng)絡(luò)，這些圖共享同一組節(jié)點(diǎn)，但它們的邊不同。多層網(wǎng)絡(luò)中的邊緣被分為層內(nèi)邊和層間邊。多層網(wǎng)絡(luò)社區(qū)檢測(cè)的研究方法主要可分為三大類(lèi)：展平方法，將多層的信息折疊成單一層，再使用傳統(tǒng)的單層算法檢測(cè)社區(qū)。聚合方法，發(fā)現(xiàn)每一層中的社區(qū)，然后通過(guò)某種聚合機(jī)制將它們合并。直接方法，通過(guò)優(yōu)化一些質(zhì)量評(píng)估標(biāo)準(zhǔn)而不進(jìn)行扁平化處理來(lái)直接檢測(cè)多層網(wǎng)絡(luò)上的社區(qū)結(jié)構(gòu)[1]。

其中基于展平方法的代表算法MCD-Berlingerio[2]，設(shè)計(jì)了一個(gè)用于查找和表征多維社區(qū)的框架，該框架基于從多維網(wǎng)絡(luò)到一維網(wǎng)絡(luò)的映射，并基于現(xiàn)有的一維社區(qū)發(fā)現(xiàn)算法對(duì)其的應(yīng)用，還可以恢復(fù)原來(lái)存在的多維社區(qū)結(jié)構(gòu)；基于聚合方法的代表算法PMM[3]，主要可以分為兩步：第一步是提取每層網(wǎng)絡(luò)的模塊度矩陣的特征向量并獲得級(jí)聯(lián)的向量，然后采用PCA(principal component analysis)得到一個(gè)較低維的嵌入，捕獲網(wǎng)絡(luò)所有維度(層)上的主模式；第二步是對(duì)所有節(jié)點(diǎn)的低維嵌入表示執(zhí)行k-means算法，以找出離散的社區(qū)劃分；基于直接方法的代表算法Gen Louvain(GL)[4]，使用多層切片模塊擴(kuò)展了經(jīng)典的Louvain方法，因此每個(gè)節(jié)點(diǎn)層元組都分別分配給一個(gè)社區(qū)；多層局部社區(qū)檢測(cè)算法ML-LCD[5]，在全局信息未知的情況下，通過(guò)優(yōu)化局部社區(qū)函數(shù)(即內(nèi)部鏈接密度和外部鏈接密度比)標(biāo)識(shí)特定節(jié)點(diǎn)所在的社區(qū)，然后通過(guò)將特定層的貢獻(xiàn)值與鏈接密度比進(jìn)行線性組合將局部社區(qū)函數(shù)擴(kuò)展到多層網(wǎng)絡(luò)[6]。

但上述關(guān)于多層復(fù)雜網(wǎng)絡(luò)全局或局部社區(qū)檢測(cè)的算法，均忽略了復(fù)雜網(wǎng)絡(luò)層與層之間的重要性差異，在真實(shí)的多層復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)往往并不是均勻分布在每一層中，而是往往存在多數(shù)層上包含較少的節(jié)點(diǎn)，而少數(shù)層卻包含更多的節(jié)點(diǎn)的情況，例如航空網(wǎng)絡(luò)中的昂貴航線與廉價(jià)航線的分布。因此當(dāng)移除少數(shù)節(jié)點(diǎn)所在層時(shí)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響有限，但當(dāng)多數(shù)節(jié)點(diǎn)層被移除時(shí)，就可能會(huì)造成網(wǎng)絡(luò)的崩潰，這說(shuō)明復(fù)雜網(wǎng)絡(luò)層之間存在重要性差異；同時(shí)局部社區(qū)檢測(cè)算法的效果多依賴(lài)于選取種子節(jié)點(diǎn)時(shí)其所處社區(qū)位置的好壞，當(dāng)其位于社區(qū)核心時(shí)劃分效果較好，反之則較差；為避免種子節(jié)點(diǎn)的隨機(jī)性造成劃分結(jié)果差距較大，該文提出一種新的局部社區(qū)檢測(cè)算法MWLCD，對(duì)多層復(fù)雜網(wǎng)絡(luò)層的重要性展開(kāi)分析，定義了基于層內(nèi)活躍節(jié)點(diǎn)占比及不同層包含重要節(jié)點(diǎn)占比兩種層加權(quán)方案，并基于層加權(quán)引入局部密度在隨機(jī)獲取的種子節(jié)點(diǎn)確定其所在社區(qū)的核心節(jié)點(diǎn)，從而完成了多層模塊度值更高且更加穩(wěn)定的社區(qū)劃分。

1 多層網(wǎng)絡(luò)與社區(qū)檢測(cè)ML-LCD算法

1.1 多層網(wǎng)絡(luò)

EL={(u,Li),(v,Lj)|u,v∈V∧Li,Lj∈L∧i=j}∪{(v,Li),(v,Lj)|u,v∈V∧Li,Lj∈L∧i≠j}

(1)

1.2 ML-LCD算法

Interdonato等人提出了第一種多層網(wǎng)絡(luò)上的局部社區(qū)發(fā)現(xiàn)算法ML-LCD(multi-layer local community detection)[5]，并定義了多層局部社區(qū)檢測(cè)問(wèn)題。復(fù)雜網(wǎng)絡(luò)圖中的局部社區(qū)檢測(cè)問(wèn)題是指對(duì)特定于查詢節(jié)點(diǎn)且依賴(lài)于有關(guān)網(wǎng)絡(luò)結(jié)構(gòu)的有限信息的社區(qū)的識(shí)別。局部社區(qū)檢測(cè)算法通常實(shí)現(xiàn)某種策略，該策略在每個(gè)步驟考慮來(lái)自三個(gè)集合之一的節(jié)點(diǎn)，即：正在構(gòu)建的社區(qū)(用種子節(jié)點(diǎn)初始化)節(jié)點(diǎn)集B、作為社區(qū)中節(jié)點(diǎn)的鄰居但不屬于該社區(qū)的外殼節(jié)點(diǎn)集S以及網(wǎng)絡(luò)的未探索部分節(jié)點(diǎn)集[5]。ML-LCD算法定義了三層算法框架，分別是基于層加權(quán)的ML-LCD-lwsim和基于層內(nèi)相似度的ML-LCD-wlsim以及層間相似度的ML-LCD-clsim。其中ML-LCD算法中的ML-LCD-wlsim和ML-LCD-clsim在性能上均低于ML-LCD-lwsim。

需要注意的是，雖然ML-LCD算法的第一層函數(shù)框架提到了層加權(quán)的概念，但該算法依然采用層均等權(quán)重劃分的方式對(duì)網(wǎng)絡(luò)層加權(quán)，即認(rèn)為所有網(wǎng)絡(luò)層重要性相同，或者需要預(yù)先設(shè)置權(quán)重值對(duì)特定網(wǎng)絡(luò)加權(quán)，這與真實(shí)的網(wǎng)絡(luò)的拓?fù)涮卣鞑⒉幌喾?，也無(wú)法適用于大型網(wǎng)絡(luò)的權(quán)重值衡量。

2 基于網(wǎng)絡(luò)層加權(quán)的多層局部社區(qū)檢測(cè)算法

2.1 MWLCD算法

基于ML-LCD算法第一層函數(shù)框架的層加權(quán)概念，該文提出了一種基于層加權(quán)的多層網(wǎng)絡(luò)社區(qū)檢測(cè)算法MWLCD。MWLCD算法量化了多層復(fù)雜網(wǎng)絡(luò)的層權(quán)重值，并引入局部密度算法在隨機(jī)獲取的種子節(jié)點(diǎn)周?chē)_定社區(qū)的核心節(jié)點(diǎn)，基于核心節(jié)點(diǎn)完成了模塊度更高且更穩(wěn)定的局部社區(qū)劃分。該文的主要任務(wù)是如何量化網(wǎng)絡(luò)層的權(quán)重值和確定核心節(jié)點(diǎn)，并基于核心節(jié)點(diǎn)選擇外殼集S中的最佳節(jié)點(diǎn)來(lái)添加到要識(shí)別的社區(qū)中。社區(qū)C的外殼集定義為：

S={v∈VC|?((u,Li),(v,Lj))∈

EL∧u∈C}

(2)

社區(qū)C的邊界集定義為：

B={u∈C|?((u,Li),(v,Lj))∈EL∧v∈S}

(3)

其中，Li與Lj可以為不同層，即B包含了耦合邊的邊界節(jié)點(diǎn)。

ML-LCD算法考慮要添加到正在構(gòu)建的社區(qū)的候選節(jié)點(diǎn)與到社區(qū)內(nèi)外部的節(jié)點(diǎn)鏈接的密度比作為懲罰函數(shù)[4,8-9]。在這項(xiàng)工作中，該文采用上述一般方法。

(4)

其中，LCint(G)是與G內(nèi)節(jié)點(diǎn)之間的鏈路密度成正比的函數(shù)，LCext(G)是與G內(nèi)節(jié)點(diǎn)與G外節(jié)點(diǎn)之間的鏈路密度成正比的函數(shù)。

給定GL=(VL,EL,V,L)和局部社區(qū)C，基于網(wǎng)絡(luò)層加權(quán)的局部社區(qū)內(nèi)部函數(shù)被定義為：

基于網(wǎng)絡(luò)層加權(quán)的局部社區(qū)外部函數(shù)定義為：

2.2 層加權(quán)

該文引入真實(shí)復(fù)雜網(wǎng)絡(luò)層的重要性差異，通過(guò)量化和歸一化處理，獲得復(fù)雜網(wǎng)絡(luò)各層的權(quán)重值。選取了兩種加權(quán)方案結(jié)合的方法來(lái)適應(yīng)不同拓?fù)浣Y(jié)構(gòu)的多層復(fù)雜網(wǎng)絡(luò)。

(7)

定義權(quán)重W1為：

(8)

(9)

第二種加權(quán)方案基于局部密度算法[11]。衡量不同網(wǎng)絡(luò)層包含重要節(jié)點(diǎn)的占比。衡量該比值需要計(jì)算節(jié)點(diǎn)在每一層中的局部密度與偏移量，節(jié)點(diǎn)局部密度定義如下：

(10)

其中，dc為截?cái)嗑嚯x，是可變參數(shù)，實(shí)驗(yàn)中取所有節(jié)點(diǎn)之間距離的前2%，dij是節(jié)點(diǎn)之間的距離。

節(jié)點(diǎn)偏移量定義如下：

(11)

即對(duì)于非局部密度最大的點(diǎn)，計(jì)算δi值，主要分兩步，找到所有局部密度比節(jié)點(diǎn)i高的節(jié)點(diǎn)；在這些點(diǎn)中找到距離節(jié)點(diǎn)i最近的節(jié)點(diǎn)j，節(jié)點(diǎn)i和j的距離就是δi的值。對(duì)于局部密度最大點(diǎn)，δi實(shí)際上是該點(diǎn)和其他所有節(jié)點(diǎn)距離值的最大值。

權(quán)重W2定義為：

(12)

(13)

即計(jì)算每層中前n個(gè)局部密度值與偏移量乘積值最大的節(jié)點(diǎn)之和在所有層中的比值，再計(jì)算方差衡量層與層之間比值的波動(dòng)情況，當(dāng)方差超過(guò)設(shè)置的波動(dòng)閾值s2(W2)=0.5時(shí)則表明層與層之間的波動(dòng)值較大，此時(shí)應(yīng)加大第二加權(quán)方案比重，否則加大第一加權(quán)方案比重。依據(jù)波動(dòng)值變化對(duì)網(wǎng)絡(luò)層加權(quán)的影響，該文設(shè)置了一個(gè)超參數(shù)k=0.999用于結(jié)合第一種加權(quán)方案與第二種加權(quán)方案，其定義如下：

W=kW1+(1-k)W2

(14)

其中，W代表層的綜合權(quán)重，W1代表第一加權(quán)方案權(quán)重，W2代表第二加權(quán)方案權(quán)重，超參數(shù)將兩種加權(quán)方案按方差波動(dòng)變化是否超過(guò)閾值決定如何分配其占比。

2.3 核心節(jié)點(diǎn)計(jì)算

基于2.1節(jié)獲取的網(wǎng)絡(luò)層權(quán)重為節(jié)點(diǎn)多層鏈接加權(quán)，該文通過(guò)引入局部密度獲取隨機(jī)種子節(jié)點(diǎn)v0所在社區(qū)的核心節(jié)點(diǎn)集{vi|i=1&i=2}。具體工作如下：

Step5:為防止搜索的核心節(jié)點(diǎn)位于不同社區(qū)造成兩社區(qū)合并，該文將核心節(jié)點(diǎn)限制在彼此δ階鄰域范圍內(nèi)，并在實(shí)驗(yàn)中將核心節(jié)點(diǎn)數(shù)目取1至2個(gè)。

Step6:確定核心節(jié)點(diǎn)后，該文將外殼集中節(jié)點(diǎn)按到核心節(jié)點(diǎn)距離從小到大排序，按距離大小選擇社區(qū)候選節(jié)點(diǎn)。

在第3章中將詳細(xì)分析在不同的種子節(jié)點(diǎn)鄰域內(nèi)搜索核心節(jié)點(diǎn)的劃分結(jié)果。

2.4 MWLCD算法步驟

MWLCD算法在局部社區(qū)劃分初始階段為網(wǎng)絡(luò)層設(shè)置權(quán)重，并基于網(wǎng)絡(luò)層加權(quán)獲取任意選取的節(jié)點(diǎn)周?chē)纳鐓^(qū)核心節(jié)點(diǎn)，并依據(jù)社區(qū)核心節(jié)點(diǎn)獲得局部社區(qū)劃分。MWLCD算法步驟如下：

算法：基于網(wǎng)絡(luò)層加權(quán)的多層復(fù)雜網(wǎng)絡(luò)局部社區(qū)檢測(cè)(MWLCD)算法。

輸入：多層網(wǎng)絡(luò)圖GL=(VL,EL,V,L)(可以是局部圖)及隨機(jī)節(jié)點(diǎn)v0

輸出：基于核心節(jié)點(diǎn)劃分的社區(qū)集合

3.ifs2(W1)>0.5:k=0.999 else:k=0.001

4.W←k*W1+(1-k)*W2

7.S←{v|(v,vi)∈El?l∈L∧min(Dist(v,vi))},C←B,B←{vi}

8.currLCint←LCint(C),currLCext←LCext(C) //使用公式(5)及公式(6)

9.currLC=currLCint/currLCext

10.Repeat

11.S←S{v*},v*←argmaxv∈SLC(C∪{v})//找到使LC(C)值最大的候選節(jié)點(diǎn)v*

12.B←B{u∈B|v*∈N(u)Λ/?(u,v):v∈S}

13.if LC(C∪{v*})>currLC∧LCint(C∪{v*})>currLCint←LCint(C)

14.N-C←N(v*)C,C←C∪{v*}

15.ifN-C≠φ

16.S←S∪N-C,B←B∪{v*}

17.B←B∪{u∈CB|N(u)?S}

18.currLC=currLCint/currLCext,currLCint←LCint(C),currLCext←LCext(C)

19.else

20.currLCext←LCext(C)

21.直到LC(C)值不再增大為止

22.returnC

步驟1～步驟6為MWLCD算法初始化階段，其中步驟1～步驟4用于量化多層網(wǎng)絡(luò)層權(quán)重值以及采用超參數(shù)結(jié)合了兩種不同的加權(quán)方法，以適應(yīng)拓?fù)浣Y(jié)構(gòu)不同的多層復(fù)雜網(wǎng)絡(luò)。步驟5引入局部密度算法計(jì)算節(jié)點(diǎn)綜合加權(quán)局部密度ρ并隨著數(shù)據(jù)集的更新而更新，步驟6則在隨機(jī)獲得種子節(jié)點(diǎn)v0后，依據(jù)下文第3章中對(duì)于選取種子節(jié)點(diǎn)不同鄰域范圍?內(nèi)計(jì)算社區(qū)核心節(jié)點(diǎn)獲取的社區(qū)劃分結(jié)果進(jìn)行分析，確定鄰域范圍并用于計(jì)算核心節(jié)點(diǎn)集{vi}。步驟7確定并隨社區(qū)劃分更新邊界集B和外殼集S，步驟8～步驟13為社區(qū)劃分過(guò)程，步驟14～步驟19為算法劃分結(jié)果的評(píng)估過(guò)程,當(dāng)社區(qū)劃分結(jié)果最優(yōu)時(shí)輸出社區(qū)C。

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

3.1 數(shù)據(jù)集

該文使用了4個(gè)真實(shí)世界的多層網(wǎng)絡(luò)數(shù)據(jù)集，即AUCS(節(jié)點(diǎn)數(shù)：61，邊數(shù)：620，層數(shù)：5，2016年)[12]，Airlines(節(jié)點(diǎn)數(shù)：417，邊數(shù)：3 588，層數(shù)：37，2013年)[13]，Remote Sensing(節(jié)點(diǎn)數(shù)：642，邊數(shù)：4 341，層數(shù)：5，2016年)[12]和Reality Mining(節(jié)點(diǎn)數(shù)：88，邊數(shù)：355，層數(shù)：3，2016年)[14-15]。

3.2 評(píng)價(jià)函數(shù)

對(duì)于社區(qū)劃分效果的評(píng)價(jià)是局部社區(qū)檢測(cè)極其重要的部分，在此處完成所有節(jié)點(diǎn)的社區(qū)劃分后，該文將采用經(jīng)典的多層社區(qū)檢測(cè)算法GL算法中提出的關(guān)于社區(qū)劃分質(zhì)量評(píng)估的多層模塊度函數(shù)，用于對(duì)文中算法完成劃分的社區(qū)質(zhì)量進(jìn)行評(píng)估。

多層模塊化質(zhì)量函數(shù)[4]定義如下：

θijCjsr}θ(gis,gjr)

(15)

3.3 參數(shù)?的分析

在實(shí)驗(yàn)的初始化部分，通過(guò)實(shí)驗(yàn)選取可變參數(shù)n的取值為數(shù)據(jù)集節(jié)點(diǎn)數(shù)目的5%，在使用層加權(quán)獲得節(jié)點(diǎn)多層綜合加權(quán)局部密度之后，隨機(jī)獲得種子節(jié)點(diǎn)并依據(jù)局部密度確定其所在社區(qū)的社區(qū)核心節(jié)點(diǎn)，在此處設(shè)置從種子節(jié)點(diǎn)?階鄰域范圍內(nèi)搜尋核心節(jié)點(diǎn)。圖1展現(xiàn)了4個(gè)數(shù)據(jù)集在種子節(jié)點(diǎn)不同鄰域范圍內(nèi)找到的核心節(jié)點(diǎn)最終劃分結(jié)果模塊值對(duì)比，為使鄰域足夠大該文分別選取種子節(jié)點(diǎn)3階、5階、7階鄰域與全局范圍內(nèi)的運(yùn)行50次實(shí)驗(yàn)結(jié)果作為對(duì)比。

圖1 數(shù)據(jù)集在不同鄰域參數(shù)?下運(yùn)行50次的模塊值

由圖1所示，選取種子節(jié)點(diǎn)?=3階以上鄰域范圍內(nèi)確定社區(qū)核心節(jié)點(diǎn)并基于此劃分的社區(qū)結(jié)果接近甚至高于全局社區(qū)劃分結(jié)果，數(shù)據(jù)集越大效果越明顯。實(shí)驗(yàn)結(jié)果說(shuō)明了局部社區(qū)檢測(cè)將全局社區(qū)檢測(cè)從一個(gè)全局優(yōu)化問(wèn)題轉(zhuǎn)化為局部?jī)?yōu)化問(wèn)題取得了接近甚至更好的社區(qū)劃分效果。實(shí)驗(yàn)發(fā)現(xiàn)當(dāng)選取鄰域超過(guò)三階后，社區(qū)劃分結(jié)果趨于一致，因此在初始化階段選取種子節(jié)點(diǎn)三階鄰域范圍內(nèi)的局部密度最大的兩個(gè)或者一個(gè)節(jié)點(diǎn)作為核心節(jié)點(diǎn)，并設(shè)置核心節(jié)點(diǎn)存在于彼此的β=3的鄰域范圍內(nèi)，以防止小社區(qū)合并的情況出現(xiàn)。

3.4 社區(qū)劃分評(píng)估

關(guān)于局部社區(qū)檢測(cè)的評(píng)估，對(duì)MWLCD算法和ML-LCD算法的性能結(jié)果進(jìn)行了相對(duì)較大次數(shù)的(平均50次)運(yùn)行，以減少由于它們的非確定性行為造成的偏差。表1為MWLCD算法與ML-LCD算法進(jìn)行社區(qū)劃分結(jié)果的平均值對(duì)比。

表1 MWLCD與ML-LCD算法運(yùn)行50次模塊度均值

如表1所示，MWLCD算法劃分的社區(qū)多層模塊度值平均值更高，其中黑體值表示最大的模塊度均值。

多層局部社區(qū)劃分往往依賴(lài)于種子節(jié)點(diǎn)的選取，但該文通過(guò)搜索核心節(jié)點(diǎn)減少了由于種子節(jié)點(diǎn)選取不同導(dǎo)致社區(qū)劃分結(jié)果波動(dòng)較大的情況，對(duì)MWLCD算法和ML-LCD算法的50次運(yùn)行結(jié)果進(jìn)行了可視化比較。

具體如圖2所示。

圖2 MWLCD與ML-LCD算法運(yùn)行50次模塊度值

圖2顯示，針對(duì)不同的數(shù)據(jù)集，MWLCD算法除在Airlines數(shù)據(jù)集中的表現(xiàn)略低于ML-LCD算法，在其他數(shù)據(jù)集上MWLCD算法均呈現(xiàn)了穩(wěn)定高效的劃分結(jié)果。

4 結(jié)束語(yǔ)

該文基于網(wǎng)絡(luò)層加權(quán)并引入局部密度算法，構(gòu)建了一個(gè)由隨機(jī)種子節(jié)點(diǎn)確定社區(qū)核心節(jié)點(diǎn)的多層社交網(wǎng)絡(luò)局部社區(qū)檢測(cè)算法(MWLCD)。避免了網(wǎng)絡(luò)規(guī)模增大導(dǎo)致的獲取全局信息困難的問(wèn)題，同時(shí)在局部社區(qū)檢測(cè)方面獲得了更好的社區(qū)劃分結(jié)果。使用4個(gè)真實(shí)的多層網(wǎng)絡(luò)數(shù)據(jù)集對(duì)MWLCD算法進(jìn)行了廣泛的實(shí)驗(yàn)，MWLCD算法表現(xiàn)出了更高的多層模塊性的社區(qū)與更強(qiáng)的魯棒性。未來(lái)的研究方向?qū)⒓杏诙鄬訌?fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)在層間相互作用所展現(xiàn)的層相關(guān)性等領(lǐng)域。