融合標(biāo)簽預(yù)處理與節(jié)點(diǎn)影響力的重疊社區(qū)發(fā)現(xiàn)算法

吳清壽，陳榮旺，余文森*，劉耿耿

（1.武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建武夷山 354300；2.認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室（武夷學(xué)院），福建武夷山 354300；3.福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350116）

（?通信作者電子郵箱45509111@qq.com）

0 引言

自然界和社會(huì)生活中廣泛存在各種網(wǎng)絡(luò)，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)和語(yǔ)言學(xué)網(wǎng)絡(luò)等，通常將其統(tǒng)稱為復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)會(huì)依據(jù)內(nèi)在規(guī)律形成緊密或稀疏的關(guān)系，進(jìn)而形成社區(qū)［1］。大量研究表明，處于同一社區(qū)中的節(jié)點(diǎn)之間的關(guān)系比不同社區(qū)節(jié)點(diǎn)之間的關(guān)系更加緊密，即社區(qū)內(nèi)節(jié)點(diǎn)的連邊稠密，而社區(qū)之間的連邊稀疏。社區(qū)發(fā)現(xiàn)算法研究是復(fù)雜網(wǎng)絡(luò)中其他研究的重要基礎(chǔ)工作之一，并已在社會(huì)學(xué)、物理學(xué)、流行病學(xué)、文獻(xiàn)計(jì)量學(xué)等領(lǐng)域中得到了廣泛應(yīng)用［2-3］。

早期研究認(rèn)為每個(gè)節(jié)點(diǎn)歸屬于一個(gè)社區(qū)，但真實(shí)世界網(wǎng)絡(luò)中，部分節(jié)點(diǎn)可能歸屬于多個(gè)社區(qū)，如一位科學(xué)家的研究?jī)?nèi)容可能歸屬于多個(gè)領(lǐng)域，這就構(gòu)成了社區(qū)重疊。Palla 等［4］于2005 年提出社區(qū)重疊概念，并給出了識(shí)別重疊社區(qū)的CPM（Clique Percolation Method），其基本思想是社區(qū)內(nèi)部可能存在完全圖，而社區(qū)之間的邊不會(huì)構(gòu)成完全子圖。CPM 適用于稠密網(wǎng)絡(luò)，而大部分社交網(wǎng)絡(luò)是稀疏的。Zhang等［5］針對(duì)CPM的問(wèn)題提出了表征弱派系相似度的方法weak-CPM，其時(shí)間復(fù)雜度降低為O（dm），d為節(jié)點(diǎn)平均度數(shù)，m為邊數(shù)。另外一類常用的方法是非負(fù)矩陣分解方法，Zarei等［6］提出的貝葉斯非負(fù)矩陣分解算法依賴于節(jié)點(diǎn)的中心性矩陣和社區(qū)度矩陣，并將社區(qū)度作為切割標(biāo)準(zhǔn)，可用于識(shí)別重疊社區(qū)和異常點(diǎn)。Cao等［7］提出了一種依賴于貝葉斯優(yōu)化過(guò)程的混合優(yōu)化算法。Zhang等［8］提出了一種基于偏好的概率非負(fù)矩陣分解（Probability Nonnegative Matrix Factorization，PNMF）模型，最大化每個(gè)節(jié)點(diǎn)成對(duì)偏好順序的可能性，采用隨機(jī)梯度下降引導(dǎo)采樣解決優(yōu)化問(wèn)題。胡麗瑩等［9］提出一種新的對(duì)稱非負(fù)矩陣分解算法，并用文獻(xiàn)［7］的方法進(jìn)行重疊社區(qū)劃分。最新的研究中，Shahmoradi等［10］提出多層次重疊社區(qū)的發(fā)現(xiàn)方法，通過(guò)建立模型，采用遺傳算法得到初步解，再進(jìn)行優(yōu)化選擇以得到社區(qū)。

與本文研究相關(guān)的方法有兩類：一類是基于種子擴(kuò)展的方法。Lancichinetti 等［11］提出的LFM（Local Fitness Method）以隨機(jī)節(jié)點(diǎn)作為種子節(jié)點(diǎn)，以最大化自適應(yīng)函數(shù)值為目標(biāo)進(jìn)行局部擴(kuò)展優(yōu)化，可檢測(cè)層次和重疊社區(qū)，但其時(shí)間復(fù)雜度達(dá)到O（n2），且種子節(jié)點(diǎn)的選擇未考慮節(jié)點(diǎn)的重要性，算法的穩(wěn)定性和適應(yīng)性較差。杜航原等［12］通過(guò)搜索局部密度中心作為社區(qū)中心，提升了社區(qū)中心的發(fā)現(xiàn)效率。另一類方法是基于標(biāo)簽傳播算法（Label Propagation Algorithm，LPA）［13］思想改進(jìn)的重疊社區(qū)發(fā)現(xiàn)方法，代表性的算法有Coscia 等［14］提出的

DEMON（Democratic Estimate of the Modular Organization of a Network），Gregory［15］提出的COPRA（Community Overlap PRopagation Algorithm），以及Xie 等［16］提出的SLPA（Speaker listener Label Propagation Algorithm）等。DEMON 算法提取每個(gè)節(jié)點(diǎn)的自我網(wǎng)絡(luò)（ego），并在這個(gè)結(jié)構(gòu)上應(yīng)用LPA，再將這些局部社區(qū)進(jìn)行合并，可在全局級(jí)別揭示網(wǎng)絡(luò)的模塊化組織，但該算法存在穩(wěn)定性差的問(wèn)題。COPRA 通過(guò)引入歸屬系數(shù)，將標(biāo)簽傳播方法應(yīng)用到重疊社區(qū)發(fā)現(xiàn)，其在各類網(wǎng)絡(luò)上具有較好的適應(yīng)性，但COPRA 中標(biāo)簽選擇過(guò)程隨機(jī)性較大，當(dāng)社區(qū)間混合度較大時(shí)容易把整個(gè)網(wǎng)絡(luò)識(shí)別為一個(gè)社區(qū)。馬健等［17］對(duì)COPRA 中的節(jié)點(diǎn)標(biāo)簽更新順序和傳播門限進(jìn)行了改進(jìn)，提出了COPRAPC（Community Overlap PRopagation Algorithm based on PageRank and Clustering coefficient），選擇影響力小的節(jié)點(diǎn)優(yōu)先進(jìn)行標(biāo)簽傳播，并用節(jié)點(diǎn)聚類系數(shù)控制節(jié)點(diǎn)歸屬的最大社區(qū)數(shù)。SLPA 根據(jù)動(dòng)態(tài)交互規(guī)則進(jìn)行標(biāo)簽交換，該算法在高混合度網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)的能力較弱。

結(jié)合種子擴(kuò)展和標(biāo)簽傳播的思想，本文提出了一種融合標(biāo)簽預(yù)處理與節(jié)點(diǎn)影響力（Fusing Label Preprocessing and Node Influence，F(xiàn)LPNI）的重疊社區(qū)發(fā)現(xiàn)算法，通過(guò)發(fā)現(xiàn)中心節(jié)點(diǎn)，進(jìn)行標(biāo)簽預(yù)處理，使得具有緊密關(guān)系的節(jié)點(diǎn)間具有相同的標(biāo)簽，在預(yù)處理后的節(jié)點(diǎn)上進(jìn)行標(biāo)簽傳播，并以節(jié)點(diǎn)影響力輔助標(biāo)簽選擇，降低標(biāo)簽選擇的隨機(jī)性，提高算法社區(qū)發(fā)現(xiàn)的穩(wěn)定性和準(zhǔn)確性。

本文的主要工作如下：

1）提出了一種基于節(jié)點(diǎn)影響力的中心節(jié)點(diǎn)識(shí)別方法，利用中心節(jié)點(diǎn)進(jìn)行標(biāo)簽預(yù)處理，并能初步發(fā)現(xiàn)重疊節(jié)點(diǎn)。

2）用節(jié)點(diǎn)影響力輔助標(biāo)簽傳播過(guò)程的標(biāo)簽選擇，降低算法的隨機(jī)性。

3）引入弱社區(qū)判斷條件，以自適應(yīng)函數(shù)為優(yōu)化目標(biāo)，對(duì)不滿足條件的社區(qū)進(jìn)行合并，提升社區(qū)的內(nèi)聚度。

1 相關(guān)定義

一個(gè)無(wú)權(quán)無(wú)向的復(fù)雜網(wǎng)絡(luò)用G=（V，E）表示，V=｛v1，v2，…，vn｝是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E=｛e1，e2，…，en｝表示網(wǎng)絡(luò)中邊的集合，em=｛（vi，vj）|vi≠vj?vi，vj∈V｝。

定義1基本概念。節(jié)點(diǎn)vi的鄰域定義為Γi=｛vj|（vi，vj）∈E｝，vj稱為vi的鄰居節(jié)點(diǎn)。節(jié)點(diǎn)vi的度記為ki=|Γi|。

定義2內(nèi)度與外度。假設(shè)C=｛c1，c2，…，cl｝是G的一次社區(qū)劃分結(jié)果，cl稱為一個(gè)社區(qū)。節(jié)點(diǎn)vi∈cl的內(nèi)度表示vi與社區(qū)cl內(nèi)部節(jié)點(diǎn)的連邊數(shù)量，記為(cl)。外度表示vi與社區(qū)cl外部節(jié)點(diǎn)的連邊數(shù)量，記為(cl)。

定義3節(jié)點(diǎn)影響力。用節(jié)點(diǎn)排名算法PageRank［18］計(jì)算節(jié)點(diǎn)的pr值，節(jié)點(diǎn)vi對(duì)應(yīng)的pr值表示節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力，記為pri，其第t輪迭代的值計(jì)算公式如式（1）：

其中：Mi表示指向vi的節(jié)點(diǎn)集合，本文討論無(wú)向網(wǎng)絡(luò)，所以Mi=Γi；Lj表示vj的出度，即Li=|Γj|；N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量；1-α在原算法中表示隨機(jī)跳轉(zhuǎn)到其他網(wǎng)頁(yè)的概率，在無(wú)向連通圖中一般不存在出鏈循環(huán)的問(wèn)題，為保持與原算法的一致性，此處保留參數(shù)α，并設(shè)為0.85。

定義4中心節(jié)點(diǎn)。在當(dāng)前節(jié)點(diǎn)集合中，選擇pr值最大的節(jié)點(diǎn)作為當(dāng)前中心節(jié)點(diǎn)，記為cent，其形式化描述如式（2）：

其中：V'表示當(dāng)前節(jié)點(diǎn)集合；PR表示節(jié)點(diǎn)的pr值集合。

Tang 等［19］認(rèn)為網(wǎng)絡(luò)拓?fù)浒瑑呻A結(jié)構(gòu)，其中二階結(jié)構(gòu)考慮了節(jié)點(diǎn)的共同鄰居節(jié)點(diǎn)間的關(guān)系，若共同鄰居節(jié)點(diǎn)越多，則兩個(gè)節(jié)點(diǎn)的相似度越高。通常用公共鄰居數(shù)（Common Neighbors，CN）度量指標(biāo)CN(x，y)=|Γx∩Γy|表示節(jié)點(diǎn)的結(jié)構(gòu)相似度。本文從社區(qū)發(fā)現(xiàn)的角度對(duì)相似度重新定義，只對(duì)中心節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)計(jì)算相似度。

定義5節(jié)點(diǎn)相似度。對(duì)于vj∈Γcent，節(jié)點(diǎn)vj與cent的相似度記為Sim（cent，vj），定義如式（3）：

當(dāng)節(jié)點(diǎn)vj與中心節(jié)點(diǎn)cent無(wú)其他的共同鄰居節(jié)點(diǎn)時(shí)，|Γcent∩Γj|的值為0。為避免鄰居節(jié)點(diǎn)相似度為0 的情況，在式（3）中，對(duì)分子式加1。vj可能與多個(gè)中心節(jié)點(diǎn)相鄰，設(shè)分母為|Γj|，可衡量vj與不同中心節(jié)點(diǎn)的相似度，有利于發(fā)現(xiàn)重疊節(jié)點(diǎn)。

定義6同質(zhì)節(jié)點(diǎn)與異質(zhì)節(jié)點(diǎn)。當(dāng)Sim（cent，vj）>δ時(shí)，稱節(jié)點(diǎn)vj與中心節(jié)點(diǎn)cent同質(zhì)，否則稱節(jié)點(diǎn)vj與cent異質(zhì)。

若vj與中心節(jié)點(diǎn)同質(zhì)，則其擁有中心節(jié)點(diǎn)的標(biāo)簽，與多個(gè)中心節(jié)點(diǎn)同質(zhì)，就可同時(shí)擁有多個(gè)標(biāo)簽。

定義7標(biāo)簽預(yù)處理規(guī)則。對(duì)于已按pr值非升序排列的節(jié)點(diǎn)列表V'，逐個(gè)選擇中心節(jié)點(diǎn)cent，將cent的標(biāo)簽賦予同質(zhì)的節(jié)點(diǎn)。若滿足Rj≥1/γ，則vj保留在V'中；否則將vj從V'中刪除。其中，Rj=Rj-Sim（cent，vj），Rj的初值為1。循環(huán)這個(gè)過(guò)程，直到V'=?。

各類標(biāo)簽傳播算法中，一般情況下，同步標(biāo)簽傳播的穩(wěn)定性和收斂性高于異步標(biāo)簽傳播，本文也采用相同方法。同步標(biāo)簽傳播中，t時(shí)刻vi的標(biāo)簽由t-1時(shí)刻節(jié)點(diǎn)vi鄰居節(jié)點(diǎn)的標(biāo)簽分布決定。

定義8標(biāo)簽隸屬系數(shù)。標(biāo)簽隸屬系數(shù)記為bct（l，i），表示t時(shí)刻節(jié)點(diǎn)vi的標(biāo)簽為l的概率。bct（l，i）定義為：

定義9標(biāo)簽傳播規(guī)則。對(duì)于l∈LBK：若bct（l，i）≥1/γ，將l加入vi的標(biāo)簽集合lbi中，lbi=lbi∪l；否則，設(shè)置lbi=lbmaxl，maxl定義如式（5）：

其中：γ是節(jié)點(diǎn)可能歸屬的最大社區(qū)數(shù)；表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中標(biāo)簽為l的節(jié)點(diǎn)集合；LBK表示Γi中所有節(jié)點(diǎn)的標(biāo)簽集合。標(biāo)簽傳播中的第一步根據(jù)標(biāo)簽隸屬系數(shù)可以找到節(jié)點(diǎn)可能擁有的多個(gè)標(biāo)簽，第二步融合節(jié)點(diǎn)影響力的標(biāo)簽傳播可以提高算法的穩(wěn)定性。

當(dāng)網(wǎng)絡(luò)社區(qū)之間的混合度較小時(shí)，經(jīng)標(biāo)簽傳播后的社區(qū)一般無(wú)需合并?；旌隙容^大時(shí)，可能會(huì)形成部分不符合弱社區(qū)定義［20］的社區(qū)，此時(shí)需要將這類社區(qū)與其相鄰社區(qū)進(jìn)行合并。本文采用自適應(yīng)函數(shù)［11］作為合并目標(biāo)社區(qū)的判斷依據(jù)。

定義10弱社區(qū)。當(dāng)社區(qū)內(nèi)所有節(jié)點(diǎn)內(nèi)度之和大于其外度之和，稱該社區(qū)為弱社區(qū)。即弱社區(qū)c應(yīng)滿足式（6）：

系數(shù)θ的默認(rèn)值取1，對(duì)于混合度較大的網(wǎng)絡(luò)，隨著μ值增大而適當(dāng)調(diào)整θ的取值將會(huì)得到更為合理的社區(qū)劃分。

定義11自適應(yīng)函數(shù)。自適應(yīng)函數(shù)記為f（c），定義如式（7）：

其中，α是社區(qū)規(guī)?？刂茀?shù)，其取值一般為0.8～1.2。同一社區(qū)內(nèi)的節(jié)點(diǎn)內(nèi)度之和越大，則f（c）值越大，社區(qū)的內(nèi)聚度越高。

2 FLPNI算法

FLPNI 算法包含標(biāo)簽預(yù)處理、重疊社區(qū)發(fā)現(xiàn)和優(yōu)化處理三個(gè)步驟，其流程如圖1所示。

1）節(jié)點(diǎn)標(biāo)簽預(yù)處理階段。社交網(wǎng)絡(luò)中，同一社區(qū)中相鄰的兩個(gè)節(jié)點(diǎn)之間，節(jié)點(diǎn)的影響力值越大，則其向另一節(jié)點(diǎn)傳播標(biāo)簽的概率越大［21］。首先計(jì)算全部節(jié)點(diǎn)的pr值，選取pr值最大的節(jié)點(diǎn)作為中心節(jié)點(diǎn)，并用中心節(jié)點(diǎn)的標(biāo)簽對(duì)同質(zhì)節(jié)點(diǎn)進(jìn)行標(biāo)簽預(yù)處理。當(dāng)中心節(jié)點(diǎn)對(duì)同質(zhì)節(jié)點(diǎn)的標(biāo)簽傳播完成后，將不可能歸屬于多個(gè)社區(qū)的節(jié)點(diǎn)從待處理節(jié)點(diǎn)集合中刪除。之后，從待處理節(jié)點(diǎn)集合中再次選pr值最大的節(jié)點(diǎn)作為下一個(gè)中心節(jié)點(diǎn)，用同樣的方法進(jìn)行鄰居節(jié)點(diǎn)標(biāo)簽預(yù)處理。重復(fù)上述過(guò)程，直到待處理節(jié)點(diǎn)集合為空。經(jīng)過(guò)標(biāo)簽預(yù)處理，初始標(biāo)簽數(shù)量將大量減少，有利于后續(xù)的標(biāo)簽傳播。

圖1 FLPNI算法流程Fig.1 Flow chart of FLPNI algorithm

2）重疊社區(qū)發(fā)現(xiàn)階段。采用標(biāo)簽傳播的方式進(jìn)行節(jié)點(diǎn)標(biāo)簽選擇，計(jì)算節(jié)點(diǎn)的標(biāo)簽隸屬系數(shù)，識(shí)別出重疊節(jié)點(diǎn)。對(duì)于非重疊節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)的影響力進(jìn)行標(biāo)簽選擇。此措施可提高標(biāo)簽選擇的穩(wěn)定性和準(zhǔn)確性。

3）優(yōu)化處理階段。對(duì)于社區(qū)間混合度較高的網(wǎng)絡(luò)，標(biāo)簽傳播結(jié)束后會(huì)產(chǎn)生一些不符合弱社區(qū)條件的社區(qū)，需要將其與其他社區(qū)合并。用自適應(yīng)函數(shù)增量最大化選擇合并的目的社區(qū)，可以提高社區(qū)內(nèi)聚度。

2.1 算法偽碼

由算法模型及相關(guān)定義，F(xiàn)LPNI 算法的偽代碼如算法1～算法3所示。

算法1 中引入節(jié)點(diǎn)與中心節(jié)點(diǎn)的剩余相似度Ri，其初值為1，該值用于控制節(jié)點(diǎn)vi可歸屬于哪些社區(qū)以及何時(shí)從待處理節(jié)點(diǎn)列表中刪除。

經(jīng)過(guò)標(biāo)簽預(yù)處理，相似度高的節(jié)點(diǎn)間具有相同的標(biāo)簽，標(biāo)簽總體數(shù)量大幅度減少，降低了后續(xù)標(biāo)簽傳播的隨機(jī)性，且在此過(guò)程中將發(fā)現(xiàn)部分重疊節(jié)點(diǎn)。

算法2根據(jù)定義9進(jìn)行處理，其中選擇節(jié)點(diǎn)pr值之和最大的標(biāo)簽作為當(dāng)前節(jié)點(diǎn)標(biāo)簽的措施，減少了選擇標(biāo)簽的不確定性，并提高算法的精確度。

算法3 對(duì)社區(qū)進(jìn)行合并，合并后的社區(qū)具有更大的內(nèi)聚度，社區(qū)結(jié)構(gòu)更加健壯。其中Update()方法用于社區(qū)更新和重疊節(jié)點(diǎn)標(biāo)簽的處理。

以圖2 為例，對(duì)FLPNI 算法的操作過(guò)程進(jìn)行描述，具體步驟如下：

步驟一 圖2（a）是網(wǎng)絡(luò)的初始狀態(tài)。根據(jù)Pagerank 算法，計(jì)算圖2（a）中各節(jié)點(diǎn)的pr值。為了說(shuō)明問(wèn)題，此處按pr值降序?qū)?duì)應(yīng)節(jié)點(diǎn)排名，得到節(jié)點(diǎn)序列V'={5，11，7，13，12，0，1，2，6，4，14，10，15，3，8，9}。從V'中選擇pr值最大的節(jié)點(diǎn)v5為第一個(gè)中心節(jié)點(diǎn)。對(duì)于v5的鄰居節(jié)點(diǎn)，若Sim（v5，vj）≥δ，即節(jié)點(diǎn)與v5屬于同質(zhì)節(jié)點(diǎn)，則用v5的標(biāo)簽預(yù)處理鄰居節(jié)點(diǎn)的標(biāo)簽。其中，節(jié)點(diǎn)｛4，6，7，8，9｝與v5都是同質(zhì)節(jié)點(diǎn)，經(jīng)標(biāo)簽預(yù)處理，形成候選社區(qū)c1=｛4，5，6，7，8，9｝。

此時(shí)有兩種情況：

1）用于非重疊社區(qū)檢測(cè)時(shí)，直接將以上節(jié)點(diǎn)從V'中刪除，得到V'={11，13，12，0，1，2，14，10，15，3}。

2）對(duì)于重疊社區(qū)，需要進(jìn)一步計(jì)算。若與中心節(jié)點(diǎn)的相似度滿足Rj≥1/γ，說(shuō)明vj還可能歸屬于其他社區(qū)，則節(jié)點(diǎn)vj不能刪除。所以，對(duì)c1中的節(jié)點(diǎn)，從V'中刪除除v7外的其他節(jié)點(diǎn)，得到V'={11，7，13，12，0，1，2，14，10，15，3}。

不管是上述哪種情況，此時(shí)從V'中選擇第一個(gè)節(jié)點(diǎn)v11（pr值最大）作為下一個(gè)中心節(jié)點(diǎn)。重復(fù)步驟一，直到V'=?。

最終形成4 個(gè)中心節(jié)點(diǎn)及其預(yù)處理后的鄰居節(jié)點(diǎn)標(biāo)簽，可看成候選社區(qū)：c1=｛5，4，6，7，8，9｝，c2=｛11，7，10，12，13，15｝，c3=｛0，1，2，3｝，c4=｛14｝，候選社區(qū)中的第一個(gè)節(jié)點(diǎn)為當(dāng)前社區(qū)的中心節(jié)點(diǎn)。經(jīng)過(guò)預(yù)處理，節(jié)點(diǎn)v7已同時(shí)擁有兩個(gè)標(biāo)簽v7：｛lb5，lb11｝。結(jié)果如圖2（b），此時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)的標(biāo)簽數(shù)量大量減少。

步驟二 在圖2（b）的基礎(chǔ)上，計(jì)算節(jié)點(diǎn)的標(biāo)簽隸屬系數(shù)，對(duì)于隸屬度大于等于1/γ的標(biāo)簽直接保留，此時(shí)可進(jìn)一步識(shí)別出重疊節(jié)點(diǎn)。如節(jié)點(diǎn)v4，設(shè)γ=3，其標(biāo)簽隸屬系數(shù)為bc(lb0，4)=1/3，bc（lb11，4）=1/6和bc（lb5，4）=1/2，可保留兩個(gè)標(biāo)簽v4：｛lb0，lb5｝，而當(dāng)γ=2 時(shí)，則只保留標(biāo)簽v4：｛lb5｝。對(duì)于v7，當(dāng)γ≥2時(shí)保留兩個(gè)標(biāo)簽，而當(dāng)γ=1時(shí)，其鄰居節(jié)點(diǎn)中標(biāo)簽l5對(duì)應(yīng)的節(jié)點(diǎn)為v4和v5，標(biāo)簽l11對(duì)應(yīng)的節(jié)點(diǎn)為v11和v15，計(jì)算標(biāo)簽對(duì)應(yīng)節(jié)點(diǎn)的pr值之和，pr4+pr5>pr11+pr15，所以選擇v7的標(biāo)簽為lb5。經(jīng)過(guò)迭代傳播，直到節(jié)點(diǎn)標(biāo)簽不再發(fā)生變化。結(jié)果如圖2（c）。

圖2 FLPNI算法模型Fig.2 FLPNI algorithm model

步驟三 對(duì)于步驟二得到的社區(qū)，進(jìn)行弱社區(qū)判斷，對(duì)不滿足弱社區(qū)定義的，選擇合并后自適應(yīng)函數(shù)增量最大的社區(qū)進(jìn)行合并。圖2（c）中的社區(qū)都滿足弱社區(qū)，無(wú)需合并，算法結(jié)束。

2.2 算法時(shí)間復(fù)雜度分析

約定網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量為n，邊的數(shù)量為m，節(jié)點(diǎn)的平均度為k=2m/n，重疊節(jié)點(diǎn)數(shù)量on，節(jié)點(diǎn)歸屬的最大社區(qū)數(shù)為γ。

1）標(biāo)簽預(yù)處理。用PageRank 算法計(jì)算節(jié)點(diǎn)pr值的時(shí)間復(fù)雜度為O（n+m）［22］，將節(jié)點(diǎn)按pr值排序的時(shí)間復(fù)雜度為O(nlogn)。求中心節(jié)點(diǎn)與單個(gè)鄰居節(jié)點(diǎn)相似度的時(shí)間復(fù)雜度為O（k）。因?yàn)榇蟛糠止?jié)點(diǎn)都只與一個(gè)中心節(jié)點(diǎn)相連，共需要對(duì)n+on個(gè)節(jié)點(diǎn)計(jì)算相似度，計(jì)算全部節(jié)點(diǎn)與候選核心節(jié)點(diǎn)相似度的時(shí)間復(fù)雜度為O（k（n+on）），on值一般較小，可以忽略，則可簡(jiǎn)化為O（kn）。從V'中刪除已進(jìn)行標(biāo)簽預(yù)處理的節(jié)點(diǎn)的時(shí)間復(fù)雜度為O（n）。所以，標(biāo)簽預(yù)處理函數(shù)的時(shí)間復(fù)雜度為O(n+m+nlogn+kn+n)，又因?yàn)閗=2m/n，標(biāo)簽預(yù)處理階段的時(shí)間復(fù)雜度可表示為O(m+nlogn)。

2）重疊社區(qū)發(fā)現(xiàn)。進(jìn)行標(biāo)簽傳播的過(guò)程與COPRA 相似，對(duì)于一個(gè)稀疏網(wǎng)絡(luò)，每次迭代的時(shí)間復(fù)雜度為O(γ3n+γnlogγ)，通常情況下γ是一個(gè)很小的值，所以每次迭代的時(shí)間復(fù)雜度接近線性。實(shí)驗(yàn)中，迭代次數(shù)一般小于10。此過(guò)程中增加了節(jié)點(diǎn)pr值輔助判斷標(biāo)簽歸屬，不會(huì)增加算法的時(shí)間復(fù)雜度。

3）優(yōu)化處理。首先計(jì)算社區(qū)是否滿足弱社區(qū)條件，需要對(duì)每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)查詢其歸屬社區(qū)，其時(shí)間開銷為O(kn)。計(jì)算f（c）同樣需要查詢節(jié)點(diǎn)及鄰居節(jié)點(diǎn)的社區(qū)分布，且只在不滿足弱社區(qū)條件的情況下執(zhí)行，所以其時(shí)間開銷不超過(guò)O（kn）。

綜上，F(xiàn)LPNI 算法的三個(gè)步驟都具有接近線性的時(shí)間復(fù)雜度，算法總體時(shí)間復(fù)雜度為O(m+nlogn)。

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

本文實(shí)驗(yàn)包含了7 個(gè)對(duì)比算法，并分別在真實(shí)社交網(wǎng)絡(luò)和LFR（Lancichinetti-Fortunato-Radicchi）人工基準(zhǔn)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。對(duì)于有真實(shí)社區(qū)劃分的網(wǎng)絡(luò)，采用標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI）指標(biāo)［23］進(jìn)行對(duì)比評(píng)價(jià)。對(duì)于真實(shí)網(wǎng)絡(luò)，大部分情況下無(wú)法獲取其社區(qū)劃分，目前主流的方法是采用擴(kuò)展模塊度（Extended modularity，EQ）函數(shù)［24］進(jìn)行評(píng)價(jià)。實(shí)驗(yàn)環(huán)境為：Intel Core i7-8650U CPU 4.10 GHz，16 GB內(nèi)存，Windows 10操作系統(tǒng)，算法采用Python3.7實(shí)現(xiàn)。

對(duì)比算法包括COPRA、DBLINK（Density-Based LINK）［25］、CPM、LFM、DEMON、SLPA 和COPRAPC［17］。對(duì)比算法的參數(shù)設(shè)置如下：DBLINK 中，設(shè)置參數(shù)u=2～4，ε=0.1～0.4，步長(zhǎng)設(shè)置為0.02。CPM 中，設(shè)置參數(shù)k=3～10。LFM 中，設(shè)置參數(shù)α=0.8～1.2。DEMON 中，設(shè)置參數(shù)ε=0.1～1。在SLPA 中，迭代次數(shù)設(shè)置為15，參數(shù)r=0.1～0.5。COPRA 中，參數(shù)v=2～9。各算法在參數(shù)范圍內(nèi)評(píng)價(jià)指標(biāo)均達(dá)到最大值?？紤]到算法隨機(jī)性對(duì)結(jié)果的影響，F(xiàn)LPNI、COPRA、DEMON、LFM、COPRAPC和SLPA各運(yùn)行15次，并取各次最大值的平均值。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

3.1.1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

實(shí)驗(yàn)涉及的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集包含PGP（Pretty Good Privacy）［26］、Football、Karate、Polblog、Jazz 和Dolphins。其中，后面五個(gè)數(shù)據(jù)集來(lái)自于網(wǎng)站http：//www-personal.umich.edu/～mejn/netdata/。各個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和邊數(shù)情況如表1所示。

表1 真實(shí)網(wǎng)絡(luò)信息Tab.1 Information of real networks

3.1.2 LFR人工基準(zhǔn)網(wǎng)絡(luò)

LFR 人工基準(zhǔn)網(wǎng)絡(luò)［27］的各參數(shù)意義如下：N是生成網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)；minc和maxc規(guī)定一個(gè)社區(qū)中節(jié)點(diǎn)的最小和最大數(shù)量；k和maxk表示節(jié)點(diǎn)的平均度和最大度；μ是混合度參數(shù)，用于表示社區(qū)的清晰度，其值越大，各社區(qū)間的連接邊數(shù)越多，結(jié)構(gòu)越不清晰，社區(qū)發(fā)現(xiàn)的難度越大。μ是衡量算法穩(wěn)定性的一個(gè)重要指標(biāo)。重疊社區(qū)中，on表示網(wǎng)絡(luò)中具有重疊社區(qū)的節(jié)點(diǎn)數(shù)量，om表示節(jié)點(diǎn)最大可歸屬的社區(qū)數(shù)。本文實(shí)驗(yàn)數(shù)據(jù)集的各參數(shù)值設(shè)定如表2 所示。其中，全部網(wǎng)絡(luò)的節(jié)點(diǎn)度冪率分布指數(shù)τ1=2，社區(qū)規(guī)模冪率分布指數(shù)τ2=1。

表2 LFR基準(zhǔn)網(wǎng)絡(luò)信息Tab.2 Information of LFR benchmark networks

3.2 評(píng)價(jià)指標(biāo)

用于實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)包括EQ和NMI。

3.2.1 重疊模塊度

本文研究的對(duì)象為重疊社區(qū)，所以對(duì)于無(wú)真實(shí)社區(qū)劃分的網(wǎng)絡(luò)，算法運(yùn)行結(jié)果采用EQ指標(biāo)作為重疊社區(qū)結(jié)構(gòu)劃分質(zhì)量的評(píng)價(jià)指標(biāo)。與Girvan 等［1］提出的模塊度指標(biāo)不同的是，EQ中增加了節(jié)點(diǎn)歸屬社區(qū)數(shù)因子，定義如下：

其中：Ci表示算法劃分得到的第i個(gè)社區(qū)；Ox表示節(jié)點(diǎn)x歸屬的社區(qū)數(shù)；A是鄰接矩陣，節(jié)點(diǎn)x和y是鄰居節(jié)點(diǎn)時(shí)Axy=1，否則Axy=0；kx是節(jié)點(diǎn)x的度；m是網(wǎng)絡(luò)邊數(shù)。

3.2.2 標(biāo)準(zhǔn)化互信息

對(duì)于具有真實(shí)社區(qū)劃分的網(wǎng)絡(luò)，可采用NMI指標(biāo)對(duì)算法運(yùn)行結(jié)果予以評(píng)價(jià)。NMI用于比較基準(zhǔn)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)與算法所獲取社區(qū)結(jié)構(gòu)的相似程度，其定義如下：

其中：A是真實(shí)社區(qū)結(jié)構(gòu)；B是算法劃分結(jié)果；N是節(jié)點(diǎn)數(shù)；M是混淆矩陣；CA是真實(shí)社區(qū)數(shù)量；CB是經(jīng)算法劃分得到的社區(qū)數(shù)量；Mi·是A中第i個(gè)社區(qū)的節(jié)點(diǎn)數(shù)，即矩陣M中第i行元素之和；相應(yīng)地，M·j表示B中第j個(gè)社區(qū)的節(jié)點(diǎn)數(shù)，即矩陣M中第j列元素之和；Mij表示A中第i個(gè)社區(qū)的節(jié)點(diǎn)屬于B中第j個(gè)社區(qū)的節(jié)點(diǎn)數(shù)。NMI的值域?yàn)椋?，1］，值越大則表示算法的效果越好，當(dāng)NMI（A，B）=1時(shí)，表示A和B的結(jié)構(gòu)完全相同。

3.3 參數(shù)的取值實(shí)驗(yàn)

FLPNI 算法中涉及三個(gè)參數(shù)α、δ和γ。自適應(yīng)函數(shù)fitness中的參數(shù)α建議取值范圍為0.8～1.2，本文設(shè)置α=1。參數(shù)δ和γ的取值討論如下。

3.3.1δ的取值實(shí)驗(yàn)

在標(biāo)簽預(yù)處理階段，需要判斷中心節(jié)點(diǎn)與鄰居節(jié)點(diǎn)是否同質(zhì)，參數(shù)δ的取值與μ的關(guān)系較大，因此，本實(shí)驗(yàn)在具有不同μ值的N1數(shù)據(jù)集上進(jìn)行，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 參數(shù)δ實(shí)驗(yàn)結(jié)果Fig.3 Experimental results of parameter δ

對(duì)于μ≤0.5 的網(wǎng)絡(luò)，δ的變化對(duì)結(jié)果影響較小。其中，各個(gè)數(shù)據(jù)集在δ=0.3 時(shí)會(huì)取得較優(yōu)的結(jié)果。對(duì)于μ=0.6 的數(shù)據(jù)集，當(dāng)δ>0.2，NMI的下降比較明顯，且NMI值隨著δ值的增大而呈下降趨勢(shì)。在μ=0.7 的數(shù)據(jù)集上，當(dāng)δ>0.3 時(shí)，F(xiàn)LPNI 算法得到的NMI值為0，即把整個(gè)網(wǎng)絡(luò)劃分為一個(gè)社區(qū)?？梢?，在μ較小的網(wǎng)絡(luò)中，同一社區(qū)的節(jié)點(diǎn)間關(guān)系較為密切，δ的取值變化對(duì)結(jié)果影響小。在μ較大的網(wǎng)絡(luò)中，節(jié)點(diǎn)間的相似度較小，當(dāng)δ值較大時(shí)，無(wú)法識(shí)別同質(zhì)節(jié)點(diǎn)，沒有達(dá)到標(biāo)簽預(yù)處理的目的，導(dǎo)致在μ=0.7的數(shù)據(jù)集上，將整個(gè)網(wǎng)絡(luò)識(shí)別為一個(gè)社區(qū)，其結(jié)果與COPRA 相同。所以，建議在μ≤0.4 時(shí)，設(shè)δ=0.3；μ=0.5時(shí)，δ設(shè)為0.2～0.25；μ≥0.6時(shí)，δ設(shè)為0.1～0.15。

3.3.2γ的取值實(shí)驗(yàn)

γ用于控制節(jié)點(diǎn)在多大概率上可以接受鄰居節(jié)點(diǎn)的標(biāo)簽傳播，其值越大，節(jié)點(diǎn)可能歸屬的社區(qū)數(shù)就越多。而一個(gè)節(jié)點(diǎn)歸屬的社區(qū)情況通常是未知的，并不是歸屬的社區(qū)數(shù)越多越好。圖4是在N1上γ的取值實(shí)驗(yàn)結(jié)果。

圖4 參數(shù)γ實(shí)驗(yàn)結(jié)果Fig.4 Experimental results of parameter γ

對(duì)于μ≤0.4的網(wǎng)絡(luò)，γ=6～7時(shí)FLPNI算法得到的NMI值最大。對(duì)于μ≥0.5 的網(wǎng)絡(luò)，算法得到的NMI值呈現(xiàn)隨γ值增加而增大的趨勢(shì)。這是因?yàn)棣讨翟酱?，歸屬于其他社區(qū)的鄰居節(jié)點(diǎn)就越多，節(jié)點(diǎn)的標(biāo)簽隸屬度變小。當(dāng)γ值較小的時(shí)候，節(jié)點(diǎn)歸屬的社區(qū)數(shù)就少，易將重疊節(jié)點(diǎn)誤判為只歸屬于一個(gè)社區(qū)，算法得到的社區(qū)劃分結(jié)果與實(shí)際情況差別較大，造成NMI下降。

3.4 在真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果分析

FLPNI 算法與其他7 個(gè)對(duì)比算法在Karate 等6 個(gè)真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果如圖5 所示。在Polbooks、Dolphins 和PGP 三個(gè)網(wǎng)絡(luò)上，F(xiàn)LPNI 算法的社區(qū)劃分結(jié)果EQ值最大。在Football網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果中，SLPA 具有最大的EQ值，F(xiàn)LPNI與LFM 的結(jié)果相同，高于其他算法。在Karate 網(wǎng)絡(luò)上，F(xiàn)LPNI算法得到的EQ值小于LFM 算法，但其得到的結(jié)果與真實(shí)社區(qū)劃分一致。除Jazz 網(wǎng)絡(luò)之外，F(xiàn)LPNI 算法在其他網(wǎng)絡(luò)上得到的社區(qū)劃分結(jié)果其EQ值都優(yōu)于COPRA，表明融合標(biāo)簽預(yù)處理和節(jié)點(diǎn)重要性的方法對(duì)提高標(biāo)簽傳播的準(zhǔn)確性是有效的。

圖5 真實(shí)網(wǎng)絡(luò)上不同算法的實(shí)驗(yàn)結(jié)果（EQ值）Fig.5 Experimental results of different algorithms on real networks（EQ value）

3.5 在LFR基準(zhǔn)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果分析

將本文算法和對(duì)比算法在LFR 基準(zhǔn)網(wǎng)絡(luò)（表2）上進(jìn)行實(shí)驗(yàn)，分別檢測(cè)算法對(duì)于混合度參數(shù)、節(jié)點(diǎn)歸屬社區(qū)數(shù)和網(wǎng)絡(luò)中重疊節(jié)點(diǎn)數(shù)量變化的適應(yīng)性。

3.5.1 在不同μ值網(wǎng)絡(luò)上的精度實(shí)驗(yàn)

對(duì)于表2 中的N1 數(shù)據(jù)集，各算法劃分出的社區(qū)的NMI值如圖6所示。

隨著μ值增加，各算法得到的NMI值都呈下降趨勢(shì)。其中，F(xiàn)LPNI 算法在7 個(gè)網(wǎng)絡(luò)上的NMI值都高于對(duì)比算法。FLPNI 算法在第一步進(jìn)行了標(biāo)簽預(yù)處理，形成了初步的社區(qū)，有效解決了高混合度網(wǎng)絡(luò)中標(biāo)簽傳播隨機(jī)性大的缺陷，其在μ=0.7 的網(wǎng)絡(luò)中仍可以把部分節(jié)點(diǎn)劃分到正確的社區(qū)中；而其他對(duì)比算法得到的NMI值等于0 或接近0，且由表3 可知，COPRA 和COPRAPC 得到的社區(qū)數(shù)為1，已無(wú)法識(shí)別社區(qū)，這是μ值過(guò)大、標(biāo)簽過(guò)度傳播引起的結(jié)果。

圖6 不同μ值網(wǎng)絡(luò)上的精度實(shí)驗(yàn)結(jié)果Fig.6 Experimental results of accuracy on networks with differentμ

3.5.2 在不同om值網(wǎng)絡(luò)上的精度實(shí)驗(yàn)

在不同om值網(wǎng)絡(luò)（N2網(wǎng)絡(luò)）上的實(shí)驗(yàn)結(jié)果如圖7所示。

圖7結(jié)果表明，對(duì)于不同的om值，F(xiàn)LPNI算法都具有較強(qiáng)的適應(yīng)性，其得到的NMI值均高于對(duì)比算法。FLPNI 算法在網(wǎng)絡(luò)優(yōu)化處理階段對(duì)部分不滿足弱社區(qū)定義的待合并社區(qū)進(jìn)行了優(yōu)化處理，基于自適應(yīng)函數(shù)的處理方法增強(qiáng)了社區(qū)的內(nèi)聚度，提高了社區(qū)發(fā)現(xiàn)的質(zhì)量。

圖7 不同om值網(wǎng)絡(luò)上的精度實(shí)驗(yàn)結(jié)果Fig.7 Experimental results of accuracy on networks with different om

3.5.3 在不同on值網(wǎng)絡(luò)上的精度實(shí)驗(yàn)

在不同on值網(wǎng)絡(luò)（N3 網(wǎng)絡(luò)）上的精度實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 不同on值網(wǎng)絡(luò)上的精度實(shí)驗(yàn)結(jié)果Fig.8 Experimental results of accuracy on networks with different on

隨著網(wǎng)絡(luò)中重疊節(jié)點(diǎn)數(shù)量增加，社區(qū)發(fā)現(xiàn)難度逐漸變大。當(dāng)on=3 000 時(shí)，LFM、CPM 和DBLINK 算法得到的NMI值小于0.3，發(fā)現(xiàn)的社區(qū)質(zhì)量較差；當(dāng)on=3 500 時(shí)，LFM 和CPM 的NMI值接近0，已無(wú)法識(shí)別社區(qū)。FLPNI、COPRA、COPRAPC和DEMON 算法具有較好的適應(yīng)性。在8 個(gè)算法中，F(xiàn)LPNI 算法仍然具有最大的NMI值。

3.5.4 在不同規(guī)模網(wǎng)絡(luò)上的時(shí)間性能實(shí)驗(yàn)

在不同規(guī)模網(wǎng)絡(luò)（N4 網(wǎng)絡(luò)）上的時(shí)間性能實(shí)驗(yàn)如圖9所示。

圖9 在不同規(guī)模網(wǎng)絡(luò)上的時(shí)間性能實(shí)驗(yàn)結(jié)果Fig.9 Experimental results of time performance on networks with different scales

其中，SLPA具有最快的運(yùn)行速度，DBLINK的運(yùn)行時(shí)間比SLPA 略長(zhǎng)。FLPNI、COPRA 和COPRAPC 的時(shí)間性能較為接近，F(xiàn)LPNI 運(yùn)行時(shí)間略長(zhǎng)于COPRA，主要原因是FLPNI 中，經(jīng)標(biāo)簽預(yù)處理后，標(biāo)簽傳播的迭代次數(shù)減少，但前期預(yù)處理的時(shí)間復(fù)雜度為O(m+nlogn)，當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，其運(yùn)行時(shí)間會(huì)比COPRA 有所增加。FLPNI 算法的時(shí)間性能明顯優(yōu)于LFM、CPM 和DEMON 等三個(gè)算法。實(shí)驗(yàn)結(jié)果表明，F(xiàn)LPNI 算法具有接近線性的時(shí)間復(fù)雜度。

3.5.5 算法得到的社區(qū)數(shù)量

算法得到的社區(qū)數(shù)量與真實(shí)社區(qū)數(shù)量的接近程度，可以作為輔助衡量算法社區(qū)發(fā)現(xiàn)能力的一個(gè)指標(biāo)。對(duì)各類算法在N1數(shù)據(jù)集上發(fā)現(xiàn)的社區(qū)數(shù)量進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表3所示，其中NCREAL表示網(wǎng)絡(luò)的真實(shí)社區(qū)數(shù)。在μ≤0.5 的網(wǎng)絡(luò)上，F(xiàn)LPNI 算法得到的社區(qū)數(shù)與真實(shí)社區(qū)數(shù)一致。COPRA 得到的結(jié)果也比較接近真實(shí)社區(qū)數(shù)量，但其和DBLINK 算法在μ=0.7 的網(wǎng)絡(luò)上無(wú)法檢測(cè)社區(qū)，將整個(gè)網(wǎng)絡(luò)識(shí)別為一個(gè)社區(qū)。CPM 和LFM 識(shí)別出的社區(qū)數(shù)與真實(shí)情況差別較大，其對(duì)應(yīng)的NMI值也趨于0。實(shí)驗(yàn)結(jié)果表明，本文算法劃分的社區(qū)數(shù)更接近真實(shí)社區(qū)數(shù)量。

表3 不同算法劃分的社區(qū)數(shù)Tab.3 Number of communities detected by different algorithms

4 結(jié)語(yǔ)

本文提出了一種融合標(biāo)簽預(yù)處理和節(jié)點(diǎn)影響力的重疊社區(qū)發(fā)現(xiàn)算法。該算法針對(duì)初始階段節(jié)點(diǎn)標(biāo)簽傳播隨機(jī)性較大的問(wèn)題，利用節(jié)點(diǎn)重要性排名，提出了一種中心節(jié)點(diǎn)識(shí)別方法，并利用中心節(jié)點(diǎn)對(duì)鄰居節(jié)點(diǎn)進(jìn)行標(biāo)簽預(yù)處理，同時(shí)根據(jù)剩余相似度識(shí)別出與多個(gè)中心節(jié)點(diǎn)有緊密聯(lián)系的重疊節(jié)點(diǎn)。經(jīng)過(guò)預(yù)處理，相似度較高的節(jié)點(diǎn)具有相同的標(biāo)簽，標(biāo)簽數(shù)量大幅度減少，降低了后續(xù)標(biāo)簽傳播的隨機(jī)性和迭代次數(shù)。在重疊社區(qū)發(fā)現(xiàn)過(guò)程，對(duì)于非重疊節(jié)點(diǎn)，在需要隨機(jī)選擇標(biāo)簽的情況下，對(duì)鄰居節(jié)點(diǎn)按標(biāo)簽分組計(jì)算對(duì)應(yīng)節(jié)點(diǎn)的影響力作為選擇標(biāo)準(zhǔn)，減少了標(biāo)簽震蕩現(xiàn)象，提高了算法的穩(wěn)定性和社區(qū)劃分的精確度。最后，通過(guò)計(jì)算社區(qū)內(nèi)節(jié)點(diǎn)的內(nèi)度與外度分布，以優(yōu)化內(nèi)聚度為目標(biāo)，將內(nèi)度較小的社區(qū)與相鄰社區(qū)合并，提高了社區(qū)質(zhì)量，且使得算法得到的社區(qū)數(shù)量與真實(shí)社區(qū)數(shù)量較為接近。通過(guò)與其他算法在真實(shí)網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果對(duì)比，驗(yàn)證了所提出算法的有效性。

下一步的研究中，一個(gè)改進(jìn)的方向是在動(dòng)態(tài)網(wǎng)絡(luò)中快速識(shí)別中心節(jié)點(diǎn)，使得算法可以擴(kuò)展應(yīng)用于動(dòng)態(tài)網(wǎng)絡(luò)的重疊社區(qū)識(shí)別。針對(duì)大規(guī)模網(wǎng)絡(luò)，還需要考慮將關(guān)鍵步驟并行化，進(jìn)一步提高算法效率，以適應(yīng)規(guī)模日益增長(zhǎng)的社交網(wǎng)絡(luò)應(yīng)用。