基于譜頂層分割的網絡社區層次抽取方法①

熊 英

(江門開放大學 網絡信息中心,江門 529000)

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

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

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

1 譜頂層分割

1.1 頂層分割

存在一個具有內部結構的網絡N,所有構成它的第一層的社區稱為關于該網絡N的頂層社區,所有頂層社區的集合稱為N的頂層分解,而使N的頂層分解中所有節點只存在于一個分組中的方法則為N 的譜頂層分割,進而形成一個網絡的二分,使沒有任何一個頂層分解跨越得到兩個組.如圖1所示,在具有兩層網絡組織結構中,P1和P2為網絡N的頂層社區,社區C1和C2為P1的頂層社區,則P1-P2是網絡的頂層分割,C1-C2是 P1的頂層分割.

圖1 具有網絡組織結構的頂層分割

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

1.2 譜頂層期望劃分

設存在具有3個社區C1、C2和C3的隨機網絡,假設連接概率的如表1所示且p0

表1 社區內和社區間的連接概率配置

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

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

2 網絡層次社區抽取

2.1 連接密度計算

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

式(2)中,E(N1,N2)表示網絡N1和N2之間的邊數,而計算連接密度是關于N的頂層社區間的連接密度的一個估計.

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

式(3)中,n表示網絡N從q_curr中取出后,執行頂層分割的次數,δ?0表示新的值.當q_work為空時,表示從q_curr中取出的第一個組N1已經完全分解為它的頂層社區;而從q_curr中取出下一個組直到q_curr為空,將q_next中的組移到q_curr,并進行h+1層分析,重復上述過程得到調整后的估計值.

2.2 算法實現

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

算法1.層次抽取算法(偽代碼)輸入:q_curr,q_work,q_next輸出:新的層次社區1)initialize q_curr,q_work,q_next 2)N→q_curr,h=0 //N表示整個網絡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為最頂層社區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 //返回新的層次社區?23)q_next q_curr 24)end if 25)end while

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

3 實驗分析

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

3.1 同質層次隨機網絡性能

對于數據源中學院、系、研究組,其每個層次具有相似的層次分布結構,在滿足所有層次比例μ=k

圖2 本文方法在層次隨機網絡的凝聚性精度

由圖2可知,對于具有3個同質層的隨機網絡上的性能,每一個點是在10個實例網絡上的平均,一個穩定的分割可能對應于某一層次的劃分.

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

3.2 異質層次隨機網絡性能

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

圖3 層次隨機網絡的凝聚性比較

圖4 異質隨機網絡的社區層次抽取結果

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

4 結論與展望

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

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