, ，，

(西安理工大學(xué) 自動化與信息工程學(xué)院， 西安 710048)

0 引言

現(xiàn)實世界中的許多復(fù)雜系統(tǒng)可以用復(fù)雜網(wǎng)絡(luò)來表示，社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個重要拓?fù)涮匦訹1]，它具有同一類節(jié)點之間聯(lián)系緊密，不同類節(jié)點之間聯(lián)系稀疏的特性。社團(tuán)發(fā)現(xiàn)是根據(jù)復(fù)雜網(wǎng)絡(luò)里隱含的拓?fù)湫畔碚页銎渲械纳鐖F(tuán)結(jié)構(gòu)，它可應(yīng)用于信息標(biāo)簽化、預(yù)防病毒，預(yù)測行為等。研究復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的性質(zhì)不僅有助于分析復(fù)雜網(wǎng)絡(luò)的功能，對研究生物學(xué)、醫(yī)學(xué)、工程學(xué)、計算機科學(xué)等也具有十分重要的意義。因此，對社團(tuán)發(fā)現(xiàn)算法的研究受到了國內(nèi)外許多學(xué)者的廣泛關(guān)注[2]。

目前，已經(jīng)存在的社團(tuán)發(fā)現(xiàn)算法多針對于單層網(wǎng)絡(luò)，例如：以圖分割[4]、GN[5]算法和標(biāo)簽傳播算法(LPA)[6]為代表的從網(wǎng)絡(luò)的整體到局部的社團(tuán)發(fā)現(xiàn)算法，當(dāng)然也有以Newman快速算法[7]、譜聚類[8]算法和CNM[9]算法為代表的從網(wǎng)絡(luò)的局部到整體的社團(tuán)發(fā)現(xiàn)算法。對多層網(wǎng)絡(luò)的研究最初起源于社會科學(xué)領(lǐng)域，后來發(fā)展到醫(yī)學(xué)、計算機科學(xué)等。近年來，多層網(wǎng)絡(luò)的研究逐步發(fā)展起來，繼而出現(xiàn)了許多多層社團(tuán)發(fā)現(xiàn)算法：CLEDCC算法[10]、多層α-核散列聚類的異常數(shù)據(jù)社團(tuán)發(fā)現(xiàn)算法[11]、基于多層粒子群的社團(tuán)發(fā)現(xiàn)算法[12]、CLECC算法[13]、多層網(wǎng)絡(luò)局部社團(tuán)發(fā)現(xiàn)算法[14]以及通過比較節(jié)點度之間的關(guān)系來發(fā)現(xiàn)多層網(wǎng)絡(luò)中的局部社團(tuán)結(jié)構(gòu)[15]等。

為了提高目前多層網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法社團(tuán)劃分的準(zhǔn)確度，以及對于一些沒有直接相連的節(jié)點作出準(zhǔn)確的劃分。本文提出一種新的算法，通過結(jié)合RA相似度提取拓?fù)湫畔ⅲ瑥亩g接的提取社團(tuán)結(jié)構(gòu)。這種基于層次覆蓋的多層網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法在時間復(fù)雜度方面得到了改善。實驗結(jié)果表明，該算法能較準(zhǔn)確地劃分出多層網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，避免了對多層網(wǎng)絡(luò)劃分的局部性。

1 算法

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

定義單層網(wǎng)絡(luò)G=，其中節(jié)點集為V=(v1,v2,...,vn)，n是節(jié)點數(shù)目，邊集為E，(vi,vj)表示節(jié)點i與j之間的邊。圖1是一個簡單的無權(quán)無向圖，假設(shè)它是某實驗室的成員圖，每個節(jié)點代表一個成員，每個邊代表成員之間的關(guān)系。

圖1 單層網(wǎng)絡(luò)模型

一個特定復(fù)雜系統(tǒng)構(gòu)成一個單層網(wǎng)絡(luò)，人們在生活中會碰到各種各樣的單層網(wǎng)絡(luò)，比如在日常通信中會用到的微信這一通訊工具，微信里的朋友圈就構(gòu)成了一個單層的復(fù)雜系統(tǒng)。然而，隨著社會的快速發(fā)展，人們在平時的社交過程中不僅僅局限于微信這一種通信工具，還會涉及到微博、E-mail、Twitter、Facebook等，每一種通訊工具都會構(gòu)成一個單層的復(fù)雜系統(tǒng)，因此，日常生活中人們處在多個單層的復(fù)雜系統(tǒng)之間，這就構(gòu)成了一個多層次復(fù)雜系統(tǒng)即多層網(wǎng)絡(luò)。

多層網(wǎng)絡(luò)的每一層都可以用一個圖來表示，由于圖與圖的某些節(jié)點是相互對應(yīng)的關(guān)系，且多層網(wǎng)絡(luò)是由多個相互對應(yīng)的關(guān)系組成的網(wǎng)絡(luò)，因此了解每一個多層網(wǎng)絡(luò)里不同圖節(jié)點之間的對應(yīng)關(guān)系很重要。下面給出多層網(wǎng)絡(luò)的定義：多層網(wǎng)絡(luò)是一個單層網(wǎng)絡(luò)的集合，多層網(wǎng)絡(luò)G=，每一層網(wǎng)絡(luò)的層次序號=，i=，i∈1,...,l，Vi和Ei分別是第i層網(wǎng)絡(luò)的節(jié)點集和邊集.圖2是一個柱形多層網(wǎng)絡(luò)的模型，第一層與第二層之間的節(jié)點都是一一對應(yīng)的。假設(shè)第一層是微信網(wǎng)絡(luò)，第二層是微博網(wǎng)絡(luò)，如果微信里的用戶在微博里都有注冊，那么在微博網(wǎng)絡(luò)里這些用戶之間的關(guān)系可以代表他們在微信網(wǎng)絡(luò)里的關(guān)系，在這里需要注意每個用戶的賬戶只能在他所在的層次登錄，不能在其他層次登錄。圖3是一個較為復(fù)雜的普通多層網(wǎng)絡(luò)，假設(shè)第一層是Twitter網(wǎng)絡(luò)，第二層是Facebook網(wǎng)絡(luò)，第一層的節(jié)點2是Twitter網(wǎng)絡(luò)里的某用戶，那么第一層的節(jié)點2對應(yīng)的第二層的兩個節(jié)點2是他在Facebook網(wǎng)絡(luò)里注冊的不同的賬戶，因此，不同節(jié)點不一定代表不同的用戶，而是不同的賬戶。

圖2 柱形多層網(wǎng)絡(luò) 圖3 普通多層網(wǎng)絡(luò)

1.2 RA相似度

由于多層網(wǎng)絡(luò)的多重性，且為了準(zhǔn)確的找到不同層次任意兩個節(jié)點之間的連接密切關(guān)系，本文采用RA相似度[16]公式：

(1)

公式(1)中的φ(i)∩φ(j)表示節(jié)點i和節(jié)點j的共同鄰居節(jié)點集合，k(i)表示兩個節(jié)點共同鄰居的節(jié)點的度.該相似度公式與以往的相似度公式不同之處在于：在比較兩個節(jié)點之間的相似度時，已經(jīng)存在的相似度公式僅考慮的是共同的鄰居節(jié)點數(shù)目，如Jaccard相似度[17]，而RA相似度基于網(wǎng)絡(luò)中資源配置的原理，通過比較兩個節(jié)點之間的共同的鄰居節(jié)點的特征來反映這兩個節(jié)點之間的相似性。RA相似度通過公式(1)計算兩個節(jié)點的共同鄰居節(jié)點集合里每個節(jié)點的度，以得到兩個節(jié)點之間的相似性。RA相似度的方法避免了局部相似度存在的一些問題，能更準(zhǔn)確的比較兩個節(jié)點之間的相似性，下面我們通過一個例子來介紹一下RA相似度公式：

圖4 節(jié)點圖

1.3 算法核心

給定一個多層網(wǎng)絡(luò)G=，定義C為某一層的內(nèi)部初始核心節(jié)點社團(tuán)，定義D={v∈C|?(u,v)∈E,u∈S}為社團(tuán)C的邊界子集合，定義S=(v∈VC|(u,v)∈E,u∈C)為外層節(jié)點集合，ED代表集合D與集合S中節(jié)點之間的邊，是第i層的邊集，定義L為局部社團(tuán)相似性測度，表示為社團(tuán)內(nèi)部節(jié)點連接拓?fù)湫畔㈥P(guān)系與社團(tuán)間節(jié)點連接拓?fù)湫畔㈥P(guān)系之間的比值。首先隨機選取一個節(jié)點v作為初始社團(tuán)C，通過比較給出兩個公式來表示社團(tuán)內(nèi)連接關(guān)系和社團(tuán)間連接關(guān)系：

(2)

(3)

公式(3)表示社團(tuán)間節(jié)點連接拓?fù)湫畔㈥P(guān)系。

1.4 判斷條件

為了判斷一個外層節(jié)點加入內(nèi)部社團(tuán)C后是否能加強社團(tuán)的緊密性，定義局部社團(tuán)相似性測度L來評價外層節(jié)點加入內(nèi)層節(jié)點之后的效果，公式如下所示：

(4)

若外層節(jié)點u加入C后滿足以下條件：

L(C∪{u})>L(C)

(5)

Lint(C∪{u})>Lint(C)

(6)

公式(5)、(6)表示若節(jié)點u加入社團(tuán)C后，局部社團(tuán)相似性測度L值變大，L值越大表明外層節(jié)點加入內(nèi)層社團(tuán)C后，C更緊密，且內(nèi)層社團(tuán)與外層社團(tuán)連接更加稀疏，社團(tuán)結(jié)構(gòu)更加明顯。且社團(tuán)內(nèi)部節(jié)點連接更緊密，此時將節(jié)點u加入到v所在的社團(tuán)C中。在判斷的過程中，每次將L取最大值時的外層節(jié)點加入到社團(tuán)C中，迭代地判斷每個節(jié)點，直到L不再增大。

用L作為劃分節(jié)點的評判標(biāo)準(zhǔn)，將每次使得L值最大的外層節(jié)點劃分到內(nèi)層社團(tuán)C中，直到不存在符合條件的節(jié)點出現(xiàn)為止，但這種方法在面對一些異常節(jié)點時通常不能有很好的劃分效果，對于這種情況，若外層節(jié)點符合以下兩個條件，就將它們劃分到社團(tuán)C中：

(7)

(8)

公式(7)表示加入節(jié)點u后，社團(tuán)內(nèi)連接系數(shù)較沒加入u之前增大，社團(tuán)間連接系數(shù)變小。明顯地看出，公式(7)所述情況L值會增大，且符合(5)、(6)兩個條件，此時，將節(jié)點u劃分到社團(tuán)C中。如果加入節(jié)點u后遇到公式(8)這種情況，即加入節(jié)點u后，社團(tuán)內(nèi)連接系數(shù)和社團(tuán)間連接系數(shù)較之前都有增大，社團(tuán)內(nèi)部連接以及社團(tuán)之間的連接都更加緊密，此時節(jié)點u有兩種可能：

(1)節(jié)點u符合以上條件，且u不是核心節(jié)點，可以與社團(tuán)C內(nèi)的節(jié)點進(jìn)行合并；

(2)節(jié)點u可能是一個核心節(jié)點，它與社團(tuán)內(nèi)和社團(tuán)外的節(jié)點都有大量的連接。

對于(1)中的節(jié)點u，將它劃分到社團(tuán)C中。對于(2)中的節(jié)點u，暫時將它加入到C中，直到所有節(jié)點被劃分到相應(yīng)的社團(tuán)后，再將這些疑似的核心節(jié)點從C中移除，此時，再返回到條件(5)、(6)對這些節(jié)點進(jìn)行判斷。

1.5 算法流程

該算法首先隨機選取一個節(jié)點v作為覆蓋第一層的中心節(jié)點，在初始階段，集合D和集合C里只有節(jié)點v，集合S是外層節(jié)點集合，不斷地從S集合里隨機選出節(jié)點u，如果u加入到C中使得L值較大且能滿足公式(4)以及公式(5)中的兩個條件，則將u加入到v所在的集合里，迭代上述過程，在每一步迭代中，都要更新集合D、集合C和集合S，且直到L值不再增大，算法結(jié)束。具體算法流程如下所示。

算法：基于層次覆蓋的多層網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法：

輸入：多層網(wǎng)絡(luò)G；

輸出：網(wǎng)絡(luò)G的社團(tuán)劃分結(jié)果。

(1)初始化：隨機選取一節(jié)點v加入集合C與集合D中，S為外層節(jié)點集合。

1)L(C∪{u})>L(C)加入節(jié)點u后，相似性測度L變大；

2)Lint(C∪{u})>Lint(C)加入節(jié)點u后，社團(tuán)內(nèi)部連接系數(shù)變大。

(4)若節(jié)點u同時滿足條件1)和2)，將u加入到社團(tuán)C中，若節(jié)點u為疑似核心節(jié)點，也將其放入C中，返回第(2)步，直到遍歷所有節(jié)點，L不再變大，再將疑似的核心節(jié)點從C中移除，返回(3)對其進(jìn)行重新判斷。

(5)合并集合C與集合D,并計算不同層次的模塊度Q。

2 實驗分析

2.1 多層網(wǎng)絡(luò)數(shù)據(jù)

為了測試算法的性能，會用到的不同的多層網(wǎng)絡(luò)數(shù)據(jù)集，下面先來對這些數(shù)據(jù)集做一個簡單的介紹。

MIT Reality Mining[18]網(wǎng)絡(luò)數(shù)據(jù)集是通過給麻省理工學(xué)院87個移動用戶安裝一個軟件，記錄用戶之間的數(shù)據(jù)交互信息，網(wǎng)絡(luò)的每一層分別代表從現(xiàn)實中采集到的用戶的物理位置、藍(lán)牙交互和通話記錄等用戶之間的互動行為。

E-mail[19]網(wǎng)絡(luò)數(shù)據(jù)集是一個記錄Enron公司員工之間電子郵件往來的數(shù)據(jù)集，該網(wǎng)絡(luò)有150個節(jié)點，每個節(jié)點代表1個用戶，每條邊代表2個用戶之間發(fā)的一條電子郵件，該網(wǎng)絡(luò)包括用戶之間發(fā)送郵件的時間、發(fā)送主題、發(fā)送者賬戶以及接收者賬戶等。網(wǎng)絡(luò)中的每一層分別代表員工之間的關(guān)系和郵件信息內(nèi)容的相似性。

IMDB[20]網(wǎng)絡(luò)數(shù)據(jù)集是一個互聯(lián)網(wǎng)電影數(shù)據(jù)集，該數(shù)據(jù)集包含300個節(jié)點，每個節(jié)點代表一個一位演員，每條邊代表這兩個演員一起演了一部戲，該網(wǎng)絡(luò)數(shù)據(jù)集的每一層分別代表第一年演員之間的合作、最后一年演員之間的合作、演員的平均收入和門票賣出的平均數(shù)量。

在實驗仿真部分，用以上三個多層網(wǎng)絡(luò)數(shù)據(jù)集對算法進(jìn)行測試，測試了算法在三種網(wǎng)絡(luò)上的運行時間，并用模塊度Q[21]來評價社團(tuán)劃分結(jié)果，之后又將該算法與CLECC、CLEDCC兩種算法進(jìn)行了對比，結(jié)果表明本文算法的準(zhǔn)確度更高，運行時間更少。

2.2 評價標(biāo)準(zhǔn)

為了評價社團(tuán)劃分的結(jié)果，采用Newman和Girvan提出的模塊度Q。其定義式如下：

(9)

圖5 隨著層數(shù)的變化，社團(tuán)數(shù)量的變化

圖6 隨著層數(shù)的變化，社團(tuán)數(shù)量的變化

圖7 不同層次的模塊度Q值的變化

圖5、6代表算法對三種網(wǎng)絡(luò)的劃分隨著層數(shù)的變化，社團(tuán)數(shù)量的變化，其中x軸代表某一層次，y軸代表社團(tuán)數(shù)量。圖7代表不同層次的模塊度Q值的變化，其中x軸代表社團(tuán)數(shù)量，y軸代表模塊度Q值。

圖8 E-mail網(wǎng)絡(luò)模塊度Q值對比

圖8和圖9分別是本文算法、CLECC算法以及CLEDCC算法在E-mail網(wǎng)絡(luò)上以及IMDB網(wǎng)絡(luò)上劃分的模塊度Q值的對比，其中x軸代表社團(tuán)數(shù)量，y軸代表模塊度Q值。從圖8可以看出，將E-mail網(wǎng)絡(luò)劃分在24個社團(tuán)左右時，有最大的模塊度Q值，此時的劃分效果較好。從圖9可以看出，將IMDB網(wǎng)絡(luò)劃分在95個社團(tuán)左右時，會得到較為明顯劃分結(jié)果。

圖9 IMDB網(wǎng)絡(luò)模塊度Q值對比

由圖8和圖9可以看出，不同算法在E-mail網(wǎng)絡(luò)和IMDB網(wǎng)絡(luò)上的模塊度Q值不盡相同，本文算法相比CLECC算法和CLEDCC算法模塊度更高，劃分也更準(zhǔn)確。

表1 三種算法運行時間比較(ms)

表1是本文算法和CLECC、CLEDCC三種算法對三個網(wǎng)絡(luò)劃分時間的對比，可以看出本文算法需要的運行時間更少，效率更高。

3 結(jié)論與展望

文中采用RA相似度和一種多層網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)檢測的模型，提出了一種基于層次覆蓋的多層網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)的新算法，并將算法在幾個經(jīng)典的多層網(wǎng)絡(luò)進(jìn)行了性能測試，均取得了不錯的劃分結(jié)果。實驗的后一部分將本文算法與CLECC和CLEDCC兩種算法作了比較，結(jié)果表明，不論在模塊度值還是算法運行效率上都有所提高，避免了沒有直接相連節(jié)點無法正確劃分的情況，避免了對多層網(wǎng)絡(luò)劃分的局部性。