基于層次覆蓋的多層網絡社團發現算法

, ，，

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

0 引言

現實世界中的許多復雜系統可以用復雜網絡來表示，社團結構是復雜網絡的一個重要拓撲特性[1]，它具有同一類節點之間聯系緊密，不同類節點之間聯系稀疏的特性。社團發現是根據復雜網絡里隱含的拓撲信息來找出其中的社團結構，它可應用于信息標簽化、預防病毒，預測行為等。研究復雜網絡社團結構的性質不僅有助于分析復雜網絡的功能，對研究生物學、醫學、工程學、計算機科學等也具有十分重要的意義。因此，對社團發現算法的研究受到了國內外許多學者的廣泛關注[2]。

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

為了提高目前多層網絡社團發現算法社團劃分的準確度，以及對于一些沒有直接相連的節點作出準確的劃分。本文提出一種新的算法，通過結合RA相似度提取拓撲信息，從而間接的提取社團結構。這種基于層次覆蓋的多層網絡社團發現算法在時間復雜度方面得到了改善。實驗結果表明，該算法能較準確地劃分出多層網絡中的社團結構，避免了對多層網絡劃分的局部性。

1 算法

1.1 多層網絡

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

圖1 單層網絡模型

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

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

圖2 柱形多層網絡 圖3 普通多層網絡

1.2 RA相似度

由于多層網絡的多重性，且為了準確的找到不同層次任意兩個節點之間的連接密切關系，本文采用RA相似度[16]公式：

(1)

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

圖4 節點圖

1.3 算法核心

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

(2)

(3)

公式(3)表示社團間節點連接拓撲信息關系。

1.4 判斷條件

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

(4)

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

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

(5)

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

(6)

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

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

(7)

(8)

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

(1)節點u符合以上條件，且u不是核心節點，可以與社團C內的節點進行合并；

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

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

1.5 算法流程

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

算法：基于層次覆蓋的多層網絡社團發現算法：

輸入：多層網絡G；

輸出：網絡G的社團劃分結果。

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

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

2)Lint(C∪{u})>Lint(C)加入節點u后，社團內部連接系數變大。

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

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

2 實驗分析

2.1 多層網絡數據

為了測試算法的性能，會用到的不同的多層網絡數據集，下面先來對這些數據集做一個簡單的介紹。

MIT Reality Mining[18]網絡數據集是通過給麻省理工學院87個移動用戶安裝一個軟件，記錄用戶之間的數據交互信息，網絡的每一層分別代表從現實中采集到的用戶的物理位置、藍牙交互和通話記錄等用戶之間的互動行為。

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

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

在實驗仿真部分，用以上三個多層網絡數據集對算法進行測試，測試了算法在三種網絡上的運行時間，并用模塊度Q[21]來評價社團劃分結果，之后又將該算法與CLECC、CLEDCC兩種算法進行了對比，結果表明本文算法的準確度更高，運行時間更少。

2.2 評價標準

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

(9)

圖5 隨著層數的變化，社團數量的變化

圖6 隨著層數的變化，社團數量的變化

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

圖5、6代表算法對三種網絡的劃分隨著層數的變化，社團數量的變化，其中x軸代表某一層次，y軸代表社團數量。圖7代表不同層次的模塊度Q值的變化，其中x軸代表社團數量，y軸代表模塊度Q值。

圖8 E-mail網絡模塊度Q值對比

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

圖9 IMDB網絡模塊度Q值對比

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

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

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

3 結論與展望

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