蔣智恩
(福建信息職業(yè)技術(shù)學(xué)院 商貿(mào)管理系,福建 福州 350003)
一般認(rèn)為,社區(qū)是一些連接更為緊密的節(jié)點(diǎn)集合?,F(xiàn)實(shí)世界中許多網(wǎng)絡(luò)都具有社區(qū)特性,比如通信網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)等。為了分析這些復(fù)雜網(wǎng)絡(luò)的拓?fù)涮匦约敖Y(jié)構(gòu)功能,對(duì)其進(jìn)行社區(qū)檢測(cè)很有必要。
實(shí)際網(wǎng)絡(luò)中更為常見(jiàn)的是社區(qū)重疊的情況,即一個(gè)節(jié)點(diǎn)同時(shí)被多個(gè)社區(qū)共享。近年來(lái)學(xué)者們提出一系列相應(yīng)的啟發(fā)式算法。Palla提出了CPM算法[1],算法認(rèn)為一個(gè)社區(qū)內(nèi)節(jié)點(diǎn)間的邊可形成全聯(lián)通圖(clique),通過(guò)相互連通的k-團(tuán)來(lái)發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。Lancichinetti[2]提出了LFM算法,該算法的基本思想是通過(guò)目標(biāo)函數(shù)的直方圖峰值區(qū)分社區(qū)。Steve等人[3]在GN算法的基礎(chǔ)上提出了CONGA算法,該算法將部分節(jié)點(diǎn)分裂成多個(gè)子節(jié)點(diǎn),之后利用GN算法來(lái)處理,但其時(shí)間復(fù)雜度很高?;诰仃囈蚴椒纸獾姆椒ㄒ部捎糜谥丿B社區(qū)檢測(cè),并擴(kuò)展出很多新算法,例如Psorakis等[4]和Wang等[5]提出的NMF算法,但是NMF所涉及的數(shù)據(jù)矩陣通常存在缺失值。目前關(guān)于社區(qū)結(jié)構(gòu)的多尺度特征研究還很少,陳東等[6]基于結(jié)構(gòu)相似度提出了多尺度局部社區(qū)發(fā)現(xiàn)算法,引入尺度分子來(lái)定義結(jié)構(gòu)模塊度,在局部社區(qū)檢測(cè)中得到了良好的效果。郭玉泉等[7]則將譜分析與啟發(fā)式遺傳算法相結(jié)合,提出多尺度社區(qū)檢測(cè)算法HGASA。
基于以上研究,嘗試提出一種模塊化多尺度通信重疊社區(qū)檢測(cè)算法,從單個(gè)節(jié)點(diǎn)、單個(gè)社區(qū)以及整個(gè)網(wǎng)絡(luò)的尺度上,量化各種尺度下社區(qū)結(jié)構(gòu)特征,合并在一起組成算法內(nèi)容。最后通過(guò)實(shí)驗(yàn)驗(yàn)證不同尺度下各類參數(shù)對(duì)檢測(cè)效果的影響,并在現(xiàn)實(shí)世界網(wǎng)絡(luò)中檢驗(yàn)算法有效性和準(zhǔn)確性。
為了完整描述社區(qū)特性,需要解決社區(qū)定義的多尺度問(wèn)題:?jiǎn)蝹€(gè)節(jié)點(diǎn)的尺度、單個(gè)社區(qū)的尺度、整個(gè)網(wǎng)絡(luò)的尺度。算法功能:針對(duì)社會(huì)網(wǎng)絡(luò)中社區(qū)重疊問(wèn)題,嘗試從尺度特征出發(fā)提出合理的解決方法。對(duì)于一個(gè)給定的待檢社區(qū),根據(jù)每種尺度的社區(qū)結(jié)構(gòu)調(diào)整具體的量化模塊,因此,提出的方法是高度模塊化的。這種方法為探索社區(qū)檢測(cè)算法提供了一種新思路,符合目標(biāo)社區(qū)檢測(cè)要求。多尺度社區(qū)結(jié)構(gòu)反映了在傳播過(guò)程中的網(wǎng)絡(luò)動(dòng)力學(xué)特征,可以有效地揭示出網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。
輸入:網(wǎng)絡(luò)的鄰接矩陣
算法:
③ 如果社區(qū)中有節(jié)點(diǎn)未被聚類,將它們添加到與他們連接最頻繁的社區(qū)。成本:可忽略;
④ 剔除檢測(cè)出的更小的社區(qū),規(guī)定所有的節(jié)點(diǎn)至少屬于一個(gè)社區(qū),描述方法見(jiàn)1.3節(jié)。
輸出:網(wǎng)絡(luò)中節(jié)點(diǎn)集組成的社區(qū)。
由于算法的出發(fā)點(diǎn)是從邊的排列中識(shí)別社區(qū),這里把描述社區(qū)結(jié)構(gòu)的節(jié)點(diǎn)集稱為邊緣描述符集。一個(gè)節(jié)點(diǎn)所屬的連通圖都可由邊緣描述符集產(chǎn)生。
圖1 網(wǎng)絡(luò)中星標(biāo)節(jié)點(diǎn)的自我中心網(wǎng)
假設(shè)一個(gè)節(jié)點(diǎn)與某個(gè)社區(qū)內(nèi)其他節(jié)點(diǎn)有更密切的聯(lián)系,那它屬于這個(gè)社區(qū)的可能性就更大,這說(shuō)明同一社區(qū)內(nèi)節(jié)點(diǎn)間的邊連接更加密集。因此,一個(gè)由邊集合組成的連通圖可看作是一種邊聚類的原型。同時(shí),當(dāng)一個(gè)節(jié)點(diǎn)屬于幾個(gè)相對(duì)較大且不相交的連通圖時(shí),這個(gè)節(jié)點(diǎn)可認(rèn)為是多個(gè)社區(qū)間的交點(diǎn)。在以上社區(qū)形成規(guī)則的基礎(chǔ)上,提出提取邊集的方法,其中,這些邊集不僅連接緊密,而且大部分彼此不相交,每個(gè)節(jié)點(diǎn)的自我中心網(wǎng)(egonet)可認(rèn)為是該節(jié)點(diǎn)的邊緣描述符集,如圖1所示,所有的淺灰和淺灰邊都屬于星標(biāo)節(jié)點(diǎn)的自我中心網(wǎng)。每個(gè)集合可看作是社區(qū)結(jié)構(gòu)小尺度特征的一組編碼。
邊緣描述符集被提取出來(lái)后,需要一種集中現(xiàn)有局部特征共同形成社區(qū)的方式。為此,使用和社區(qū)尺度相關(guān)的量化特征來(lái)聚類這些邊集。
圖2 黑色社區(qū)、灰色社區(qū)的分布
一個(gè)待檢測(cè)社區(qū)擁有的總體量化特征,就是它們具有比整個(gè)網(wǎng)絡(luò)更高的邊密度,這一特點(diǎn)也可以在單個(gè)節(jié)點(diǎn)的邊緣描述符集上清楚地顯現(xiàn)出來(lái)。網(wǎng)絡(luò)示例如圖2中所示。對(duì)于黑色和灰色社區(qū),需要將黑邊集合及灰邊集合與白邊集合區(qū)分開(kāi)。從社區(qū)的角度看,目的就是尋找形成社區(qū)的邊緣描述符集的集合。
為解釋聚集邊緣描述符集形成社區(qū)這種特性,采用了連接密度的說(shuō)法。令C表示節(jié)點(diǎn)集組成的社區(qū),E(C)表示C中所有成員兩者之間的邊集。即假定一個(gè)含有n個(gè)節(jié)點(diǎn)的集,則該連通圖的邊的最大數(shù)量為n(n-1)/2。定義邊密度如下:
(1)
實(shí)現(xiàn)社區(qū)構(gòu)成方法需滿足ρ(C)=D的條件。其中,D表示給定的入鏈(內(nèi)部連接)密度,取值為0≤D≤1,所涉及節(jié)點(diǎn)的數(shù)目|C|盡可能地大。作為輸入量,D的合理取值取決于從網(wǎng)絡(luò)中提取的結(jié)構(gòu)尺度;閾值密度更低的對(duì)應(yīng)于更稀疏的社區(qū),閾值密度更高的對(duì)應(yīng)更緊密的社區(qū)。
采取貪心算法擴(kuò)展社區(qū),如果它們將ρ降低到最小限度,但仍保持在給定的閾值以上,新的節(jié)點(diǎn)將被吸收到社區(qū)中,并連帶產(chǎn)生新的邊緣描述符集。從數(shù)學(xué)角度看,這不是最佳優(yōu)化方法,但它保留了社區(qū)的直觀形成過(guò)程,展示了社會(huì)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)在各個(gè)角度的擴(kuò)張過(guò)程,這和文獻(xiàn)[8]中邊緣描述符集的滲流法相似,也可看作是文獻(xiàn)[9][10]的變體。社區(qū)擴(kuò)展算法描述如下:
輸入:網(wǎng)絡(luò)中已經(jīng)檢測(cè)到的所有邊緣描述符集
算法:
① 從最大的未聚類的邊緣描述符集開(kāi)始,以此作為社區(qū)基礎(chǔ);
② 為將形成的社區(qū)找到使入鏈密度降低到最低限度的邊緣描述符集;
③ 如果入鏈密度保持在用戶提供的密度閾值以上,添加邊緣描述符到將要形成的社區(qū)中;
④ 重復(fù)步驟②和步驟③直到?jīng)]有邊緣描述符集滿足密度約束條件;
⑤ 重復(fù)步驟①直到?jīng)]有邊緣描述符集保持未聚類。
輸出:社區(qū)的初始集。
圖3 社區(qū)網(wǎng)絡(luò)節(jié)點(diǎn)聚類示意圖
為最終實(shí)現(xiàn)網(wǎng)絡(luò)中沒(méi)有剩余的未聚類的節(jié)點(diǎn),且社區(qū)個(gè)數(shù)為最少,還須挖掘出整個(gè)網(wǎng)絡(luò)層面上的社區(qū)特性。這里采用常規(guī)啟發(fā)式方法,保證了網(wǎng)絡(luò)中的節(jié)點(diǎn)集有社區(qū)隸屬關(guān)系。
對(duì)于圖3中的網(wǎng)絡(luò),關(guān)鍵在于這些不確定屬于任何社區(qū)的節(jié)點(diǎn)該如何處理。首先使用前面提到的方法形成社區(qū)的初始集合,強(qiáng)行要求所有節(jié)點(diǎn)至少屬于一個(gè)社區(qū)。對(duì)于始終保持未聚類的節(jié)點(diǎn),將其分配到與其連接最多的社區(qū)。如有必要,迭代此過(guò)程,直至沒(méi)有未聚類點(diǎn)。從最大的社區(qū)開(kāi)始作為集合中第一個(gè)元素,隨后社區(qū)被成功地添加到該集合中,在已檢測(cè)到的社區(qū)外建立一個(gè)保護(hù)層,該保護(hù)層和現(xiàn)有保護(hù)層有最低重疊比例。當(dāng)多個(gè)社區(qū)被約束了最低比例,大社區(qū)的優(yōu)先級(jí)將高于小社區(qū)。一直執(zhí)行此過(guò)程,直到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)至少屬于一個(gè)社區(qū)。
采用人工合成網(wǎng)絡(luò)和現(xiàn)實(shí)世界網(wǎng)絡(luò)對(duì)模塊化多尺度檢測(cè)算法的性能進(jìn)行測(cè)試。人工合成網(wǎng)絡(luò)選用LFR基準(zhǔn)測(cè)試,現(xiàn)實(shí)世界網(wǎng)絡(luò)選用中學(xué)朋友圈網(wǎng)絡(luò)[11-12]。使用標(biāo)準(zhǔn)社區(qū)作為檢測(cè)社區(qū)的評(píng)價(jià)依據(jù),采用精度、召回率、F分值來(lái)評(píng)定社區(qū)檢測(cè)算法的有效性。幾項(xiàng)評(píng)價(jià)指標(biāo)由公式(2)到(4)定義。
(2)
(3)
(4)
當(dāng)每個(gè)檢測(cè)到的社區(qū)以最高的F分值和標(biāo)準(zhǔn)社區(qū)配對(duì)時(shí),社區(qū)內(nèi)節(jié)點(diǎn)代表每個(gè)集合的元素,精度和召回率是指平均的精度和召回率。利用這個(gè)度量評(píng)定算法的優(yōu)勢(shì)在于,精度直接反映了選擇的邊緣描述符集的質(zhì)量,召回率反映了選擇的社區(qū)組成和網(wǎng)絡(luò)等級(jí)特性的質(zhì)量。
為了測(cè)量在LFR基準(zhǔn)測(cè)試和中學(xué)朋友圈網(wǎng)絡(luò)中算法的性能,另外計(jì)算了兩個(gè)社區(qū)標(biāo)簽集間的規(guī)范化互信息(NMI)的擴(kuò)展概念[13-14]。受到文獻(xiàn)[12]中用到的性能度量的啟發(fā),這些測(cè)試措施允許本算法和其他大量算法作比較。盡管NMI的擴(kuò)展概念與所謂的標(biāo)準(zhǔn)NMI有稍微差異,但是為便于計(jì)算,在文中也稱這個(gè)擴(kuò)展版本為NMI。NMI分值為1,表示標(biāo)簽間有很好的關(guān)聯(lián);NMI分值為0,表示標(biāo)簽間沒(méi)有關(guān)聯(lián)。
設(shè)計(jì)這種測(cè)試的目的是構(gòu)造內(nèi)置社區(qū)結(jié)構(gòu)的綜合網(wǎng)絡(luò)。LFR網(wǎng)絡(luò)模型中的節(jié)點(diǎn)度不需要全都相同,社區(qū)也可為不同尺寸。在考慮邊的權(quán)重和方向時(shí),有很多常規(guī)的測(cè)試方法可供選擇[15],但是這里注重測(cè)試的擴(kuò)展形式,這種形式允許節(jié)點(diǎn)同屬多個(gè)社區(qū),即重疊節(jié)點(diǎn)。設(shè)已知網(wǎng)絡(luò)中重疊節(jié)點(diǎn)的總數(shù)記為On,重疊社區(qū)個(gè)數(shù)記為Om。
為便于將本算法和文獻(xiàn)[12]中算法結(jié)果作比較,在實(shí)驗(yàn)中采用與之一樣的參數(shù)。節(jié)點(diǎn)度和社區(qū)規(guī)模分別由冪律分布繪制,其中τ1=2,τ2=1,設(shè)每個(gè)節(jié)點(diǎn)的平均度kave=10,設(shè)一個(gè)節(jié)點(diǎn)的最大度kmax=50,剩余的參數(shù)根據(jù)測(cè)試而定。采用的社區(qū)規(guī)模為N∈{1000,5000},社區(qū)規(guī)模在小區(qū)間s=(10,50)和大區(qū)間b=(20,100)之間浮動(dòng)。社區(qū)內(nèi)節(jié)點(diǎn)與其他社區(qū)間的少量連接記為混合參數(shù)μ。最后,為每組參數(shù)值隨機(jī)生成了20個(gè)網(wǎng)絡(luò),計(jì)算其平均性能。
前4組實(shí)驗(yàn)中,設(shè)定重疊社區(qū)的最大個(gè)數(shù)為常數(shù),Om=2。增加社區(qū)間邊密度,參數(shù)μ從0.1以0.05的增量增加到0.3。On設(shè)定為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的10%或50%,N和社區(qū)規(guī)模的參數(shù)值的所有可能組合都測(cè)試一遍。對(duì)于這組測(cè)試,考察了每組社區(qū)的精度、召回率、F分值和NMI的平均值。社區(qū)擴(kuò)展的截止密度通過(guò)自我中心網(wǎng)平均密度進(jìn)行(1-μ)倍增。
經(jīng)測(cè)算,當(dāng)社區(qū)的數(shù)量和規(guī)模增加時(shí),算法的性能也在提高。同時(shí),在低重疊的情況下,算法的F分值也隨著混合參數(shù)值的增加而提高,這里的On等于節(jié)點(diǎn)總數(shù)的10%。這種情況可理解為,當(dāng)增加μ時(shí),社區(qū)內(nèi)的邊緣密度相對(duì)降低了。可以用一個(gè)更低的邊緣密度閾值來(lái)合并連通圖并發(fā)現(xiàn)社區(qū),從而提高召回率。同時(shí),由于On很小,社區(qū)始終保持分散狀態(tài),這時(shí)出鏈的增加對(duì)散亂連通圖的產(chǎn)生無(wú)效。然而,對(duì)于高重疊的情況,發(fā)現(xiàn)增大混合參數(shù)的值將對(duì)召回率僅有微小的效果,但是卻顯著降低了精度。
測(cè)試的后4組中Om從2到8變化,N=5000,μ=0.3,On等于節(jié)點(diǎn)總數(shù)的10%。這組測(cè)試中算法的精度、召回率、F分值、NMI如圖4和圖5所示。結(jié)果表明,相較于其他算法,本算法的精度值更高。
圖4 使用小的社區(qū)規(guī)模范圍時(shí)的算法性能 圖5 使用大的社區(qū)規(guī)模范圍時(shí)的算法性能
圖6 中學(xué)朋友圈網(wǎng)絡(luò)分組情況圖
中學(xué)朋友圈網(wǎng)絡(luò)的數(shù)據(jù)集是青少年到成人健康的國(guó)家縱向研究的一部分。這個(gè)現(xiàn)實(shí)世界網(wǎng)絡(luò)經(jīng)常被用在重疊社區(qū)檢測(cè)算法評(píng)價(jià)中。該網(wǎng)絡(luò)由中學(xué)生組成,學(xué)生間的連接指自發(fā)社交聯(lián)系,網(wǎng)絡(luò)的標(biāo)準(zhǔn)分區(qū)是學(xué)生所屬的年級(jí)(假設(shè)分Grade7到Grade12,如圖6)。盡管本來(lái)是6個(gè)社區(qū),但是9年級(jí)的友誼連接顯示,這個(gè)年級(jí)可以被分成兩個(gè)不同子組,第一組由黑人學(xué)生組成,另一組由白人學(xué)生組成,圖6中清楚地劃分出學(xué)生的分組情況。
通過(guò)考察每個(gè)節(jié)點(diǎn)自我中心網(wǎng)的平均局部邊密度,來(lái)估計(jì)期望的社區(qū)密度,并且把社區(qū)連接密度設(shè)為前者密度的3/4。對(duì)于中學(xué)朋友圈網(wǎng)絡(luò),經(jīng)計(jì)算自我中心網(wǎng)的平均連接密度是67.0%,因此社區(qū)密度閾值設(shè)為50.3%。然后將社區(qū)形成后依然是未聚類的節(jié)點(diǎn),安排它們屬于與之連接最多的社區(qū)。本算法在該網(wǎng)絡(luò)中的表現(xiàn)如表1所示。
表1 本算法在中學(xué)朋友圈網(wǎng)絡(luò)中的表現(xiàn)
算法在緊密連接的幾個(gè)年級(jí)中,精確地檢測(cè)出了9年級(jí)的子劃分,對(duì)朋友圈網(wǎng)絡(luò)的檢測(cè)結(jié)果也是合理的。由幾項(xiàng)量化評(píng)價(jià)指標(biāo)同樣可以看出,算法準(zhǔn)確性還是比較高的。
利用社區(qū)結(jié)構(gòu)的多尺度特征,設(shè)計(jì)了一種重疊社區(qū)檢測(cè)算法。通過(guò)考察節(jié)點(diǎn)尺度、社區(qū)尺度以及網(wǎng)絡(luò)尺度,分別量化每種尺度特征并結(jié)合在一起,建立了高度模塊化的模型??筛鶕?jù)具體社區(qū)檢測(cè)問(wèn)題,對(duì)社區(qū)結(jié)構(gòu)的數(shù)學(xué)模型作適配調(diào)整。LFR基準(zhǔn)測(cè)試顯示算法具有良好的綜合性能。隨著社區(qū)數(shù)量或者社會(huì)規(guī)模的增大,算法的性能也在提高。經(jīng)現(xiàn)實(shí)世界網(wǎng)絡(luò)驗(yàn)證,結(jié)果表明本算法可以較準(zhǔn)確地檢測(cè)重疊社區(qū)。
信陽(yáng)農(nóng)林學(xué)院學(xué)報(bào)2020年2期