趙興旺 張珧溥 梁吉業(yè)

（山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 太原 030006）

（計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室（山西大學(xué)） 太原 030006）（zhaoxw84@163.com）

社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特征，即同一個(gè)社區(qū)內(nèi)節(jié)點(diǎn)之間連接緊密而不同社區(qū)間節(jié)點(diǎn)之間連接稀疏[1].例如，社交網(wǎng)絡(luò)的社區(qū)代表具有相似特征的人群，蛋白質(zhì)交互網(wǎng)絡(luò)中社區(qū)代表具有相似功能的生物組織模塊，萬維網(wǎng)中不同的社區(qū)代表不同功能的網(wǎng)頁.社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)分析挖掘中的重要任務(wù)之一，對(duì)于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析、功能分析和行為預(yù)測(cè)具有重要意義，已在社會(huì)學(xué)、生物信息學(xué)、交通系統(tǒng)等領(lǐng)域得到了廣泛應(yīng)用[2-4].例如，在社交網(wǎng)絡(luò)中，社區(qū)發(fā)現(xiàn)有助于分析個(gè)體的行為模式、信息的傳播方式和網(wǎng)絡(luò)的變化趨勢(shì)[5]；在生物網(wǎng)絡(luò)中，社區(qū)發(fā)現(xiàn)有助于分析屬于共同功能模塊的蛋白質(zhì)之間的相互作用[6]；在交通網(wǎng)絡(luò)中，社區(qū)發(fā)現(xiàn)可以通過將城市道路網(wǎng)絡(luò)劃分為多個(gè)支線網(wǎng)絡(luò)來實(shí)現(xiàn)對(duì)城市交通網(wǎng)絡(luò)的區(qū)域控制，從而緩解城市交通擁堵問題[7].

針對(duì)不同的應(yīng)用領(lǐng)域，研究者近年來已經(jīng)開展了廣泛研究，并提出了系列社區(qū)發(fā)現(xiàn)算法，主要包括：基于劃分的方法[8]、基于模塊度的方法[9-10]、基于譜的方法[11]、基于動(dòng)力學(xué)的方法[12]、基于標(biāo)簽傳播的方法[13]等.已有算法大多適用于單層網(wǎng)絡(luò)，然而現(xiàn)實(shí)世界中由多種類型節(jié)點(diǎn)及其連邊關(guān)系組成的多層網(wǎng)絡(luò)存在更為普遍[14].例如，社交網(wǎng)絡(luò)中的個(gè)體之間可能存在不同類型的社交關(guān)系，如好友、關(guān)注、評(píng)論、轉(zhuǎn)發(fā)等；在生物網(wǎng)絡(luò)中，對(duì)于某些生物體來說，完整的蛋白質(zhì)與蛋白質(zhì)相互作用涉及數(shù)千種蛋白質(zhì)分子之間多種不同的相互作用模式；在航空運(yùn)輸系統(tǒng)中，通過直飛航班對(duì)機(jī)場(chǎng)之間的連接建模，不同的商業(yè)航空公司可以被視為機(jī)場(chǎng)之間的不同連接模式.與單層網(wǎng)絡(luò)相比，多層網(wǎng)絡(luò)結(jié)構(gòu)具有更加豐富的拓?fù)湫畔?，有助于更為?zhǔn)確地探測(cè)網(wǎng)絡(luò)中蘊(yùn)含的社區(qū)結(jié)構(gòu).但是不同網(wǎng)絡(luò)層蘊(yùn)含的社區(qū)結(jié)構(gòu)之間既存在一定的相關(guān)性又存在異質(zhì)性，為社區(qū)發(fā)現(xiàn)任務(wù)帶來了新的挑戰(zhàn).

近年來，一些學(xué)者針對(duì)多層網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題已經(jīng)開展了有益探索，提出了相應(yīng)的算法[15-16].其中，基于聚合的方法由于實(shí)現(xiàn)簡(jiǎn)單、具有良好的可擴(kuò)展性等優(yōu)點(diǎn)，得到了廣泛關(guān)注.第1 類基于聚合的方法為網(wǎng)絡(luò)聚合，直接將多層網(wǎng)絡(luò)合并為單層網(wǎng)絡(luò)，然后利用傳統(tǒng)社區(qū)發(fā)現(xiàn)算法實(shí)現(xiàn)社區(qū)劃分.該類方法雖然降低了社區(qū)發(fā)現(xiàn)后續(xù)研究的難度，但是在聚合過程中丟失了不同層網(wǎng)絡(luò)結(jié)構(gòu)的獨(dú)特性，造成社區(qū)結(jié)果的不準(zhǔn)確.第2 類方法為基于集成學(xué)習(xí)的方法，首先在每層網(wǎng)絡(luò)上分別利用傳統(tǒng)社區(qū)發(fā)現(xiàn)算法進(jìn)行社區(qū)劃分，然后基于集成學(xué)習(xí)機(jī)制將每層的社區(qū)劃分融合得到最終的社區(qū)結(jié)構(gòu).這類方法在不同網(wǎng)絡(luò)層得到基社區(qū)劃分后，往往各層社區(qū)劃分分別進(jìn)行融合或者不同層的社區(qū)劃分進(jìn)行統(tǒng)一融合，忽視了不同層社區(qū)之間的異質(zhì)性；另一方面在融合過程中忽略了不同的基社區(qū)結(jié)構(gòu)和社區(qū)劃分之間的重要性，難以獲得準(zhǔn)確的社區(qū)結(jié)構(gòu)[17].

針對(duì)上述問題，本文提出了一種基于2 階段集成的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，旨在有效融合不同網(wǎng)絡(luò)層獲得的基社區(qū)劃分之間的信息，提高社區(qū)發(fā)現(xiàn)結(jié)果的準(zhǔn)確性和可解釋性.在第1 階段，分別以各層網(wǎng)絡(luò)生成的基社區(qū)劃分為主，并結(jié)合其他各層網(wǎng)絡(luò)得到的基社區(qū)劃分中最優(yōu)的社區(qū)劃分結(jié)構(gòu)信息進(jìn)行局部集成；在第2 階段，首先對(duì)得到的局部社區(qū)劃分及各個(gè)社區(qū)結(jié)構(gòu)的重要性度量，然后進(jìn)行全局加權(quán)集成得到最終的社區(qū)劃分結(jié)果.

1 相關(guān)工作

1.1 基于擴(kuò)展的方法

基于擴(kuò)展的方法主要指將單層網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法直接擴(kuò)展到多層網(wǎng)絡(luò)，通常通過優(yōu)化社區(qū)質(zhì)量評(píng)估函數(shù)來實(shí)現(xiàn).基于模塊度函數(shù)優(yōu)化是探測(cè)社區(qū)結(jié)構(gòu)的經(jīng)典方法，其核心思想是通過最大化模塊度來獲得社區(qū)劃分結(jié)果.例如，Mucha 等人[18]將模塊度擴(kuò)展到了多層網(wǎng)絡(luò)，開發(fā)了一種多層網(wǎng)絡(luò)社區(qū)質(zhì)量函數(shù)的廣義框架用于檢測(cè)多層網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu).該算法就是通過優(yōu)化多層模塊度擴(kuò)展了傳統(tǒng)的Louvain算法，從而得到一個(gè)多層模塊度高的社區(qū)劃分.Ma等人[19]提出了一種用于多層網(wǎng)絡(luò)社區(qū)檢測(cè)的定量函數(shù)——多層模塊化密度，解決了模塊度的分辨率限制問題，為社區(qū)發(fā)現(xiàn)算法的設(shè)計(jì)提供了理論基礎(chǔ)，并提出了一種半監(jiān)督聯(lián)合非負(fù)矩陣分解的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法S2-jNMF.該算法用貪婪搜索方法提取多層網(wǎng)絡(luò)所有層中連接良好的子圖作為先驗(yàn)信息，然后將與多層網(wǎng)絡(luò)相關(guān)的矩陣和先驗(yàn)信息聯(lián)合分解為一個(gè)基矩陣和一個(gè)多系數(shù)矩陣用于社區(qū)發(fā)現(xiàn).LART[20]是一種基于局部自適應(yīng)隨機(jī)游走的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，它首先對(duì)每一層網(wǎng)絡(luò)運(yùn)行不同的隨機(jī)游走；然后利用每層轉(zhuǎn)移概率獲得節(jié)點(diǎn)之間的不同度量；最后，采用層次聚類方法生成社區(qū)劃分，最終在多層模塊度的最優(yōu)值對(duì)應(yīng)的水平上得到社區(qū)劃分結(jié)果.Laishram 等人[21]提出了一種新穎的基于采樣的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，使用來自探索成本低的層的信息來幫助探索成本高的層的信息.盡管該類方法通過對(duì)單層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法進(jìn)行直接擴(kuò)展可以對(duì)多層網(wǎng)絡(luò)進(jìn)行有效社區(qū)發(fā)現(xiàn)，但是存在著需要設(shè)置的參數(shù)較多、時(shí)間復(fù)雜度較高、易受噪聲影響等缺點(diǎn).

1.2 基于聚合的方法

為了降低社區(qū)檢測(cè)的難度，基于多層網(wǎng)絡(luò)的聚合結(jié)構(gòu)進(jìn)行社區(qū)發(fā)現(xiàn)的相關(guān)研究具有實(shí)現(xiàn)簡(jiǎn)單、可擴(kuò)展性強(qiáng)的特點(diǎn).這些研究主要包括基于網(wǎng)絡(luò)聚合和基于集成學(xué)習(xí)2 類思路.

基于網(wǎng)絡(luò)聚合的方法是將一個(gè)多層網(wǎng)絡(luò)壓縮成單個(gè)網(wǎng)絡(luò)，然后采用單層網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法對(duì)其進(jìn)行社區(qū)檢測(cè).最簡(jiǎn)單的策略就是對(duì)鄰接矩陣進(jìn)行加權(quán)，其中2 個(gè)節(jié)點(diǎn)之間的權(quán)值為它們?cè)诙鄬泳W(wǎng)絡(luò)中相連的層數(shù).Berlingerio 等人[22]對(duì)簡(jiǎn)單的加權(quán)策略進(jìn)行了修改并提出了基于共同鄰居數(shù)的鄰接矩陣的加權(quán)策略，這種策略不再考慮2 個(gè)節(jié)點(diǎn)之間的直接聯(lián)系，而是關(guān)注它們的鄰居，共同鄰居數(shù)越多則越可能在同一個(gè)社區(qū).Zhu 等人[23]進(jìn)一步考慮了每層網(wǎng)絡(luò)的重要性，將單層網(wǎng)絡(luò)之間的相關(guān)性與單層網(wǎng)絡(luò)的重要性密切聯(lián)系起來，若某一單層網(wǎng)絡(luò)與其他的單層網(wǎng)絡(luò)之間的相關(guān)性更大，則表明其重要性更強(qiáng).同時(shí)判斷2 個(gè)節(jié)點(diǎn)之間是否存在路徑來衡量節(jié)點(diǎn)相似度，然后利用單層網(wǎng)絡(luò)重要性和節(jié)點(diǎn)相似度構(gòu)造統(tǒng)一矩陣，最后再用單層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法得到最終的社區(qū)劃分結(jié)果.基于網(wǎng)絡(luò)聚合方法在聚合過程中丟失了不同層網(wǎng)絡(luò)結(jié)構(gòu)的獨(dú)特性，造成社區(qū)結(jié)果的不準(zhǔn)確.

基于集成學(xué)習(xí)的方法首先利用傳統(tǒng)算法對(duì)多層網(wǎng)絡(luò)的各個(gè)層進(jìn)行社區(qū)發(fā)現(xiàn)，然后基于集成學(xué)習(xí)機(jī)制將各層得到的社區(qū)劃分結(jié)果進(jìn)行融合得到最終的社區(qū)劃分[17].Tang 等人[24]提出了主模塊化最大化方法，首先通過模塊化最大化從多層網(wǎng)絡(luò)的每個(gè)層中提取結(jié)構(gòu)特征，然后對(duì)這些特征進(jìn)行跨層次分析，采用PCA 技術(shù)找到低維嵌入，使從所有層中提取的特征彼此高度相關(guān)，最后通過k-means 聚類算法找到社區(qū)劃分.Berlingerio 等人[25]提出了一種基于頻繁模式挖掘的多層網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法，能夠從單層社區(qū)成員中提取頻繁的封閉項(xiàng)集來提取多層社區(qū).首先用單層社區(qū)發(fā)現(xiàn)算法獲得每層網(wǎng)絡(luò)上的社區(qū)，然后用頻繁封閉項(xiàng)集算法將至少在最少數(shù)量的層上屬于同一社區(qū)的節(jié)點(diǎn)分配到同一社區(qū).Tagarelli 等人[17]提出了一種新的基于模塊化優(yōu)化的集成的多層社區(qū)發(fā)現(xiàn)算法，此方法在尋找共識(shí)社區(qū)結(jié)構(gòu)時(shí)，不僅捕獲了節(jié)點(diǎn)的原型社區(qū)成員，而且能夠保存多層網(wǎng)絡(luò)的拓?fù)湫畔?，在獲得共識(shí)解的過程中將多層網(wǎng)絡(luò)的拓?fù)渖辖绾屯負(fù)湎陆缱鳛樗阉骺臻g，共識(shí)函數(shù)也是通過基于模塊化優(yōu)化的方法，同時(shí)考慮了社區(qū)內(nèi)和社區(qū)間的連通性.這類方法在得到不同層的社區(qū)劃分后，往往各層社區(qū)劃分分別進(jìn)行融合或者不同層的社區(qū)劃分進(jìn)行統(tǒng)一融合.由于每一層網(wǎng)絡(luò)中節(jié)點(diǎn)之間的交互方式以及社區(qū)結(jié)構(gòu)的不同，進(jìn)行簡(jiǎn)單集成容易忽視不同層社區(qū)之間的異質(zhì)性；而且在融合過程中忽略了不同的基社區(qū)結(jié)構(gòu)和社區(qū)劃分之間的重要性，難以獲得準(zhǔn)確的社區(qū)結(jié)果.

2 基于集成的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

本節(jié)首先對(duì)基于集成學(xué)習(xí)的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題進(jìn)行了描述，接著對(duì)本文提出的基于2 階段集成的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法進(jìn)行了介紹.

2.1 問題描述

一個(gè)多層網(wǎng)絡(luò)可以定義為

其 中G={Gα|α ∈{1,2,…,L}}表 示L層 網(wǎng) 絡(luò) 構(gòu) 成 的 集合，Gα=(Vα,Eα) 為 多層網(wǎng)絡(luò)中的第 α 層，Vα?V={v1,v2,…,vN}，Vα表示第 α層的節(jié)點(diǎn)集，V為多層網(wǎng)絡(luò)的所有節(jié)點(diǎn)的集合，Eα?Vα×Vα表 示第 α層內(nèi)節(jié)點(diǎn)之間連接的邊集； A表示任意2 個(gè)不同層的節(jié)點(diǎn)之間的連接，可以表示為

即Eα中 的元素表示層內(nèi)頂點(diǎn)間連接，Eαβ表示層間頂點(diǎn)間的連接.本文主要討論的對(duì)象為所有層共享相同節(jié)點(diǎn)集的多層網(wǎng)絡(luò)，即在給定的多層網(wǎng)絡(luò)GL=(G,A) 中，對(duì)于每一層Gα=(Vα,Eα)∈G都 有Vα=V(V={v1,v2,…,vN}), 但是每一層內(nèi)的邊集不同，即Gα=(V,Eα).另外，對(duì)于層間連接

即所有層的節(jié)點(diǎn)是對(duì)齊的.如圖1 為一個(gè)多層網(wǎng)絡(luò)示意圖，由3 層網(wǎng)絡(luò)組成，每層均包括6 個(gè)節(jié)點(diǎn)，每層內(nèi)的連邊表示節(jié)點(diǎn)間的一種關(guān)系，層間的虛線表示不同層的節(jié)點(diǎn)是對(duì)齊的.

Fig.1 An example of multi-layer network圖1 多層網(wǎng)絡(luò)示例

給定一個(gè)L層的多層網(wǎng)絡(luò) GL=(G,A)，針對(duì)每層網(wǎng)絡(luò)Gα=(V,Eα)分別多次利用傳統(tǒng)單層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法得到該層的社區(qū)結(jié)構(gòu)為其中表示第 α 層 網(wǎng)絡(luò)共生成Mα個(gè)基社區(qū)劃分，則多層網(wǎng)絡(luò) GL的基社區(qū)結(jié)構(gòu)表示為B={B1,…,Bα,…,BL}，基于集成的社區(qū)發(fā)現(xiàn)算法的目的是基于各層網(wǎng)絡(luò)產(chǎn)生的基社區(qū)結(jié)構(gòu)B={B1,…,Bα,…,BL}，通過集成函數(shù)獲得給定多層網(wǎng)絡(luò) GL=(G,A)的最終社區(qū)劃分結(jié)果C*={C1,C2,…,Ck} ，且 ∪ki=1Ci=V,Ci∩Cj=?， 其 中k表示最終社區(qū)個(gè)數(shù).多層網(wǎng)絡(luò)總的社區(qū)結(jié)構(gòu)劃分方案?jìng)€(gè)數(shù)為

2.2 基于2 階段集成的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

本文算法的主要步驟如圖2 所示，主要包括基社區(qū)劃分生成、局部集成、全局加權(quán)集成3 個(gè)步驟.具體地：1）基社區(qū)劃分生成是指在多層網(wǎng)絡(luò)的每一層分別多次利用相同的傳統(tǒng)單層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法產(chǎn)生一組基社區(qū)劃分；2）分別基于單層網(wǎng)絡(luò)生成的基社區(qū)劃分和其他各層網(wǎng)絡(luò)得到的基社區(qū)劃分中最優(yōu)的社區(qū)劃分信息對(duì)各層進(jìn)行局部集成得到局部社區(qū)劃分結(jié)果；3）分別對(duì)局部集成得到的社區(qū)劃分及各個(gè)社區(qū)的重要性進(jìn)行度量并進(jìn)行全局加權(quán)集成得到最終社區(qū)結(jié)果.

Fig.2 Illustration of our proposed algorithm process圖2 本文算法流程示意圖

2.2.1 基社區(qū)劃分生成

該步驟的目的是為不同層的網(wǎng)絡(luò)分別生成多組準(zhǔn)確性高、差異性強(qiáng)的基社區(qū)劃分.給定一個(gè)L層的多層網(wǎng)絡(luò) GL=(G,A) ，在每層網(wǎng)絡(luò)Gα=(V,Eα)分別多次利用傳統(tǒng)單層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法獲得該層的社區(qū)劃分表示第 α層網(wǎng)絡(luò)共生成Mα個(gè)基社區(qū)劃分.為了生成準(zhǔn)確性高、多樣性強(qiáng)的基社區(qū)劃分，本文采用經(jīng)典的LM 算法[10]對(duì)每層網(wǎng)絡(luò)分別進(jìn)行社區(qū)發(fā)現(xiàn).

2.2.2 局部集成

由于不同層產(chǎn)生的基社區(qū)劃分之間既存在異質(zhì)性，又存在一定的相關(guān)性.因此，在局部社區(qū)劃分集成階段各層結(jié)合其他各層的最優(yōu)社區(qū)結(jié)構(gòu)信息進(jìn)行集成.本文中將各個(gè)層中最優(yōu)的社區(qū)劃分結(jié)果加入其他層，以此達(dá)到提升局部模型性能的目的.模塊度是社區(qū)劃分質(zhì)量?jī)?yōu)劣的評(píng)價(jià)指標(biāo)[26].模塊度反映了網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)內(nèi)部連接的強(qiáng)弱，指的是社區(qū)內(nèi)的邊占所有邊的比例減去在同樣的社區(qū)結(jié)構(gòu)下隨機(jī)放置社區(qū)內(nèi)部的邊占所有邊的比例的期望值，定義為

其中m表示網(wǎng)絡(luò)的總邊數(shù)，A表 示網(wǎng)絡(luò)的鄰接矩陣，ki和kj分 別代表節(jié)點(diǎn)vi和vj的 度，當(dāng)節(jié)點(diǎn)vi和vj屬于同一個(gè)社區(qū)時(shí)， δ (i,j)=1， 否則， δ(i,j)=0.模塊度越高，則社區(qū)劃分質(zhì)量越高.針對(duì)第 α層網(wǎng)絡(luò)獲得的基社區(qū)劃分Bα={B1α,B2α,…,BαMα}，可以通過計(jì)算各個(gè)劃分下的模塊度指標(biāo)來選出第 α層中最優(yōu)的基社區(qū)劃分.因此，在進(jìn)行局部集成時(shí)，每一層的基社區(qū)劃分由該層產(chǎn)生的Mα個(gè) 基社區(qū)和其他L-1層分別選出的最優(yōu)社區(qū)劃分組成.基于基社區(qū)劃分信息，從局部角度每層分別構(gòu)造節(jié)點(diǎn)之間的共協(xié)矩陣Aα（1 ≤α ≤L），記為

其中nij表示在第 α層中節(jié)點(diǎn)vi和vj在參與集成的基社區(qū)劃分中被分配到同一個(gè)社區(qū)的數(shù)量，Mα+L-1是參與集成的社區(qū)劃分的數(shù)量.基于共協(xié)矩陣，利用層次聚類即可得到每層的局部社區(qū)劃分結(jié)果Pα（1 ≤α ≤L）， 則多層網(wǎng)絡(luò) GL的局部社區(qū)劃分結(jié)果記為E={P1,P2,…,PL}.

2.2.3 全局加權(quán)集成

在集成過程中，不同社區(qū)劃分以及社區(qū)的優(yōu)劣均會(huì)對(duì)最終社區(qū)的檢測(cè)產(chǎn)生不同的影響.本節(jié)通過社區(qū)劃分和社區(qū)質(zhì)量進(jìn)行評(píng)價(jià)來對(duì)集成過程進(jìn)行加權(quán).局部社區(qū)劃分結(jié)果E中，每層網(wǎng)絡(luò)的Pα的優(yōu)劣通過該劃分方案運(yùn)用到其他層網(wǎng)絡(luò)上的模塊度來衡量，定義為

其中mβ表 示第 β 層 網(wǎng)絡(luò)的總邊數(shù)，Aβ表示第 β層網(wǎng)絡(luò)的鄰接矩陣，kβi和kβj分別代表節(jié)點(diǎn)vi和vj在 第 β層網(wǎng)絡(luò)中 的 度，當(dāng) 節(jié) 點(diǎn)vi和vj在Pα屬 于 同 一 個(gè) 社 區(qū) 時(shí)，δα(i,j)=1， 否則， δα(i,j)=0.如果Q(Pα,Gβ)越高，則表示相對(duì)于第 β層Pα的質(zhì)量越優(yōu).因此，在全局集成中第 α 層 獲得的Pα的權(quán)重定義為

然 后，對(duì) E={P1,P2,…,PL} 中 各 層Pα（1 ≤α ≤L）的 權(quán)重進(jìn)行歸一化，則有

信息熵是信息論中用于度量系統(tǒng)不確定性的一種重要度量方法.如果一個(gè)社區(qū)結(jié)構(gòu)相對(duì)其他劃分越穩(wěn)定，則表明該社區(qū)的不確定性越小、可靠性越強(qiáng)，該社區(qū)在集成過程中的權(quán)重越大.

局部社區(qū)劃分結(jié)果 E={P1,P2,…,PL} 中第 α層的社 區(qū) 劃 分 記 為Pα={C1α,C2α,…,Cnαα}， 其 中Ciα表 示Pα中的第i個(gè)社區(qū)，nα表示Pα中 社區(qū)的數(shù)量.因此， E中所有社區(qū)可以表示為

其中Ci表 示第i個(gè)社區(qū)，nC表 示 E中所有社區(qū)的總個(gè)數(shù).

給定一個(gè)社區(qū)Ci∈C 和網(wǎng)絡(luò)層Gα的Pα∈E，如果社區(qū)Ci不 屬于Pα， 那么Ci中 的節(jié)點(diǎn)可能屬于Pα中的多個(gè)社區(qū)，Ci相 對(duì)于Pα的 不確定性可以通過考慮Ci中的對(duì)象在Pα中各個(gè)社區(qū)中的分布來進(jìn)行計(jì)算.那么，社區(qū)Ci關(guān) 于第 α 層網(wǎng)絡(luò)Gα的Pα的不確定性可表示為

其中

其中nα表示社區(qū)劃分Pα中的社區(qū)數(shù)量，Cαj表示Pα中的第j個(gè)社區(qū)，表示2 個(gè)社區(qū)中共有節(jié)點(diǎn)的個(gè)數(shù)， |Ci|表 示Ci中 節(jié) 點(diǎn)的 個(gè) 數(shù).p(Ci,Cαj)∈[0,1]，所以Hα(Ci)∈[0,+∞).

因此，Ci關(guān) 于多層網(wǎng)絡(luò) GL的局部社區(qū)劃分 E的不確定性可以通過Ci關(guān) 于 E中每層網(wǎng)絡(luò)的社區(qū)劃分結(jié)構(gòu)的不確定性的和來表示，即

基于信息熵來衡量每個(gè)社區(qū)關(guān)于局部社區(qū)劃分E的不確定性，那么進(jìn)一步可通過歸一化來衡量E中每個(gè)社區(qū)的權(quán)重，即

由于HE(Ci)∈[0,+∞) ， 所以W(Ci)∈[0,1]，即一個(gè)社區(qū)的不確定越小，則該社區(qū)的可靠性就越高，在集成過程中的權(quán)重越大.

基于式（8）（13）給出的社區(qū)劃分以及社區(qū)的權(quán)重，從全局角度構(gòu)造節(jié)點(diǎn)之間的加權(quán)共協(xié)矩陣，表示為

其中

其中Clsα(vi)表 示節(jié)點(diǎn)vi在Pα中所屬社區(qū)的標(biāo)簽.

基于加權(quán)共協(xié)矩陣，通過層次聚類獲得多層網(wǎng)絡(luò) GL的最終社區(qū)劃分結(jié)果C*={C1,C2,…,Ck}.

基于以上對(duì)各階段集成過程的描述，本文提出的基于2 階段集成的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法描述如算法1.

算法1.基于2 階段集成的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法.

輸入：多層網(wǎng)絡(luò) GL=(G,A) ，社區(qū)劃分個(gè)數(shù)k，各層網(wǎng)絡(luò)社區(qū)基劃分次數(shù)M；

輸出：多層網(wǎng)絡(luò) GL的最終社區(qū)劃分結(jié)果C*={C1,C2,…,Ck}.

① 在每層網(wǎng)絡(luò)上利用傳統(tǒng)的LM 社區(qū)發(fā)現(xiàn)算法獲得基社區(qū)劃分結(jié)果，記為B={B1,B2,…,BL}；

② forBα∈B

④ {B1,…,Bα-1,Bα+1,…,BL}←； /*將添加到B中除Bα外的其他集合中*/

⑤ end for

⑥ forGα∈G

⑦Aα←Bα； /*根據(jù)式（5）計(jì)算共協(xié)矩陣*/

⑧Pα←Aα；/*利用層次聚類獲得局部社區(qū)劃分*/

⑨ end for

⑩ forPα∈E

?W(Pα)←Pα；/*根據(jù)式（7）計(jì)算局部社區(qū)劃分的權(quán)重*/

? end for

?(Pα)←W(Pα)；/*根據(jù)式（8）對(duì)權(quán)重進(jìn)行歸一化 */

? forCi∈E

?HE(Ci) ←Ci；/*根據(jù)式（12）計(jì)算社區(qū)不確定性*/

? end for

?W(Ci)←HE(Ci)；/*根據(jù)式（13）計(jì)算各個(gè)社區(qū)權(quán)重*/

? 根據(jù)式（14）構(gòu)造加權(quán)共協(xié)矩陣，并利用層次聚類得到最終社區(qū)結(jié)構(gòu)C*={C1,C2,…,Ck}.

2.3 時(shí)間復(fù)雜度分析

本文提出的基于2 階段集成的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法主要包括3 個(gè)步驟：1）基社區(qū)劃分生成；2）局部集成；3）全局加權(quán)集成.

在步驟1 中采用LM 算法[10]，假設(shè)一個(gè)單層網(wǎng)絡(luò)的邊的數(shù)量為e，則其時(shí)間復(fù)雜度為O(e)，所以步驟1的時(shí)間復(fù)雜度為O(LMe).步驟2 中主要包括構(gòu)造共協(xié)矩陣，因?yàn)锽α中 的社區(qū)劃分?jǐn)?shù)量為Mα+L-1，因此其時(shí)間復(fù)雜度為O((Mα+L-1)N2)；此外，利用層次聚類算法獲得局部社區(qū)劃分結(jié)果的時(shí)間復(fù)雜度為O(N2)，所以步驟2 的時(shí)間復(fù)雜度為O(L(Mα+L-1)N2+LN2).步驟3 通過信息熵來計(jì)算各個(gè)社區(qū)的穩(wěn)定性，假設(shè)步驟2 得到的總社區(qū)數(shù)量為nC，則計(jì)算社區(qū)不穩(wěn)定性的時(shí)間復(fù)雜度為O(nC)，基于共協(xié)矩陣?yán)脤哟尉垲愑?jì)算最終社區(qū)劃分結(jié)果的時(shí)間復(fù)雜度為O(N2)，所以步驟3 的時(shí)間復(fù)雜度為O(nC+N2).因此，算法的總時(shí)間復(fù)雜度為O(LMe+L(Mα+L-1)N2+LN2+nC+N2).由于L，M，nC均 小于節(jié)點(diǎn)個(gè)數(shù)N，所以算法的總時(shí)間復(fù)雜度為O(N2).

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文算法的有效性，與已有的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法在人工合成多層網(wǎng)絡(luò)和12 個(gè)真實(shí)多層網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)比較分析.

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

3.1.1 人工合成多層網(wǎng)絡(luò)

為了生成人工合成多層網(wǎng)絡(luò)數(shù)據(jù)，本文采用了Bazzi 等人[27]提出的算法.算法參數(shù)設(shè)置為：網(wǎng)絡(luò)的層數(shù)L= 3，5，7，每層網(wǎng)絡(luò)的規(guī)模N= 1 000 或N=5 000，社區(qū)個(gè)數(shù)分別為10 和50，其中每個(gè)節(jié)點(diǎn)都出現(xiàn)在每一層中，即在這些網(wǎng)絡(luò)中分別總共有3 000，5 000，7 000，15 000，25 000，35 000 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的度設(shè)置為其算法默認(rèn)值，即最小度為3，最大度為150.混合參數(shù) μ∈[0,1]， μ的值越接近1，生成網(wǎng)絡(luò)的隨機(jī)性越強(qiáng).參數(shù)∈[0,1]表 示層間相關(guān)系數(shù)，當(dāng)=0時(shí)，表示產(chǎn)生的多層網(wǎng)絡(luò)各層之間社區(qū)劃分是相互獨(dú)立；當(dāng)=1時(shí)，所產(chǎn)生的多層網(wǎng)絡(luò)各層之間的社區(qū)劃分是相同的.由于本文算法為通過集成策略產(chǎn)生統(tǒng)一的社區(qū)劃分，因此選擇參數(shù)=1.

3.1.2 真實(shí)多層網(wǎng)絡(luò)

實(shí)驗(yàn)中采用的真實(shí)多層網(wǎng)絡(luò)數(shù)據(jù)集的基本情況如表1 所示.所有真實(shí)網(wǎng)絡(luò)數(shù)據(jù)的社區(qū)劃分未知.

Table 1 Real Multilayer Networks表1 真實(shí)多層網(wǎng)絡(luò)

AUCS 數(shù)據(jù)集描述某大學(xué)研究部門的61 名員工節(jié)點(diǎn)（包括教授、博士后、博士生和行政人員）之間的Facebook 關(guān)系、午餐關(guān)系、合作關(guān)系、休閑關(guān)系和工作關(guān)系[28].EUAir 數(shù)據(jù)集是歐洲航空交通網(wǎng)絡(luò)，每層網(wǎng)絡(luò)對(duì)應(yīng)在歐洲運(yùn)營(yíng)的不同航空公司[29].Pierreauger數(shù)據(jù)集表示天文臺(tái)科學(xué)家之間的協(xié)作關(guān)系，每一層代表一種協(xié)作任務(wù)[30].CKM 數(shù)據(jù)集由美國(guó)4 個(gè)城鎮(zhèn)的246 名醫(yī)生組成，主要討論網(wǎng)絡(luò)關(guān)系對(duì)醫(yī)生用藥決策的影響，包括通常找誰獲取用藥建議、經(jīng)常與誰討論和與誰關(guān)系最好3 層網(wǎng)絡(luò)[30].Kapferer 網(wǎng)絡(luò)中節(jié)點(diǎn)為裁縫店的工人，關(guān)系為他們之間的工作和友誼互動(dòng)[31].

另外，在包含相互作用數(shù)據(jù)集的生物通用存儲(chǔ)庫中選取了Gallus[32]，Herpes4[33]， Hiv1[33]， Plasmodium[32]，Xenopus[33]， Bos[32]，Candida[32]共7 個(gè)多層網(wǎng)絡(luò)數(shù)據(jù)集.這些網(wǎng)絡(luò)代表蛋白質(zhì)之間的相互作用，不同的層對(duì)應(yīng)于不同性質(zhì)的相互作用，即直接作用、物理關(guān)聯(lián)、共定位、關(guān)聯(lián)、抑制、增強(qiáng)和合成遺傳相互作用.每種生物體所對(duì)應(yīng)的層數(shù)為3～7 不等.

3.2 評(píng)價(jià)指標(biāo)

當(dāng)數(shù)據(jù)集的真實(shí)社區(qū)結(jié)果未知時(shí)，采用Mucha等人[18]提出的多層網(wǎng)絡(luò)模塊度QM來評(píng)價(jià)多層網(wǎng)絡(luò)的社區(qū)質(zhì)量，定義為

其中 μ表示多層網(wǎng)絡(luò)中的連接的數(shù)量，分辨率 γ以控制每層網(wǎng)絡(luò)的社區(qū)規(guī)模和數(shù)量.Ai jα表 示網(wǎng)絡(luò)第 α層的鄰接矩陣節(jié)點(diǎn)vi和 節(jié)點(diǎn)vj之 間的連接關(guān)系， δαβ在第α 層和第 β 層 為同一層時(shí)為1，否則為0； δij在 節(jié)點(diǎn)vi和節(jié)點(diǎn)vj為 同層節(jié) 點(diǎn)時(shí)為1，否則為0.Cjαβ表 示 α 層 和β層之間與節(jié)點(diǎn)vj的 層間連邊數(shù)，表示節(jié)點(diǎn)vi在 α 層上的度，表示 α層的總邊數(shù).如果節(jié)點(diǎn)vi和 節(jié) 點(diǎn)vj的 社 區(qū) 分 布 相 同，則 δ(giα,gjβ)=1，否 則為0.

對(duì)于有真實(shí)社區(qū)劃分的數(shù)據(jù)集，利用標(biāo)準(zhǔn)化互信息（NMI）[34]來評(píng)價(jià)社區(qū)劃分結(jié)果的質(zhì)量，NMI定義為

其中X和Y分別表示數(shù)據(jù)集的真實(shí)社區(qū)劃分結(jié)果和算法得到的社區(qū)劃分結(jié)果，cX和cY分別表示X和Y中的社區(qū)數(shù)量，是一個(gè)混淆矩陣，其元素Nij表示在X的社區(qū)i與Y的社區(qū)j中共同出現(xiàn)的節(jié)點(diǎn)數(shù)量，Ni表示的第i行的元素的和，Nj表示的第j列的元素的和，N表示節(jié)點(diǎn)數(shù)量.NMI(X,Y)的范圍為[0,1]，如果X和Y完全相同，則NMI(X,Y) =1；如果X和Y完全不同，則NMI(X,Y)=0.

3.3 對(duì)比方法及參數(shù)設(shè)置

本文算法與已有多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)基線方法進(jìn)行了比較，代表性方法包括PMM[24]，SCML[35]，PM[36]，CoReg[37]，AWP[38]，EVM[39].

根據(jù)已有文獻(xiàn)實(shí)驗(yàn)分析中的建議，對(duì)基線方法的參數(shù)進(jìn)行了設(shè)置.其中，本文方法與基線方法PMM，SCML，PM，CoReg，AWP 共同的參數(shù)為社區(qū)個(gè)數(shù)k，為了比較的公平性，對(duì)于社區(qū)已知的人造網(wǎng)絡(luò)個(gè)數(shù)k均設(shè)置為真實(shí)的社區(qū)個(gè)數(shù)，對(duì)于社區(qū)未知的真實(shí)網(wǎng)絡(luò)將社區(qū)個(gè)數(shù)k設(shè)置為其中N表示節(jié)點(diǎn)個(gè)數(shù)，各個(gè)算法分別在不同的k值下運(yùn)行，并從結(jié)果中選取最優(yōu)值進(jìn)行比較.PMM 算法中結(jié)構(gòu)特征的數(shù)量可以是1～(N-2)（N為節(jié)點(diǎn)總數(shù)）之間的任意數(shù)字，根據(jù)建議，對(duì)于人工多層網(wǎng)絡(luò)和真實(shí)多層網(wǎng)絡(luò)均設(shè)置了2 個(gè)值，人工多層網(wǎng)絡(luò)比較低的常數(shù)為50，真實(shí)多層網(wǎng)絡(luò)比較低的常數(shù)為10，用PMMl來表示；另一個(gè)是根據(jù)節(jié)點(diǎn)總數(shù)來設(shè)定的值，2 類數(shù)據(jù)集上都設(shè)置為N/2，用PMMh來表示，k-means 算法執(zhí)行的次數(shù)設(shè)置為10.SCML 算法中正則化參數(shù) λ= 0.5；PM 算法中參 數(shù)p=-10 ； CoReg 算 法 正 則 化 參 數(shù) λ=0.01；EVM算法正則化參數(shù) γ=0.5.本文算法中各層網(wǎng)絡(luò)生成的基社區(qū)劃分個(gè)數(shù)M= 10.

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

3.4.1 人工網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果分析

在不同的參數(shù)下生成了60 個(gè)不同的人工合成網(wǎng)絡(luò)，針對(duì)各個(gè)網(wǎng)絡(luò)，對(duì)比算法均在不同參數(shù)設(shè)置下運(yùn)行10 次，然后取結(jié)果的平均值進(jìn)行比較.各個(gè)算法在不同人工網(wǎng)絡(luò)的NMI值隨網(wǎng)絡(luò)參數(shù) μ的變化如圖3所示.隨著 μ的逐漸增大，不同算法的性能均出現(xiàn)了下降趨勢(shì).這是因?yàn)殡S著 μ的增大網(wǎng)絡(luò)的隨機(jī)性變強(qiáng)，網(wǎng)絡(luò)蘊(yùn)含的社區(qū)結(jié)構(gòu)復(fù)雜導(dǎo)致社區(qū)發(fā)現(xiàn)算法識(shí)別正確社區(qū)的難度加大.當(dāng)多層網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量N= 1 000時(shí)，PMMh產(chǎn)生了較差的結(jié)果，且在所有網(wǎng)絡(luò)中，PMMl和PMMh產(chǎn)生的結(jié)果有著較大的差異，說明不同的結(jié)構(gòu)特征數(shù)量對(duì)PMM 產(chǎn)生了較大的影響，而其取值為1～(N-2)，特別對(duì)于規(guī)模較大的網(wǎng)絡(luò)，選取合適的結(jié)構(gòu)特征數(shù)量并不容易.其他算法的結(jié)果都隨著 μ的變化出現(xiàn)了較大的波動(dòng)，從圖3 可以看出本文算法在大部分情況下優(yōu)于其他算法.當(dāng)多層網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量N= 5 000 時(shí)，基本上所有算法的結(jié)果隨著μ的增大而減小.例如，PM 算法的結(jié)果在L= 3，5，7 的情況下分別在 μ= 0.4，0.5，0.6 的時(shí)候明顯下降，PMM算法對(duì)于不同的提取的結(jié)構(gòu)特征數(shù)量值，結(jié)果產(chǎn)生了較大的差異；AWP 算法的結(jié)果在3 種不同層數(shù)的網(wǎng)絡(luò)中 μ＜0.7 時(shí)均表現(xiàn)較好，但在 μ = 0.7 出現(xiàn)了明顯下降； SCML 算法表現(xiàn)較好，這是因?yàn)镾CML 算法通過將包含在單個(gè)圖層中的信息轉(zhuǎn)換為Grassmann 流形上的子空間并利用Grassmann 流形上的距離分析找到一個(gè)具有代表性的子空間，最后在這個(gè)代表子空間上進(jìn)行聚類.但是，SCML 的聚類結(jié)果容易受到與代表性子空間距離更近的單個(gè)圖層子空間上聚類結(jié)果的影響，當(dāng)所有單個(gè)圖層都包含豐富的信息時(shí)，SCML 將產(chǎn)生更好的結(jié)果，若與代表性子空間距離更近的單個(gè)圖層上的聚類質(zhì)量較差時(shí)也會(huì)導(dǎo)致SCML產(chǎn)生較差的結(jié)果.下面我們選取L= 3,N= 5 000, μ=0.5 和L= 3,N= 1 000, μ= 0.6 這2 種不同情況的人工網(wǎng)絡(luò)來說明SCML 算法為何在N= 5 000 時(shí)取得較好的結(jié)果.如表2 所示，在L= 3,N= 5 000， μ= 0.5 上代表性子空間與第2 層的子空間距離最近，且從表2 中SCML 算法在單層網(wǎng)絡(luò)上得到的結(jié)果和NMI值，可以看出各層網(wǎng)絡(luò)均包含較為豐富的信息，所以SCML得到了更好的結(jié)果.如表3 所示，在L= 3,N= 1 000,μ= 0.6 上代表性子空間與第2 層的子空間距離最近，與表2 不同的是該網(wǎng)絡(luò)的第2 層得到了低質(zhì)量的聚類結(jié)果，SCML 產(chǎn)生了較差的結(jié)果.說明當(dāng)多層網(wǎng)絡(luò)的各層網(wǎng)絡(luò)中都包含較為豐富的信息時(shí)，SCML 產(chǎn)生更好的結(jié)果，而當(dāng)各層網(wǎng)絡(luò)中存在信息較少且該層網(wǎng)絡(luò)的子空間與SCML 計(jì)算所得的代表性子空間距離即使較近時(shí)，SCML 也會(huì)忽略信息較多的層，從而導(dǎo)致最終產(chǎn)生較差的結(jié)果.基于以上2 個(gè)人工網(wǎng)絡(luò)對(duì)本文提出的方法進(jìn)行分析，在L= 3,N= 5 000, μ= 0.5上，本文算法的NMI分別為0.802 1，0.813 1，0.802 3.可以看出，該網(wǎng)絡(luò)中各層都包含了較為豐富的信息，通過式（14）進(jìn)行全局加權(quán)集成后，得到的NMI= 0.850 1；在L= 3,N= 1 000, μ = 0.6 上，本文算法的NMI分別為0.544 0，0.224 7，0.024 7.可以看出該網(wǎng)絡(luò)中各層之間的差異性較大.

Table 2 Result Analysis of SCML on Network with L=3, N=5 000, μ=0.5表2 SCML 在L=3, N =5 000, μ=0.5 網(wǎng)絡(luò)上的結(jié)果分析

Table 3 Result Analysis of SCML on Network with L=3, N=1 000, μ=0.6表3 SCML 在L=3, N=1 000, μ=0.6 網(wǎng)絡(luò)上的結(jié)果分析

Fig.3 Comparison results of NMI on synthetic networks圖3 不同算法在合成網(wǎng)絡(luò)上的NMI 比較結(jié)果

通過式（14）進(jìn)行全局加權(quán)集成后，得到的最終結(jié)果的NMI=0.548 9.通過對(duì)比表2、表3 與本文算法得到的NMI值可以看出L= 3，N=5 000， μ=0.5 中各層網(wǎng)絡(luò)包含信息較為平均，而L= 3，N=1 000， μ=0.6 中各層網(wǎng)絡(luò)包含信息的差異較大，所以當(dāng)N=5 000 時(shí)，由于單層網(wǎng)絡(luò)之間差異較小，且隨著 μ的增大，各層網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)難以識(shí)別，導(dǎo)致各層網(wǎng)絡(luò)上得到的基社區(qū)劃分較差，從而導(dǎo)致經(jīng)過集成產(chǎn)生的社區(qū)質(zhì)量也較低；當(dāng) μ＜0.7時(shí)，本文算法在3 種不同層數(shù)的網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果變化較小，說明本文算法的魯棒性較強(qiáng).CoReg 和EVM 同樣在N=5 000，即單層網(wǎng)絡(luò)差異較小的人工網(wǎng)絡(luò)上表現(xiàn)出了良好的性能，而在單層網(wǎng)絡(luò)差異較大的人工網(wǎng)絡(luò)上表現(xiàn)較差.

3.4.2 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果分析

不同算法在真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如表4 所示，其中每個(gè)算法在不同參數(shù)設(shè)置下均運(yùn)行10 次，從不同社區(qū)個(gè)數(shù)得到的結(jié)果中選取最優(yōu)模塊度值進(jìn)行比較.對(duì)不同算法在每個(gè)數(shù)據(jù)集上社區(qū)發(fā)現(xiàn)結(jié)果的最優(yōu)結(jié)果和次優(yōu)結(jié)果進(jìn)行加粗標(biāo)注.從表4 可以看出，本文算法在除AUCS 之外的11 個(gè)數(shù)據(jù)集上都取得了最優(yōu)結(jié)果或次優(yōu)的結(jié)果，其中在EUAir ，Gallus，Herpes4，Hiv1，Plasmodium，Xenopus，Bos 共7 個(gè)數(shù)據(jù)集上本文算法的結(jié)果明顯優(yōu)于次優(yōu)的結(jié)果.總之，本文算法在真實(shí)數(shù)據(jù)集上表現(xiàn)出了較為良好的性能.

Table 4 Comparison of Experimental Results on Real Networks in Terms of QM表4 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果的QM 比較

3.4.3 魯棒性分析

為了驗(yàn)證本文算法的有效性受基社區(qū)劃分?jǐn)?shù)M變化的影響，對(duì)采用 μ=0.3 時(shí)不同規(guī)模的6 個(gè)人工多層網(wǎng)絡(luò)和部分層數(shù)較少的真實(shí)多層網(wǎng)絡(luò)進(jìn)行了魯棒性 測(cè) 試.其 中，M∈{10,20,30,40,50}，對(duì) 于 不 同 的M值，取本文算法在每個(gè)網(wǎng)絡(luò)上執(zhí)行10 次的結(jié)果的平均值進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖4 和圖5 所示.

Fig.4 NMI of the proposed algorithm changes with varying ensemble number M圖4 本文算法的NMI 隨基社區(qū)劃分?jǐn)?shù)M 的變化

Fig.5 Q M of the proposed algorithm changes with varying ensemble number M圖5 本文算法的QM 隨基社區(qū)劃分?jǐn)?shù)M 的變化

在人工多層網(wǎng)絡(luò)數(shù)據(jù)集中，采用NMI指標(biāo)對(duì)社區(qū)劃分結(jié)果進(jìn)行評(píng)價(jià)，統(tǒng)計(jì)在不同M下NMI的變化情況.由圖4 可知，當(dāng)L= 7，N=1 000， μ=0.3 時(shí)本文算法的NMI值出現(xiàn)了最大的波動(dòng)（0.013），其次當(dāng)L=7，N=5 000， μ=0.3 時(shí)NMI值為0.01，在其他人工網(wǎng)絡(luò)數(shù)據(jù)集上NMI值的波動(dòng)范圍均在0.01 以內(nèi).在真實(shí)多層網(wǎng)絡(luò)數(shù)據(jù)集中，通過多層模塊度指標(biāo)QM對(duì)各個(gè)結(jié)果的變化范圍進(jìn)行分析.在Plas 數(shù)據(jù)集上，本文算法的結(jié)果在不同的M值下QM值的波動(dòng)為0.015，在CKM 和Candida 數(shù)據(jù)上的QM值的波動(dòng)范圍均為0.011，而在其他數(shù)據(jù)集上不同的M值下QM值變化范圍均小于0.01.結(jié)果表明，本文算法的性能受基各層社區(qū)劃分個(gè)數(shù)M的影響較小，具有良好的魯棒性.

4 總 結(jié)

近年來，有效融合多層網(wǎng)絡(luò)信息并對(duì)其進(jìn)行社區(qū)發(fā)現(xiàn)成為了一個(gè)重要的研究?jī)?nèi)容.為此，本文提出了一種基于2 階段集成的多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法.首先，第1 階段在各層進(jìn)行局部集成時(shí)結(jié)合了其他層的最優(yōu)社區(qū)劃分信息，有效利用了不同網(wǎng)絡(luò)層社區(qū)結(jié)構(gòu)的相關(guān)性；其次，第2 階段中基于其他網(wǎng)絡(luò)層的社區(qū)結(jié)構(gòu)信息對(duì)各層融合得到的社區(qū)劃分及社區(qū)結(jié)構(gòu)的重要性進(jìn)行評(píng)價(jià)加權(quán)，再進(jìn)行全局加權(quán)集成，綜合考慮了各層局部社區(qū)劃分結(jié)果對(duì)集成的影響；最后，通過在人工生成多層網(wǎng)絡(luò)和真實(shí)多層網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)分析，對(duì)本文算法的有效性和魯棒性進(jìn)行了驗(yàn)證.然而，本文提出的算法面臨時(shí)間復(fù)雜度較高的問題，在未來的工作中將考慮如何提高算法的計(jì)算效率來應(yīng)對(duì)大規(guī)模多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)面臨的挑戰(zhàn).

作者貢獻(xiàn)聲明：趙興旺提出論文算法思想、設(shè)計(jì)實(shí)驗(yàn)方案并修訂論文；張珧溥完成實(shí)驗(yàn)并撰寫論文；梁吉業(yè)提出算法的指導(dǎo)意見和審核論文.