蔣智恩

(福建信息職業(yè)技術(shù)學(xué)院 商貿(mào)管理系，福建 福州 350003)

一般認(rèn)為，社區(qū)是一些連接更為緊密的節(jié)點(diǎn)集合?，F(xiàn)實(shí)世界中許多網(wǎng)絡(luò)都具有社區(qū)特性，比如通信網(wǎng)絡(luò)、社會網(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)功能，對其進(jìn)行社區(qū)檢測很有必要。

實(shí)際網(wǎng)絡(luò)中更為常見的是社區(qū)重疊的情況，即一個(gè)節(jié)點(diǎn)同時(shí)被多個(gè)社區(qū)共享。近年來學(xué)者們提出一系列相應(yīng)的啟發(fā)式算法。Palla提出了CPM算法[1]，算法認(rèn)為一個(gè)社區(qū)內(nèi)節(jié)點(diǎn)間的邊可形成全聯(lián)通圖(clique)，通過相互連通的k-團(tuán)來發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。Lancichinetti[2]提出了LFM算法，該算法的基本思想是通過目標(biāo)函數(shù)的直方圖峰值區(qū)分社區(qū)。Steve等人[3]在GN算法的基礎(chǔ)上提出了CONGA算法，該算法將部分節(jié)點(diǎn)分裂成多個(gè)子節(jié)點(diǎn)，之后利用GN算法來處理，但其時(shí)間復(fù)雜度很高?；诰仃囈蚴椒纸獾姆椒ㄒ部捎糜谥丿B社區(qū)檢測，并擴(kuò)展出很多新算法，例如Psorakis等[4]和Wang等[5]提出的NMF算法，但是NMF所涉及的數(shù)據(jù)矩陣通常存在缺失值。目前關(guān)于社區(qū)結(jié)構(gòu)的多尺度特征研究還很少，陳東等[6]基于結(jié)構(gòu)相似度提出了多尺度局部社區(qū)發(fā)現(xiàn)算法，引入尺度分子來定義結(jié)構(gòu)模塊度，在局部社區(qū)檢測中得到了良好的效果。郭玉泉等[7]則將譜分析與啟發(fā)式遺傳算法相結(jié)合，提出多尺度社區(qū)檢測算法HGASA。

基于以上研究，嘗試提出一種模塊化多尺度通信重疊社區(qū)檢測算法，從單個(gè)節(jié)點(diǎn)、單個(gè)社區(qū)以及整個(gè)網(wǎng)絡(luò)的尺度上，量化各種尺度下社區(qū)結(jié)構(gòu)特征，合并在一起組成算法內(nèi)容。最后通過實(shí)驗(yàn)驗(yàn)證不同尺度下各類參數(shù)對檢測效果的影響，并在現(xiàn)實(shí)世界網(wǎng)絡(luò)中檢驗(yàn)算法有效性和準(zhǔn)確性。

1 模塊化多尺度算法

為了完整描述社區(qū)特性，需要解決社區(qū)定義的多尺度問題：單個(gè)節(jié)點(diǎn)的尺度、單個(gè)社區(qū)的尺度、整個(gè)網(wǎng)絡(luò)的尺度。算法功能：針對社會網(wǎng)絡(luò)中社區(qū)重疊問題，嘗試從尺度特征出發(fā)提出合理的解決方法。對于一個(gè)給定的待檢社區(qū)，根據(jù)每種尺度的社區(qū)結(jié)構(gòu)調(diào)整具體的量化模塊，因此，提出的方法是高度模塊化的。這種方法為探索社區(qū)檢測算法提供了一種新思路，符合目標(biāo)社區(qū)檢測要求。多尺度社區(qū)結(jié)構(gòu)反映了在傳播過程中的網(wǎng)絡(luò)動力學(xué)特征，可以有效地揭示出網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

輸入：網(wǎng)絡(luò)的鄰接矩陣

算法：

③ 如果社區(qū)中有節(jié)點(diǎn)未被聚類，將它們添加到與他們連接最頻繁的社區(qū)。成本：可忽略；

④ 剔除檢測出的更小的社區(qū)，規(guī)定所有的節(jié)點(diǎn)至少屬于一個(gè)社區(qū)，描述方法見1.3節(jié)。

輸出：網(wǎng)絡(luò)中節(jié)點(diǎn)集組成的社區(qū)。

1.1 社區(qū)結(jié)構(gòu)的節(jié)點(diǎn)尺度特征

由于算法的出發(fā)點(diǎn)是從邊的排列中識別社區(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ū)的可能性就更大，這說明同一社區(qū)內(nèi)節(jié)點(diǎn)間的邊連接更加密集。因此，一個(gè)由邊集合組成的連通圖可看作是一種邊聚類的原型。同時(shí)，當(dāng)一個(gè)節(jié)點(diǎn)屬于幾個(gè)相對較大且不相交的連通圖時(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)小尺度特征的一組編碼。

1.2 社區(qū)結(jié)構(gòu)的社區(qū)尺度特征

邊緣描述符集被提取出來后，需要一種集中現(xiàn)有局部特征共同形成社區(qū)的方式。為此，使用和社區(qū)尺度相關(guān)的量化特征來聚類這些邊集。

圖2 黑色社區(qū)、灰色社區(qū)的分布

一個(gè)待檢測社區(qū)擁有的總體量化特征，就是它們具有比整個(gè)網(wǎng)絡(luò)更高的邊密度，這一特點(diǎn)也可以在單個(gè)節(jié)點(diǎn)的邊緣描述符集上清楚地顯現(xiàn)出來。網(wǎng)絡(luò)示例如圖2中所示。對于黑色和灰色社區(qū)，需要將黑邊集合及灰邊集合與白邊集合區(qū)分開。從社區(qū)的角度看，目的就是尋找形成社區(qū)的邊緣描述符集的集合。

為解釋聚集邊緣描述符集形成社區(qū)這種特性，采用了連接密度的說法。令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)尺度；閾值密度更低的對應(yīng)于更稀疏的社區(qū)，閾值密度更高的對應(yīng)更緊密的社區(qū)。

采取貪心算法擴(kuò)展社區(qū)，如果它們將ρ降低到最小限度，但仍保持在給定的閾值以上，新的節(jié)點(diǎn)將被吸收到社區(qū)中，并連帶產(chǎn)生新的邊緣描述符集。從數(shù)學(xué)角度看，這不是最佳優(yōu)化方法，但它保留了社區(qū)的直觀形成過程，展示了社會網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)在各個(gè)角度的擴(kuò)張過程，這和文獻(xiàn)[8]中邊緣描述符集的滲流法相似，也可看作是文獻(xiàn)[9][10]的變體。社區(qū)擴(kuò)展算法描述如下：

輸入：網(wǎng)絡(luò)中已經(jīng)檢測到的所有邊緣描述符集

算法：

① 從最大的未聚類的邊緣描述符集開始，以此作為社區(qū)基礎(chǔ)；

② 為將形成的社區(qū)找到使入鏈密度降低到最低限度的邊緣描述符集；

③ 如果入鏈密度保持在用戶提供的密度閾值以上，添加邊緣描述符到將要形成的社區(qū)中；

④ 重復(fù)步驟②和步驟③直到?jīng)]有邊緣描述符集滿足密度約束條件；

⑤ 重復(fù)步驟①直到?jīng)]有邊緣描述符集保持未聚類。

輸出：社區(qū)的初始集。

1.3 社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)尺度特性

圖3 社區(qū)網(wǎng)絡(luò)節(jié)點(diǎn)聚類示意圖

為最終實(shí)現(xiàn)網(wǎng)絡(luò)中沒有剩余的未聚類的節(jié)點(diǎn)，且社區(qū)個(gè)數(shù)為最少，還須挖掘出整個(gè)網(wǎng)絡(luò)層面上的社區(qū)特性。這里采用常規(guī)啟發(fā)式方法，保證了網(wǎng)絡(luò)中的節(jié)點(diǎn)集有社區(qū)隸屬關(guān)系。

對于圖3中的網(wǎng)絡(luò)，關(guān)鍵在于這些不確定屬于任何社區(qū)的節(jié)點(diǎn)該如何處理。首先使用前面提到的方法形成社區(qū)的初始集合，強(qiáng)行要求所有節(jié)點(diǎn)至少屬于一個(gè)社區(qū)。對于始終保持未聚類的節(jié)點(diǎn)，將其分配到與其連接最多的社區(qū)。如有必要，迭代此過程，直至沒有未聚類點(diǎn)。從最大的社區(qū)開始作為集合中第一個(gè)元素，隨后社區(qū)被成功地添加到該集合中，在已檢測到的社區(qū)外建立一個(gè)保護(hù)層，該保護(hù)層和現(xiàn)有保護(hù)層有最低重疊比例。當(dāng)多個(gè)社區(qū)被約束了最低比例，大社區(qū)的優(yōu)先級將高于小社區(qū)。一直執(zhí)行此過程，直到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)至少屬于一個(gè)社區(qū)。

2 實(shí)驗(yàn)結(jié)果與分析

采用人工合成網(wǎng)絡(luò)和現(xiàn)實(shí)世界網(wǎng)絡(luò)對模塊化多尺度檢測算法的性能進(jìn)行測試。人工合成網(wǎng)絡(luò)選用LFR基準(zhǔn)測試，現(xiàn)實(shí)世界網(wǎng)絡(luò)選用中學(xué)朋友圈網(wǎng)絡(luò)[11-12]。使用標(biāo)準(zhǔn)社區(qū)作為檢測社區(qū)的評價(jià)依據(jù)，采用精度、召回率、F分值來評定社區(qū)檢測算法的有效性。幾項(xiàng)評價(jià)指標(biāo)由公式(2)到(4)定義。

(2)

(3)

(4)

當(dāng)每個(gè)檢測到的社區(qū)以最高的F分值和標(biāo)準(zhǔn)社區(qū)配對時(shí)，社區(qū)內(nèi)節(jié)點(diǎn)代表每個(gè)集合的元素，精度和召回率是指平均的精度和召回率。利用這個(gè)度量評定算法的優(yōu)勢在于，精度直接反映了選擇的邊緣描述符集的質(zhì)量，召回率反映了選擇的社區(qū)組成和網(wǎng)絡(luò)等級特性的質(zhì)量。

為了測量在LFR基準(zhǔn)測試和中學(xué)朋友圈網(wǎng)絡(luò)中算法的性能，另外計(jì)算了兩個(gè)社區(qū)標(biāo)簽集間的規(guī)范化互信息(NMI)的擴(kuò)展概念[13-14]。受到文獻(xiàn)[12]中用到的性能度量的啟發(fā)，這些測試措施允許本算法和其他大量算法作比較。盡管NMI的擴(kuò)展概念與所謂的標(biāo)準(zhǔn)NMI有稍微差異，但是為便于計(jì)算，在文中也稱這個(gè)擴(kuò)展版本為NMI。NMI分值為1，表示標(biāo)簽間有很好的關(guān)聯(lián)；NMI分值為0，表示標(biāo)簽間沒有關(guān)聯(lián)。

2.1 LFR基準(zhǔn)測試

設(shè)計(jì)這種測試的目的是構(gòu)造內(nèi)置社區(qū)結(jié)構(gòu)的綜合網(wǎng)絡(luò)。LFR網(wǎng)絡(luò)模型中的節(jié)點(diǎn)度不需要全都相同，社區(qū)也可為不同尺寸。在考慮邊的權(quán)重和方向時(shí)，有很多常規(guī)的測試方法可供選擇[15]，但是這里注重測試的擴(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ù)測試而定。采用的社區(qū)規(guī)模為N∈{1000,5000}，社區(qū)規(guī)模在小區(qū)間s=(10,50)和大區(qū)間b=(20,100)之間浮動。社區(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ù)值的所有可能組合都測試一遍。對于這組測試，考察了每組社區(qū)的精度、召回率、F分值和NMI的平均值。社區(qū)擴(kuò)展的截止密度通過自我中心網(wǎng)平均密度進(jìn)行(1-μ)倍增。

經(jīng)測算，當(dāng)社區(qū)的數(shù)量和規(guī)模增加時(shí)，算法的性能也在提高。同時(shí)，在低重疊的情況下，算法的F分值也隨著混合參數(shù)值的增加而提高，這里的On等于節(jié)點(diǎn)總數(shù)的10%。這種情況可理解為，當(dāng)增加μ時(shí)，社區(qū)內(nèi)的邊緣密度相對降低了?？梢杂靡粋€(gè)更低的邊緣密度閾值來合并連通圖并發(fā)現(xiàn)社區(qū)，從而提高召回率。同時(shí)，由于On很小，社區(qū)始終保持分散狀態(tài)，這時(shí)出鏈的增加對散亂連通圖的產(chǎn)生無效。然而，對于高重疊的情況，發(fā)現(xiàn)增大混合參數(shù)的值將對召回率僅有微小的效果，但是卻顯著降低了精度。

測試的后4組中Om從2到8變化，N=5000，μ=0.3，On等于節(jié)點(diǎn)總數(shù)的10%。這組測試中算法的精度、召回率、F分值、NMI如圖4和圖5所示。結(jié)果表明，相較于其他算法，本算法的精度值更高。

圖4 使用小的社區(qū)規(guī)模范圍時(shí)的算法性能 圖5 使用大的社區(qū)規(guī)模范圍時(shí)的算法性能

2.2 中學(xué)朋友圈網(wǎng)絡(luò)

圖6 中學(xué)朋友圈網(wǎng)絡(luò)分組情況圖

中學(xué)朋友圈網(wǎng)絡(luò)的數(shù)據(jù)集是青少年到成人健康的國家縱向研究的一部分。這個(gè)現(xiàn)實(shí)世界網(wǎng)絡(luò)經(jīng)常被用在重疊社區(qū)檢測算法評價(jià)中。該網(wǎng)絡(luò)由中學(xué)生組成，學(xué)生間的連接指自發(fā)社交聯(lián)系，網(wǎng)絡(luò)的標(biāo)準(zhǔn)分區(qū)是學(xué)生所屬的年級(假設(shè)分Grade7到Grade12，如圖6)。盡管本來是6個(gè)社區(qū)，但是9年級的友誼連接顯示，這個(gè)年級可以被分成兩個(gè)不同子組，第一組由黑人學(xué)生組成，另一組由白人學(xué)生組成，圖6中清楚地劃分出學(xué)生的分組情況。

通過考察每個(gè)節(jié)點(diǎn)自我中心網(wǎng)的平均局部邊密度，來估計(jì)期望的社區(qū)密度，并且把社區(qū)連接密度設(shè)為前者密度的3/4。對于中學(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è)年級中，精確地檢測出了9年級的子劃分，對朋友圈網(wǎng)絡(luò)的檢測結(jié)果也是合理的。由幾項(xiàng)量化評價(jià)指標(biāo)同樣可以看出，算法準(zhǔn)確性還是比較高的。

3 結(jié)語

利用社區(qū)結(jié)構(gòu)的多尺度特征，設(shè)計(jì)了一種重疊社區(qū)檢測算法。通過考察節(jié)點(diǎn)尺度、社區(qū)尺度以及網(wǎng)絡(luò)尺度，分別量化每種尺度特征并結(jié)合在一起，建立了高度模塊化的模型。可根據(jù)具體社區(qū)檢測問題，對社區(qū)結(jié)構(gòu)的數(shù)學(xué)模型作適配調(diào)整。LFR基準(zhǔn)測試顯示算法具有良好的綜合性能。隨著社區(qū)數(shù)量或者社會規(guī)模的增大，算法的性能也在提高。經(jīng)現(xiàn)實(shí)世界網(wǎng)絡(luò)驗(yàn)證，結(jié)果表明本算法可以較準(zhǔn)確地檢測重疊社區(qū)。