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

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

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

0 引言

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

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

與本文研究相關(guān)的方法有兩類：一類是基于種子擴(kuò)展的方法。Lancichinetti 等［11］提出的LFM（Local Fitness Method）以隨機(jī)節(jié)點作為種子節(jié)點，以最大化自適應(yīng)函數(shù)值為目標(biāo)進(jìn)行局部擴(kuò)展優(yōu)化，可檢測層次和重疊社區(qū)，但其時間復(fù)雜度達(dá)到O（n2），且種子節(jié)點的選擇未考慮節(jié)點的重要性，算法的穩(wěn)定性和適應(yīng)性較差。杜航原等［12］通過搜索局部密度中心作為社區(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 算法提取每個節(jié)點的自我網(wǎng)絡(luò)（ego），并在這個結(jié)構(gòu)上應(yīng)用LPA，再將這些局部社區(qū)進(jìn)行合并，可在全局級別揭示網(wǎng)絡(luò)的模塊化組織，但該算法存在穩(wěn)定性差的問題。COPRA 通過引入歸屬系數(shù)，將標(biāo)簽傳播方法應(yīng)用到重疊社區(qū)發(fā)現(xiàn)，其在各類網(wǎng)絡(luò)上具有較好的適應(yīng)性，但COPRA 中標(biāo)簽選擇過程隨機(jī)性較大，當(dāng)社區(qū)間混合度較大時容易把整個網(wǎng)絡(luò)識別為一個社區(qū)。馬健等［17］對COPRA 中的節(jié)點標(biāo)簽更新順序和傳播門限進(jìn)行了改進(jìn)，提出了COPRAPC（Community Overlap PRopagation Algorithm based on PageRank and Clustering coefficient），選擇影響力小的節(jié)點優(yōu)先進(jìn)行標(biāo)簽傳播，并用節(jié)點聚類系數(shù)控制節(jié)點歸屬的最大社區(qū)數(shù)。SLPA 根據(jù)動態(tài)交互規(guī)則進(jìn)行標(biāo)簽交換，該算法在高混合度網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)的能力較弱。

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

本文的主要工作如下：

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

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

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

1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 FLPNI算法

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

1）節(jié)點標(biāo)簽預(yù)處理階段。社交網(wǎng)絡(luò)中，同一社區(qū)中相鄰的兩個節(jié)點之間，節(jié)點的影響力值越大，則其向另一節(jié)點傳播標(biāo)簽的概率越大［21］。首先計算全部節(jié)點的pr值，選取pr值最大的節(jié)點作為中心節(jié)點，并用中心節(jié)點的標(biāo)簽對同質(zhì)節(jié)點進(jìn)行標(biāo)簽預(yù)處理。當(dāng)中心節(jié)點對同質(zhì)節(jié)點的標(biāo)簽傳播完成后，將不可能歸屬于多個社區(qū)的節(jié)點從待處理節(jié)點集合中刪除。之后，從待處理節(jié)點集合中再次選pr值最大的節(jié)點作為下一個中心節(jié)點，用同樣的方法進(jìn)行鄰居節(jié)點標(biāo)簽預(yù)處理。重復(fù)上述過程，直到待處理節(jié)點集合為空。經(jīng)過標(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é)點標(biāo)簽選擇，計算節(jié)點的標(biāo)簽隸屬系數(shù)，識別出重疊節(jié)點。對于非重疊節(jié)點，根據(jù)節(jié)點的影響力進(jìn)行標(biāo)簽選擇。此措施可提高標(biāo)簽選擇的穩(wěn)定性和準(zhǔn)確性。

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

2.1 算法偽碼

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

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

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

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

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

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

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

此時有兩種情況：

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

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

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

最終形成4 個中心節(jié)點及其預(yù)處理后的鄰居節(jié)點標(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ū)中的第一個節(jié)點為當(dāng)前社區(qū)的中心節(jié)點。經(jīng)過預(yù)處理，節(jié)點v7已同時擁有兩個標(biāo)簽v7：｛lb5，lb11｝。結(jié)果如圖2（b），此時網(wǎng)絡(luò)節(jié)點的標(biāo)簽數(shù)量大量減少。

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

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

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

對比算法包括COPRA、DBLINK（Density-Based LINK）［25］、CPM、LFM、DEMON、SLPA 和COPRAPC［17］。對比算法的參數(shù)設(shè)置如下：DBLINK 中，設(shè)置參數(shù)u=2～4，ε=0.1～0.4，步長設(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)評價指標(biāo)均達(dá)到最大值?？紤]到算法隨機(jī)性對結(jié)果的影響，F(xiàn)LPNI、COPRA、DEMON、LFM、COPRAPC和SLPA各運行15次，并取各次最大值的平均值。

3.1 實驗數(shù)據(jù)集

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

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

表1 真實網(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é)點數(shù)；minc和maxc規(guī)定一個社區(qū)中節(jié)點的最小和最大數(shù)量；k和maxk表示節(jié)點的平均度和最大度；μ是混合度參數(shù)，用于表示社區(qū)的清晰度，其值越大，各社區(qū)間的連接邊數(shù)越多，結(jié)構(gòu)越不清晰，社區(qū)發(fā)現(xiàn)的難度越大。μ是衡量算法穩(wěn)定性的一個重要指標(biāo)。重疊社區(qū)中，on表示網(wǎng)絡(luò)中具有重疊社區(qū)的節(jié)點數(shù)量，om表示節(jié)點最大可歸屬的社區(qū)數(shù)。本文實驗數(shù)據(jù)集的各參數(shù)值設(shè)定如表2 所示。其中，全部網(wǎng)絡(luò)的節(jié)點度冪率分布指數(shù)τ1=2，社區(qū)規(guī)模冪率分布指數(shù)τ2=1。

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

3.2 評價指標(biāo)

用于實驗的評價指標(biāo)包括EQ和NMI。

3.2.1 重疊模塊度

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

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

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

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

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

3.3 參數(shù)的取值實驗

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

3.3.1δ的取值實驗

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

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

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

3.3.2γ的取值實驗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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