邰昌鴻，劉向陽

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

0 引 言

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

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

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

1 多層網(wǎng)絡(luò)與社區(qū)檢測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ū)檢測問題。復(fù)雜網(wǎng)絡(luò)圖中的局部社區(qū)檢測問題是指對特定于查詢節(jié)點且依賴于有關(guān)網(wǎng)絡(luò)結(jié)構(gòu)的有限信息的社區(qū)的識別。局部社區(qū)檢測算法通常實現(xiàn)某種策略，該策略在每個步驟考慮來自三個集合之一的節(jié)點，即：正在構(gòu)建的社區(qū)(用種子節(jié)點初始化)節(jié)點集B、作為社區(qū)中節(jié)點的鄰居但不屬于該社區(qū)的外殼節(jié)點集S以及網(wǎng)絡(luò)的未探索部分節(jié)點集[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)重劃分的方式對網(wǎng)絡(luò)層加權(quán)，即認為所有網(wǎng)絡(luò)層重要性相同，或者需要預(yù)先設(shè)置權(quán)重值對特定網(wǎng)絡(luò)加權(quán)，這與真實的網(wǎng)絡(luò)的拓撲特征并不相符，也無法適用于大型網(wǎng)絡(luò)的權(quán)重值衡量。

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

2.1 MWLCD算法

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

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

(4)

其中，LCint(G)是與G內(nèi)節(jié)點之間的鏈路密度成正比的函數(shù)，LCext(G)是與G內(nèi)節(jié)點與G外節(jié)點之間的鏈路密度成正比的函數(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)

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

(7)

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

(8)

(9)

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

(10)

其中，dc為截斷距離，是可變參數(shù)，實驗中取所有節(jié)點之間距離的前2%，dij是節(jié)點之間的距離。

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

(11)

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

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

(12)

(13)

即計算每層中前n個局部密度值與偏移量乘積值最大的節(jié)點之和在所有層中的比值，再計算方差衡量層與層之間比值的波動情況，當方差超過設(shè)置的波動閾值s2(W2)=0.5時則表明層與層之間的波動值較大，此時應(yīng)加大第二加權(quán)方案比重，否則加大第一加權(quán)方案比重。依據(jù)波動值變化對網(wǎng)絡(luò)層加權(quán)的影響，該文設(shè)置了一個超參數(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)方案按方差波動變化是否超過閾值決定如何分配其占比。

2.3 核心節(jié)點計算

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

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

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

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

2.4 MWLCD算法步驟

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

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

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

輸出：基于核心節(jié)點劃分的社區(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é)點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)拓撲結(jié)構(gòu)不同的多層復(fù)雜網(wǎng)絡(luò)。步驟5引入局部密度算法計算節(jié)點綜合加權(quán)局部密度ρ并隨著數(shù)據(jù)集的更新而更新，步驟6則在隨機獲得種子節(jié)點v0后，依據(jù)下文第3章中對于選取種子節(jié)點不同鄰域范圍?內(nèi)計算社區(qū)核心節(jié)點獲取的社區(qū)劃分結(jié)果進行分析，確定鄰域范圍并用于計算核心節(jié)點集{vi}。步驟7確定并隨社區(qū)劃分更新邊界集B和外殼集S，步驟8～步驟13為社區(qū)劃分過程，步驟14～步驟19為算法劃分結(jié)果的評估過程,當社區(qū)劃分結(jié)果最優(yōu)時輸出社區(qū)C。

3 實驗結(jié)果和分析

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

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

3.2 評價函數(shù)

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

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

θijCjsr}θ(gis,gjr)

(15)

3.3 參數(shù)?的分析

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

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

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

3.4 社區(qū)劃分評估

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

表1 MWLCD與ML-LCD算法運行50次模塊度均值

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

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

具體如圖2所示。

圖2 MWLCD與ML-LCD算法運行50次模塊度值

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

4 結(jié)束語

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