基于譜頂層分割的網(wǎng)絡(luò)社區(qū)層次抽取方法①

熊 英

(江門開放大學(xué) 網(wǎng)絡(luò)信息中心,江門 529000)

網(wǎng)絡(luò)層次設(shè)計進行網(wǎng)絡(luò)社區(qū)檢測的有效方式,在社交網(wǎng)絡(luò)、教育社區(qū)數(shù)據(jù)挖掘和犯罪特征識別等領(lǐng)域得到了廣泛的應(yīng)用.網(wǎng)絡(luò)層次本質(zhì)上是由不同尺度上社區(qū)內(nèi)連接密度的異構(gòu)性定義[1],若社區(qū)內(nèi)的連接密度大于社區(qū)之間的連接密度,則網(wǎng)絡(luò)社區(qū)組織結(jié)構(gòu)具有層次性.將網(wǎng)絡(luò)劃分成若干個連接相對緊密的社區(qū),每個社區(qū)又可能包含若干個連接相對更緊密的子社區(qū)[2–4].例如:存在一個具有40個節(jié)點的二層網(wǎng)絡(luò)組織,設(shè)網(wǎng)絡(luò)的一個社區(qū)Ci內(nèi)部連接密度為p1,它到網(wǎng)絡(luò)其余部分的密度為p0,則有p1>p0;如果社區(qū) Ci由許多小的社區(qū)Cik構(gòu)成,Cik的連接密度為p2,則有p2>p1.如何抽取網(wǎng)絡(luò)層次社區(qū)結(jié)構(gòu)是當(dāng)前的一個重要研究熱點[4].

抽取網(wǎng)絡(luò)層次社區(qū)結(jié)構(gòu)的主要方法是基于層次聚類方法[5,6],其思想是采用譜頂層分割的算法將k最近鄰圖劃分成大量較小的子社區(qū),并用相似的子社區(qū)反復(fù)地合并操作;文獻[7]利用譜頂層分割的方法,提出了一種基于馬爾可夫鏈的蒙特卡羅抽樣技術(shù)預(yù)測丟失連接,用于推導(dǎo)復(fù)雜網(wǎng)絡(luò)的層次,但由于其算法的抽取的空間較大,容易導(dǎo)致數(shù)據(jù)的維度問題;文獻[8]提出了多層次節(jié)點相似的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法,在改進節(jié)點相似度和團體連接緊密度的基礎(chǔ)上構(gòu)建社區(qū)發(fā)現(xiàn)模型,從而更加準(zhǔn)確地找到社區(qū)成員,但這種方法未考慮網(wǎng)絡(luò)的層次的異構(gòu)特性,且不能很好地適用于大型網(wǎng)絡(luò);文獻[9,10]提出了多尺度方法揭示不同尺度下的社區(qū)結(jié)構(gòu),該方法對異構(gòu)網(wǎng)絡(luò)的檢測具有較好的效果,但未考慮社區(qū)內(nèi)外連接密度的動態(tài)變化和社區(qū)間的異構(gòu)性,使該方法不能適用于動態(tài)演化的網(wǎng)絡(luò)社區(qū).

基于以上問題,提出了一種基于譜頂層分割的網(wǎng)絡(luò)社區(qū)層次抽取方法,該方法將網(wǎng)絡(luò)的頂層分割定義為某個子網(wǎng)絡(luò)的二分使得沒有任意一個頂層社區(qū)橫跨兩部分,并給出了頂層分割的期望劃分;引入隊列的思想計算社區(qū)連接密度,自頂向下逐層分解給定網(wǎng)絡(luò),提出社區(qū)層次抽取算法;通過實驗驗證所提出方法的科學(xué)性和合理性.

1 譜頂層分割

1.1 頂層分割

存在一個具有內(nèi)部結(jié)構(gòu)的網(wǎng)絡(luò)N,所有構(gòu)成它的第一層的社區(qū)稱為關(guān)于該網(wǎng)絡(luò)N的頂層社區(qū),所有頂層社區(qū)的集合稱為N的頂層分解,而使N的頂層分解中所有節(jié)點只存在于一個分組中的方法則為N 的譜頂層分割,進而形成一個網(wǎng)絡(luò)的二分,使沒有任何一個頂層分解跨越得到兩個組.如圖1所示,在具有兩層網(wǎng)絡(luò)組織結(jié)構(gòu)中,P1和P2為網(wǎng)絡(luò)N的頂層社區(qū),社區(qū)C1和C2為P1的頂層社區(qū),則P1-P2是網(wǎng)絡(luò)的頂層分割,C1-C2是 P1的頂層分割.

圖1 具有網(wǎng)絡(luò)組織結(jié)構(gòu)的頂層分割

譜頂層分割可以期望找到一個頂層分割或近似頂層分割,由于每次分裂總是試圖找到模塊度最大或者增量最大的二分,如果考慮更多的特征向量,找到一個頂層分割的機會將進一步增強.因此,為使頂層分割得到較高的模塊度,需計算期望最高劃分,從而選擇連接密度最小的返回頂層分割.

1.2 譜頂層期望劃分

設(shè)存在具有3個社區(qū)C1、C2和C3的隨機網(wǎng)絡(luò),假設(shè)連接概率的如表1所示且p0

表1 社區(qū)內(nèi)和社區(qū)間的連接概率配置

譜頂層分割設(shè)置了一個兩層次網(wǎng)絡(luò),即由C1和C2構(gòu)成的社區(qū)和C3形成了網(wǎng)絡(luò)的第一層,而C1和C2形成了第二層.對于該網(wǎng)絡(luò),存在3個二分,即π1:(C1,C2)- (C3),π2:(C1,C3)- (C2)和π3:(C1)- (C2,C3).為進一步分析,將3個連接概率參數(shù)設(shè)置為:p0=0.1,pn=p0+kn×rn.其中,p0作為社區(qū)與社區(qū)之間劃分的初始連接概率,pn在p0的計算基礎(chǔ)上設(shè)置連接概率,并以kn和rn取值[0,1]中的隨機數(shù),這里統(tǒng)一取kn=0.5且rn=0.5,以保持網(wǎng)絡(luò)層次的穩(wěn)定性,以免在出現(xiàn)連接狀態(tài)層次不統(tǒng)一問題.在給定一個網(wǎng)絡(luò)N的前提下,設(shè)Q為期望劃分值,對兩個層次的期望則定義為:

式(1)中,mi和ki分別是社區(qū)i的尺寸和總度.通過計算期望劃分值可以將連接密度最小社區(qū)作為頂層分割,進而對網(wǎng)絡(luò)層次進行抽取.

2 網(wǎng)絡(luò)層次社區(qū)抽取

2.1 連接密度計算

為獲取連接密度最小的社區(qū),引入隊列思想對網(wǎng)絡(luò)N自頂向下逐層分解,采用q_curr表示存儲網(wǎng)絡(luò)第h層的有待分析社區(qū),q_work表示當(dāng)前工作隊列,q_next表示存儲下一層社區(qū).當(dāng)初始化時,q_curr存儲包含網(wǎng)絡(luò)中所有節(jié)點的唯一組,從q_curr的隊頭中取出第一組并將其存入網(wǎng)絡(luò)N,然后將其分解成兩組網(wǎng)絡(luò)數(shù)據(jù)N1和N2,并計算其連接密度:

式(2)中,E(N1,N2)表示網(wǎng)絡(luò)N1和N2之間的邊數(shù),而計算連接密度是關(guān)于N的頂層社區(qū)間的連接密度的一個估計.

當(dāng)N1和N2進入工作隊列q_work時,都可能包含幾個譜頂層分割.如果當(dāng)前q_work非空,則可以從中取出第一組網(wǎng)絡(luò)數(shù)據(jù)N1并對它進行分解;如果不可分,則N1被認為是一個頂層社區(qū),否則它被劃分為兩個更小的組N11和N12,并實時檢查它們之間的連接密度 δ1,計算是否超過譜頂層分割間連接密度的估計值δ?0.如果計算結(jié)果大于估計值δ?0,則此分割不屬于h層分解,而屬于h+1層分解.由此推知,N1是關(guān)于網(wǎng)絡(luò)N的一個譜頂層分割,則N1進入q_next準(zhǔn)備下一層分解,否則,N11和N12都可能是一個譜頂層分割或者幾個譜頂層分割.因此,為進一步取代N1,需進入q_work調(diào)整估計值 δ?0,調(diào)整估計值方法的思路是將原有的估計值在頂層分割次數(shù)的基礎(chǔ)上對下一層網(wǎng)絡(luò)分割后連接密度的預(yù)判,可以實時檢測頂層分割后的每一層網(wǎng)絡(luò)的連接概況,從而提高下一層分割的精準(zhǔn)性.其計算方法如下:

式(3)中,n表示網(wǎng)絡(luò)N從q_curr中取出后,執(zhí)行頂層分割的次數(shù),δ?0表示新的值.當(dāng)q_work為空時,表示從q_curr中取出的第一個組N1已經(jīng)完全分解為它的頂層社區(qū);而從q_curr中取出下一個組直到q_curr為空,將q_next中的組移到q_curr,并進行h+1層分析,重復(fù)上述過程得到調(diào)整后的估計值.

2.2 算法實現(xiàn)

抽取網(wǎng)絡(luò)層次由算法1實現(xiàn),在該算法中函數(shù)subspaceMethod (G,N1,N2,δ1,d)為搜索一個頂層分割,將N分解為兩個組N1和G2,δ1為兩部分間的連接密度,d指示了N是來自于q_curr(d=0)還是來自于q_work(d>0).符號“←”和“→”對應(yīng)隊列的兩個基本操作,即“從隊頭取元素”和“存儲數(shù)據(jù)到隊尾”,而qa?qb表示將隊列qa的所有數(shù)據(jù)移到另一個隊列qb,算法實現(xiàn)如算法1.

算法1.層次抽取算法(偽代碼)輸入:q_curr,q_work,q_next輸出:新的層次社區(qū)1)initialize q_curr,q_work,q_next 2)N→q_curr,h=0 //N表示整個網(wǎng)絡(luò)3)while q_curr is not empty do 4)while q_curr is not empty do 5)N←q_curr, d=0 6)v=subspaceMethod (N,N1,N2,δ1,d)7)if v>0 then //N未被分解8)N1→q_work,N2→q_work,δ*=δ1 9)end if 10)while q_work is not empty do 11)N←q_work and v=subspaceMethod (N,N1,N2,δ1,d)12)if v<=0 then N→q_next δ?<=β×δ?13)else if //β確定一個劃分是否屬于下一個層次14)N1→q_work,N2→q_work update δ*15)d=d+1,compute(Q)//計算期望劃分值16)else N→q_next //N為最頂層社區(qū)17)end if 18)end if 19)end while 20)end while 21)h=h+1 22)if q_next is not empty then output the communities at h level from qnext //返回新的層次社區(qū)?23)q_next q_curr 24)end if 25)end while

由于對網(wǎng)絡(luò)分割的順序取決于集合之間邊的密度,因此上述算法可看作為一種有序的譜方法,首先搜索一個頂層分解并計算網(wǎng)絡(luò)的特征向量,判斷網(wǎng)絡(luò)N是否被分解狀態(tài),然后進入隊列進行頂層分割;在δ??β×δ?中,參數(shù)β的選擇確定一個劃分是否屬于下一層次,本文設(shè)置β=1.6,為實驗測試設(shè)定一個穩(wěn)定值,以解決該值太小導(dǎo)致連接密度的同質(zhì)性較高以及異質(zhì)性較強的問題.

3 實驗分析

仿真實驗在gephi軟件平臺上驗證本文方法的有效性,數(shù)據(jù)來源于Rovirai Virgili[11]大學(xué)Email數(shù)據(jù)中的教師聯(lián)系網(wǎng)絡(luò),該網(wǎng)絡(luò)由7個主要學(xué)院的教師共640個節(jié)點構(gòu)成的三層次網(wǎng)絡(luò),自頂向下分別為學(xué)院、系和研究組,網(wǎng)絡(luò)第一層由4個160節(jié)點的社區(qū)構(gòu)成,每個類似的社區(qū)在第二層分解為4個40節(jié)點的小社區(qū)構(gòu)成,而每個小社區(qū)又在第三層包含了4個10節(jié)點的更小社區(qū),網(wǎng)絡(luò)的邊按照各層的不同的連接密度生成的,滿足p0

3.1 同質(zhì)層次隨機網(wǎng)絡(luò)性能

對于數(shù)據(jù)源中學(xué)院、系、研究組,其每個層次具有相似的層次分布結(jié)構(gòu),在滿足所有層次比例μ=k

圖2 本文方法在層次隨機網(wǎng)絡(luò)的凝聚性精度

由圖2可知,對于具有3個同質(zhì)層的隨機網(wǎng)絡(luò)上的性能,每一個點是在10個實例網(wǎng)絡(luò)上的平均,一個穩(wěn)定的分割可能對應(yīng)于某一層次的劃分.

由圖3可知,通過本文方法與多尺度法和同步法進行比較,說明了多尺度法和同步法對3個層次分割的精度.在最強凝聚情形0.785 和0.885下,雖然同步法在3個層次上都具有相當(dāng)高的精度,但它的精度隨著凝聚強度的下降而快速下降;多尺度法在精度和穩(wěn)定性方面則更接近本文方法,但其規(guī)范化互信息仍然低于本文方法且不適應(yīng)于動態(tài)演化的網(wǎng)絡(luò).

3.2 異質(zhì)層次隨機網(wǎng)絡(luò)性能

由于在更小的網(wǎng)絡(luò)社區(qū)中,其每一層所具有的社區(qū)的尺寸是完全不同的,因此需要在通過本文方法驗證是否適用于尺寸異質(zhì)的情形.由圖4可知,通過實驗,本文方法能夠精確地抽取它的層次組織,其中粗線表示第一層劃分,細線表示第二層劃分,在第二層中社區(qū)內(nèi)的不同灰度節(jié)點表示第三層的網(wǎng)絡(luò)組織,可以顯示層次抽取后的結(jié)果.

圖3 層次隨機網(wǎng)絡(luò)的凝聚性比較

圖4 異質(zhì)隨機網(wǎng)絡(luò)的社區(qū)層次抽取結(jié)果

由圖5可知,譜頂層劃分與真實的劃分完全一致,第二層和第三層精確地逼近真實的劃分,按照互信息精度分別為0.93和0.81.同時,將本文方法與同步法和多尺度法做了比較,在第一層社區(qū)網(wǎng)絡(luò)上,本文方法比同步法和多尺度法在規(guī)范化互信息性能上分別高0.05和0.15,計算精度損失較小,這是由于在第一層社區(qū)網(wǎng)絡(luò)計算連接密度的數(shù)據(jù)量較大,而第二層次和第三層次社區(qū)網(wǎng)絡(luò)上,本文方法比同步法和多尺度法在規(guī)范化互信息性能上的差距逐漸減少,這是由于本文方法引入了隊列的思想,在空間不足的情形下通過不斷調(diào)整連接密度的估計值,實時預(yù)判和分析下一層分割網(wǎng)絡(luò)社區(qū)的密度,在期望劃分的驅(qū)動下釋放密度最小社區(qū)的相關(guān)節(jié)點,然后再計算連接密度的估計值,以此類推,得出最小社區(qū).

4 結(jié)論與展望

針對網(wǎng)絡(luò)的層次社區(qū)檢測問題,提出了一種基于譜頂層分割的網(wǎng)絡(luò)社區(qū)層次抽取方法,選取在線真實數(shù)據(jù)源作為實驗數(shù)據(jù),說明了該方法的科學(xué)性和合理性,為院校社區(qū)教育和大數(shù)據(jù)行為特征識別提供了相關(guān)技術(shù)基礎(chǔ)支持,下一步將從大數(shù)據(jù)的角度對社區(qū)的層次進行抽取,利用語義特征檢測的方法和大數(shù)據(jù)優(yōu)化相關(guān)算法,對社區(qū)層次檢測的語義性進行探索研究,以得出更好的實驗效果.

圖5 本文方法與同步法和多尺度法的規(guī)范化互信息比較