基于節(jié)點(diǎn)重要性和局部擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法*

郭 峰 尤凱麗 李昕澤

（北方工業(yè)大學(xué)信息學(xué)院 北京 100000）

1 引言

社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)［1～3］及數(shù)據(jù)挖掘領(lǐng)域中關(guān)鍵的研究?jī)?nèi)容。社區(qū)結(jié)構(gòu)［4～6］作為復(fù)雜網(wǎng)絡(luò)的共同特征，是網(wǎng)絡(luò)圖中最普遍、最重要的屬性之一，表現(xiàn)在社區(qū)內(nèi)部節(jié)點(diǎn)之間的連接要比社區(qū)外其他部分節(jié)點(diǎn)的連接要更加緊密［5］。通過(guò)社區(qū)發(fā)現(xiàn)可以幫助我們了解和分析病毒傳播行為，有助于推斷病毒的傳播機(jī)制，從而快速地采取有效防范、制定應(yīng)對(duì)措施。社區(qū)發(fā)現(xiàn)問(wèn)題具有重要的研究?jī)r(jià)值和科學(xué)意義，近年來(lái)，如何對(duì)社區(qū)結(jié)構(gòu)進(jìn)行快速、準(zhǔn)確地劃分成為眾多學(xué)者研究的熱點(diǎn)。

社區(qū)結(jié)構(gòu)具有一些明顯的屬性和特征［7］，使得在重疊社區(qū)劃分方法上出現(xiàn)不同的優(yōu)秀思想。2002年，Girvan和Newman基于分裂思想提出經(jīng)典的GN算法［8］，為復(fù)雜網(wǎng)絡(luò)研究開(kāi)辟了新的道路；2005年，Palla等對(duì)原有非重疊社區(qū)發(fā)現(xiàn)方法進(jìn)行擴(kuò)展，首次提出基于派系過(guò)濾思想的重疊社區(qū)發(fā)現(xiàn)算法CPM［9］。隨后，各種重疊社區(qū)發(fā)現(xiàn)思想層出不窮，典型算法有圍繞CPM算法中尋找相鄰k階完全子圖的核心思想，F(xiàn)arkas等提出對(duì)加權(quán)網(wǎng)絡(luò)的社區(qū)劃分算法CPMm［10］、Kumpula等提出快速的派系過(guò)濾算法SCP［11］等。2007年Raghavan首次運(yùn)用標(biāo)簽傳播思想對(duì)圖進(jìn)行劃分，提出著名的非重疊社區(qū)發(fā)現(xiàn)算法LPA［12］。其后，在LPA算法基礎(chǔ)上，Steve等引入多標(biāo)簽和隸屬度概念提出重疊社區(qū)發(fā)現(xiàn)算法COPRA［13］；Xie等引入Listener和Speaker概念提出SLPA算法［14］；Xie等結(jié)合派系相似度，以派系為載體進(jìn)行標(biāo)簽傳播，提出CSLPA算法［15］等。

局部擴(kuò)展方法是重疊社區(qū)發(fā)現(xiàn)任務(wù)中比較常用且成功的策略之一。Lancichinetti等提出的LFM算法［16］是局部擴(kuò)展思想中的一個(gè)典型算法，但該算法受參數(shù)影響及初始節(jié)點(diǎn)的隨機(jī)選擇，導(dǎo)致檢測(cè)精度不穩(wěn)定，算法不具有魯棒性。Shen等引入樹(shù)狀圖概念提出EAGLE算法［17］，還提出了一種評(píng)估重疊社區(qū)的模塊化度量EQ；與EAGLE算法思想相同的還有Huang等提出的DenShrik算法［18］和Lee等提出的GCE算法［19］等，但DenShrik與EAGLE類似，需要在檢測(cè)小規(guī)模社區(qū)時(shí)手動(dòng)調(diào)節(jié)閾值，GCE算法對(duì)初始節(jié)點(diǎn)進(jìn)行貪婪擴(kuò)展，并設(shè)計(jì)函數(shù)計(jì)算社區(qū)之間的距離來(lái)刪除相似社區(qū)，但在人工網(wǎng)絡(luò)上的表現(xiàn)效果比在大規(guī)模密集型網(wǎng)絡(luò)上表現(xiàn)效果更好。

如何在復(fù)雜網(wǎng)絡(luò)圖中準(zhǔn)確、快速找出重疊節(jié)點(diǎn)和社區(qū)、有效地劃分社區(qū)結(jié)構(gòu)是本文研究的重點(diǎn)。

2 算法

2.1 DocNet

DOCNet算法［20］是2014年Delel Rhouma等提出的基于局部擴(kuò)展的一種重疊社區(qū)發(fā)現(xiàn)方法。該算法的主要策略是：找到最重要的節(jié)點(diǎn)與其鄰節(jié)點(diǎn)形成一個(gè)初始社區(qū)，篩選達(dá)到規(guī)定質(zhì)量函數(shù)標(biāo)準(zhǔn)的節(jié)點(diǎn)加入初始社區(qū)，遍歷各個(gè)節(jié)點(diǎn)對(duì)初始社區(qū)其進(jìn)行擴(kuò)展。DOCNet算法發(fā)現(xiàn)重疊社區(qū)的過(guò)程可以總結(jié)為兩個(gè)階段，即構(gòu)建初始社區(qū)和社區(qū)擴(kuò)展。

1）構(gòu)建初始社區(qū)

DOCNet算法選取最重要的節(jié)點(diǎn)及其鄰節(jié)點(diǎn)組成初始社區(qū)，節(jié)點(diǎn)重要性隨著其鄰節(jié)點(diǎn)的增加以及這些鄰節(jié)點(diǎn)之間邊數(shù)的增加而增加，也就是說(shuō)，當(dāng)一個(gè)節(jié)點(diǎn)成為網(wǎng)絡(luò)中“有影響力的中心節(jié)點(diǎn)”時(shí)，其重要性就會(huì)增加。節(jié)點(diǎn)重要性是度量一個(gè)節(jié)點(diǎn)是否能夠形成初始社區(qū)C的重要因素。

文中將節(jié)點(diǎn)重要性N I(u)定義為式（1）：

其中cf c(u)代表聚類系數(shù)， ||B(u)代表節(jié)點(diǎn)u的鄰節(jié)點(diǎn)數(shù)。

2）社區(qū)擴(kuò)展

初始社區(qū)形成后，DOCNet算法遍歷社區(qū)相鄰節(jié)點(diǎn)，定義節(jié)點(diǎn)u對(duì)社區(qū)C的隸屬度來(lái)判斷選取哪個(gè)節(jié)點(diǎn)加入到社區(qū)C。隸屬度di st moy定義如式（2）所示：

其中dist(u，v)代表節(jié)點(diǎn)u，v之間的最短距離，即從節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的邊數(shù)。

選取出加入社區(qū)C的候選節(jié)點(diǎn)u后，DOCNet算法通過(guò)定義質(zhì)量函數(shù)來(lái)判定節(jié)點(diǎn)u是否能加入社區(qū)C。質(zhì)量函數(shù)通過(guò)社區(qū)內(nèi)外部聯(lián)系來(lái)限定一個(gè)社區(qū)，當(dāng)加入節(jié)點(diǎn)u后的IC(C)比原來(lái)的IC(C)大時(shí)，則說(shuō)明u可以加入社區(qū)C。計(jì)算方式如式（3）所示：

其中comp(C)是社區(qū)C內(nèi)的邊數(shù)，sep(C)是社區(qū)C內(nèi)節(jié)點(diǎn)與社區(qū)外節(jié)點(diǎn)相連的邊數(shù)。

DOCNet算法過(guò)程簡(jiǎn)單，在復(fù)雜網(wǎng)絡(luò)以及社區(qū)之間的重疊率高的網(wǎng)絡(luò)上有著很高的穩(wěn)定性，但仍存在一定的局限性，本文提出DOCLLE（Discover Overlapping Communities by LeaderRank and Local Expansion）算法，在節(jié)點(diǎn)重要性和隸屬度兩個(gè)方面對(duì)其進(jìn)行改進(jìn)。

2.2 DOCLLE

初始節(jié)點(diǎn)的選取是局部擴(kuò)展方法中關(guān)鍵的第一步，對(duì)最終的社區(qū)劃分結(jié)果影響很大［21～22］。針對(duì)節(jié)點(diǎn)重要性的計(jì)算，本文采用更優(yōu)的排序算法LeaderRank對(duì)圖中各節(jié)點(diǎn)進(jìn)行排序。在擴(kuò)展過(guò)程中，DOCNet算法采用平均距離來(lái)計(jì)算節(jié)點(diǎn)歸屬度，使得算法運(yùn)行時(shí)間變長(zhǎng)，本文結(jié)合節(jié)點(diǎn)間相似度概念，在局部范圍計(jì)算節(jié)點(diǎn)對(duì)社區(qū)的隸屬度，減小了計(jì)算范圍，并具有一定的準(zhǔn)確性。

2.2.1 節(jié)點(diǎn)重要性

LeaderRank重要性排名算法是對(duì)PageRank算法的擴(kuò)展，該算法加入延遲及自適應(yīng)概率等思想有效地解決了PageRank算法中每個(gè)節(jié)點(diǎn)的隨機(jī)跳轉(zhuǎn)概率都相同且最優(yōu)參數(shù)不具有普適性的問(wèn)題，在標(biāo)識(shí)圖中節(jié)點(diǎn)重要性上有很好的性能。

圖1 Zachary空手道數(shù)據(jù)集各節(jié)點(diǎn)重要性

在有向圖和無(wú)向圖上應(yīng)用LeaderRank算法后發(fā)現(xiàn)，該算法在兩種類型的圖上均具有良好的性能，圖1所示為L(zhǎng)eaderRank算法在無(wú)向網(wǎng)絡(luò)圖Zachary空手道俱樂(lè)部人員關(guān)系圖上對(duì)各個(gè)節(jié)點(diǎn)的重要性排序結(jié)果。

2.2.2 隸屬度

DOCNet算法采用節(jié)點(diǎn)到社區(qū)各點(diǎn)的平均距離值來(lái)衡量節(jié)點(diǎn)對(duì)該社區(qū)的歸屬度，算法運(yùn)算過(guò)程需要計(jì)算兩個(gè)節(jié)點(diǎn)間的最短距離，處理節(jié)點(diǎn)數(shù)較多的網(wǎng)絡(luò)圖時(shí)所需時(shí)間較長(zhǎng)。文中所提DOCLLE算法采用局部范圍內(nèi)計(jì)算節(jié)點(diǎn)間的相似度的方式來(lái)衡量節(jié)點(diǎn)對(duì)社區(qū)的隸屬度，不需要遍歷全局節(jié)點(diǎn)，提高了運(yùn)算效率。杰卡德（Jaccard）系數(shù)是衡量?jī)蓚€(gè)集合之間相似度的指標(biāo)，常用于比較有限樣本集之間的相似性與差異性。集合A、B的交集在兩個(gè)集合的并集中所占的比例即為杰卡德系數(shù)，如式（4）所示，Jaccard系數(shù)值越大，樣本相似度越高。

節(jié)點(diǎn)間相似度可以用杰卡德相似度系數(shù)來(lái)衡量，為適應(yīng)圖中節(jié)點(diǎn)特征，對(duì)杰卡德系數(shù)進(jìn)行更改，更改后的杰卡德節(jié)點(diǎn)相似度Si m(i)，j如式（5）所示：

節(jié)點(diǎn)對(duì)社區(qū)的隸屬度大小與該節(jié)點(diǎn)與社區(qū)內(nèi)部各節(jié)點(diǎn)之間的關(guān)聯(lián)程度有關(guān)。DOCLLE算法在候選節(jié)點(diǎn)集中選擇加入社區(qū)中的節(jié)點(diǎn)時(shí)，定義了如式（6）中所示的節(jié)點(diǎn)隸屬度Bl(u，C)：

其中C為每次迭代過(guò)程中的初始社區(qū)集合，P是C的邊界鄰節(jié)點(diǎn)集合，ω、φ分別是C和P中的節(jié)點(diǎn)，e uω為節(jié)點(diǎn)u與社區(qū)C中節(jié)點(diǎn)的連邊數(shù)，e uφ為節(jié)點(diǎn)u與社區(qū)P中連邊數(shù)。

2.3 算法描述

基于局部擴(kuò)展的核心思想，文中有效地改善了DocNet算法的局限之處。算法主要分為三個(gè)步驟：1）通過(guò)LeaderRank算法獲取圖中所有節(jié)點(diǎn)的重要性并用LR表示，將LR按重要性大小降序排列并選擇第一個(gè)節(jié)點(diǎn)作為初始節(jié)點(diǎn)，與其鄰節(jié)點(diǎn)共同構(gòu)成初始社區(qū)C；2）對(duì)LR進(jìn)行遍歷，通過(guò)式（6）依次計(jì)算C的邊界鄰節(jié)點(diǎn)對(duì)C的隸屬度大小，用Bldegree表示，在Bldegree中依次選擇隸屬度最大的節(jié)點(diǎn)加入初始社區(qū)C；3）通過(guò)式（3）定義的質(zhì)量函數(shù)計(jì)算加入新節(jié)點(diǎn)后的社區(qū)質(zhì)量，衡量該節(jié)點(diǎn)是否可以加入初始社區(qū)中；LR中節(jié)點(diǎn)全部遍歷后，算法終止。

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

3.1 人工生成網(wǎng)絡(luò)評(píng)估

LFR人工生成基準(zhǔn)網(wǎng)絡(luò)能夠生成給定參數(shù)的網(wǎng)絡(luò)圖，其中混合參數(shù)μ代表了每個(gè)節(jié)點(diǎn)到其社區(qū)外部節(jié)點(diǎn)之間的連邊比例，μ值越大，合成網(wǎng)絡(luò)中的社區(qū)間邊數(shù)越多，社區(qū)內(nèi)的邊數(shù)較少，從而使社區(qū)結(jié)構(gòu)更難檢測(cè)。其他參數(shù)設(shè)置如表1所示。

表1 人工生成網(wǎng)絡(luò)參數(shù)設(shè)置

人工生成網(wǎng)絡(luò)benchmark根據(jù)設(shè)定的參數(shù)生成相應(yīng)的網(wǎng)絡(luò)圖，社區(qū)個(gè)數(shù)是已知的，這里采用標(biāo)準(zhǔn)化互信息NMI（Normalized Mutual Information）［23］對(duì)算法進(jìn)行檢驗(yàn)。NMI的取值范圍為0～1，值越大，說(shuō)明社區(qū)發(fā)現(xiàn)結(jié)果越準(zhǔn)確。將DOCLLE與DOCNet算法在以上各組人工生成網(wǎng)絡(luò)圖上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2所示。

人工生成網(wǎng)絡(luò)參數(shù)的組合設(shè)置使得各組網(wǎng)絡(luò)圖規(guī)模、復(fù)雜度都有所區(qū)分，從圖2中可以看出，在網(wǎng)絡(luò)圖節(jié)點(diǎn)數(shù)達(dá)到5000時(shí)，DocNet算法的NMI值呈下降趨勢(shì)，在第7，8，9組實(shí)驗(yàn)的網(wǎng)絡(luò)圖中的社區(qū)劃分結(jié)果并不好，而DOCLLE算法則呈上升趨勢(shì)，社區(qū)劃分能力比較穩(wěn)定，能夠在節(jié)點(diǎn)較多的網(wǎng)絡(luò)中表現(xiàn)出很好的重疊社區(qū)發(fā)現(xiàn)效果。

圖2 DocNet與DOCLLE在人工網(wǎng)絡(luò)下NMI值對(duì)比

圖3 DocNet與DOCLLE在GN網(wǎng)絡(luò)中不同μ值下NMI值對(duì)比

為進(jìn)一步檢驗(yàn)DOCLLE算法，另外選擇在GN基準(zhǔn)網(wǎng)絡(luò)在不同μ值下的網(wǎng)絡(luò)圖上進(jìn)行實(shí)驗(yàn)，從圖3中可看出，μ值大小對(duì)算法檢測(cè)到的社區(qū)劃分質(zhì)量有很大的影響。隨著μ值增加，NMI減小，這意味在同等節(jié)點(diǎn)數(shù)的網(wǎng)絡(luò)規(guī)模下，隨著網(wǎng)絡(luò)變得更加復(fù)雜，算法計(jì)算出的劃分結(jié)果與真實(shí)社區(qū)劃分情況相差更遠(yuǎn)。雖然如此，DOCLLE算法在復(fù)雜的網(wǎng)絡(luò)上表現(xiàn)出了比DocNet算法更好的重疊社區(qū)劃分性能，劃分結(jié)果更加準(zhǔn)確。

3.2 真實(shí)網(wǎng)絡(luò)評(píng)估

為檢驗(yàn)在真實(shí)的重疊網(wǎng)絡(luò)上DOCLLE算法的效果，文中在Zachary、Dolphins、Footbal、Netscience四個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其社區(qū)規(guī)模是增大的，Netscience中1589個(gè)節(jié)點(diǎn)，2742條邊。圖4展示了DOCLLE算法在Zachary數(shù)據(jù)集上的社區(qū)劃分情況，圖中的節(jié)點(diǎn)表示俱樂(lè)部成員，圖中的邊表示兩個(gè)成員之間有關(guān)聯(lián)。算法能夠識(shí)別出重疊節(jié)點(diǎn)，將該社團(tuán)分為兩個(gè)社區(qū)，各包含21個(gè)節(jié)點(diǎn)，其中綠色節(jié)點(diǎn)為兩個(gè)社區(qū)間的重疊節(jié)點(diǎn)，以其為邊界將Zachary社區(qū)結(jié)構(gòu)進(jìn)行了明確的劃分。

圖4 DOCLLE在Zachary上的社區(qū)劃分結(jié)果

對(duì)真實(shí)網(wǎng)絡(luò)來(lái)說(shuō)，社區(qū)個(gè)數(shù)是未知的，采用以下比較適合衡量社區(qū)結(jié)構(gòu)［23］的評(píng)價(jià)系數(shù)：社區(qū)連接緊密度指標(biāo)EQ［17］和模塊化指標(biāo)Qov［24］對(duì)算法進(jìn)行檢驗(yàn)。評(píng)價(jià)系數(shù)的取值范圍均為（0～1），值越大說(shuō)明算法效果越好。

將文中提出的DOCLLE算法與局部擴(kuò)展經(jīng)典算法LFM［16］、DEMON［25］、標(biāo)簽傳播算法SLPA［14］以及DocNet［20］算法進(jìn)行對(duì)比，并在上述四個(gè)真實(shí)數(shù)據(jù)集上做對(duì)比實(shí)驗(yàn)。從圖5和圖6中可看出，DocNet算法在不同數(shù)據(jù)集上均有比較好表現(xiàn)，但在規(guī)模較大的Netscience數(shù)據(jù)集上，Qov分值較DOCLLE來(lái)說(shuō)相對(duì)較低；DOCLLE算法在不同數(shù)據(jù)集上均有比較好的表現(xiàn)，尤其在Netscience數(shù)據(jù)集上，相較于LFM、SLPA、Demon算法來(lái)說(shuō)，DOCLLE算法的EQ值、Qov值是最高的，這意味著隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增多，DOCLLE算法的社區(qū)劃分能力在逐步增強(qiáng)。

圖5 各數(shù)據(jù)集上各個(gè)算法的EQ值

圖6 各數(shù)據(jù)集上各個(gè)算法的Qov值

3.3 算法時(shí)間復(fù)雜度

假設(shè)圖中的節(jié)點(diǎn)數(shù)為n，邊數(shù)為m，平均社區(qū)規(guī)模為c，平均節(jié)點(diǎn)度數(shù)為d。算法在計(jì)算節(jié)點(diǎn)重要性的過(guò)程中，由于LeaderRank算法迭代次數(shù)多，運(yùn)行時(shí)間過(guò)長(zhǎng)，導(dǎo)致算法復(fù)雜度較高。實(shí)驗(yàn)中，在保證結(jié)果正確的前提下，通過(guò)調(diào)整終止條件的參數(shù)來(lái)降低迭代次數(shù)，同時(shí)對(duì)代碼進(jìn)行優(yōu)化，這里設(shè)結(jié)果穩(wěn)定時(shí)所需的迭代次數(shù)為s，優(yōu)化后的LeaderRank算法時(shí)間復(fù)雜度為O（ms）；計(jì)算質(zhì)量函數(shù)的時(shí)間復(fù)雜度為O（cd）；計(jì)算隸屬度的時(shí)間復(fù)雜度為O（n2），DOCLLE算法整體的時(shí)間復(fù)雜度為O（n2cd）。

4 結(jié)語(yǔ)

本文在局部擴(kuò)展算法DocNet的基礎(chǔ)上，在初始節(jié)點(diǎn)選取和隸屬度兩個(gè)方面做了改進(jìn)，通過(guò)引入經(jīng)典的重要性排序算法LeaderRank對(duì)節(jié)點(diǎn)重要性進(jìn)行排序，得到初始的核心節(jié)點(diǎn)；采用局部相似度的計(jì)算方式替代DocNet中的平均距離計(jì)算方式，以期在處理節(jié)點(diǎn)較多的網(wǎng)絡(luò)時(shí)減小計(jì)算范圍，提高算法效率。實(shí)驗(yàn)結(jié)果表明，在節(jié)點(diǎn)多的網(wǎng)絡(luò)圖上，DOCLLE算法有更好的表現(xiàn)，能夠以較高的效率發(fā)現(xiàn)重疊社區(qū)。在未來(lái)工作中，需在真實(shí)場(chǎng)景中將算法進(jìn)行應(yīng)用和進(jìn)一步的改進(jìn)，使算法在處理這些網(wǎng)絡(luò)圖時(shí)更具有準(zhǔn)確性和普適性。