熊 英

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

網(wǎng)絡(luò)層次設(shè)計(jì)進(jìn)行網(wǎng)絡(luò)社區(qū)檢測(cè)的有效方式,在社交網(wǎng)絡(luò)、教育社區(qū)數(shù)據(jù)挖掘和犯罪特征識(shí)別等領(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ò)劃分成若干個(gè)連接相對(duì)緊密的社區(qū),每個(gè)社區(qū)又可能包含若干個(gè)連接相對(duì)更緊密的子社區(qū)[2–4].例如:存在一個(gè)具有40個(gè)節(jié)點(diǎn)的二層網(wǎng)絡(luò)組織,設(shè)網(wǎng)絡(luò)的一個(gè)社區(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)前的一個(gè)重要研究熱點(diǎn)[4].

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

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

1 譜頂層分割

1.1 頂層分割

存在一個(gè)具有內(nèi)部結(jié)構(gòu)的網(wǎng)絡(luò)N,所有構(gòu)成它的第一層的社區(qū)稱為關(guān)于該網(wǎng)絡(luò)N的頂層社區(qū),所有頂層社區(qū)的集合稱為N的頂層分解,而使N的頂層分解中所有節(jié)點(diǎn)只存在于一個(gè)分組中的方法則為N 的譜頂層分割,進(jìn)而形成一個(gè)網(wǎng)絡(luò)的二分,使沒(méi)有任何一個(gè)頂層分解跨越得到兩個(gè)組.如圖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)的頂層分割

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

1.2 譜頂層期望劃分

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

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

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

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

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

2.1 連接密度計(jì)算

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

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

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

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

2.2 算法實(shí)現(xiàn)

抽取網(wǎng)絡(luò)層次由算法1實(shí)現(xiàn),在該算法中函數(shù)subspaceMethod (G,N1,N2,δ1,d)為搜索一個(gè)頂層分割,將N分解為兩個(gè)組N1和G2,δ1為兩部分間的連接密度,d指示了N是來(lái)自于q_curr(d=0)還是來(lái)自于q_work(d>0).符號(hào)“←”和“→”對(duì)應(yīng)隊(duì)列的兩個(gè)基本操作,即“從隊(duì)頭取元素”和“存儲(chǔ)數(shù)據(jù)到隊(duì)尾”,而qa?qb表示將隊(duì)列qa的所有數(shù)據(jù)移到另一個(gè)隊(duì)列qb,算法實(shí)現(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表示整個(gè)網(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 //β確定一個(gè)劃分是否屬于下一個(gè)層次14)N1→q_work,N2→q_work update δ*15)d=d+1,compute(Q)//計(jì)算期望劃分值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

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論與展望

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

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