, ,,
(西安理工大學(xué) 自動化與信息工程學(xué)院, 西安 710048)
現(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ò)劃分的局部性。
定義單層網(wǎng)絡(luò)G=
圖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=
圖2 柱形多層網(wǎng)絡(luò) 圖3 普通多層網(wǎng)絡(luò)
由于多層網(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é)點圖
給定一個多層網(wǎng)絡(luò)G=
(2)
(3)
公式(3)表示社團(tuán)間節(jié)點連接拓?fù)湫畔㈥P(guān)系。
為了判斷一個外層節(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)行判斷。
該算法首先隨機選取一個節(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。
為了測試算法的性能,會用到的不同的多層網(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)確度更高,運行時間更少。
為了評價社團(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ò)劃分時間的對比,可以看出本文算法需要的運行時間更少,效率更高。
文中采用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ò)劃分的局部性。