孫學良，王巍，黃俊恒，辛國棟，王佰玲

（1. 哈爾濱工業(yè)大學計算學部，黑龍江 哈爾濱 150001； 2. 哈爾濱工業(yè)大學（威海）計算機科學與技術學院，山東 威海 264209）

0 引言

網(wǎng)絡是表示事物與事物之間聯(lián)系的常用工具?，F(xiàn)實生活中，各個組織隨著時間推移所產(chǎn)生的復雜信息常以網(wǎng)絡的形式呈現(xiàn)，如科研協(xié)作網(wǎng)、社交關系網(wǎng)、金融交易網(wǎng)絡等。在這些網(wǎng)絡中，通常存在很多自然形成的社區(qū)，社區(qū)內(nèi)部成員與成員之間聯(lián)系緊密，社區(qū)之間聯(lián)系稀疏。如何有效地從網(wǎng)絡中識別出這些社區(qū)是社區(qū)檢測的基本任務，具有重要的現(xiàn)實意義。例如，從科研協(xié)作網(wǎng)中識別出具有相近研究領域的學者，或者從社交網(wǎng)絡中識別出具有相似興趣愛好的用戶等。

隨著復雜網(wǎng)絡研究的深入，相當多的社區(qū)檢測算法被相繼提出，許多算法從不同角度來解決社區(qū)檢測問題[1]。最開始是分裂算法，它基于去除邊的思想將社區(qū)分開，但這種全局的方法對計算要求很高。為了克服這個問題，研究人員后續(xù)提出了凝聚算法或其他優(yōu)化算法進行改進。在優(yōu)化算法方面，基于模塊度的算法成為優(yōu)化算法的主流，但基于模塊度的算法不易發(fā)現(xiàn)小的社區(qū)，計算量過大，因此后續(xù)發(fā)展出其他的解決方案。

2007年，Raghavan[2]提出的標簽傳播算法（LPA，label propagation algorithm）就是其中的代表方案，LPA因其易于實現(xiàn)、概念簡單廣受歡迎，該算法受傳染病模型的啟發(fā)，通過節(jié)點標簽的迭代更新直至收斂來檢測社區(qū)，但算法存在隨機性強、運行結果不穩(wěn)定等問題。

為了使社區(qū)檢測更加真實地反映節(jié)點和社區(qū)之間的實際關系，本文在標簽傳播算法的基礎上，消除了原算法的不穩(wěn)定性，并采用矢量表示和廣度優(yōu)先傳播的思想，對標簽的傳播策略進行了改進，主要工作如下。

1) 提出了基于標簽傳播的兩階段社區(qū)檢測算法（TS-LPA，two-stage community detection algorithm based on label propagation），重點優(yōu)化了標簽更新過程。

2) 結合網(wǎng)絡局部拓撲結構信息，本文采用擴展鄰域的思想對節(jié)點的中心性進行度量，并在此基礎上提出一種新的評價指標來衡量節(jié)點之間的影響概率。

3) 利用廣度優(yōu)先傳播的思想，提出了第二階段標簽傳播方式，來提高社區(qū)檢測的質量。

4) 在不同數(shù)據(jù)集上的實驗結果表明，TS-LPA表現(xiàn)出較強的穩(wěn)定性，有效提高了社區(qū)檢測的質量。

1 相關工作

國內(nèi)外學者在定義、檢測和識別現(xiàn)實網(wǎng)絡的社區(qū)方面做了很多工作，提出了各種算法，根據(jù)社區(qū)檢測的“方向”，可以分為自上而下的方法和自下而上的方法[3]。

自上而下的方法：基于圖或者邊去除的思想，將整個網(wǎng)絡分成小組，以檢測社區(qū)。分裂算法屬于該類別。2012年，Prat-Perez等[4]提出了一個加權社區(qū)聚類算法（WCC），并認為好的社區(qū)是在所有的社區(qū)節(jié)點之間形成大量的三角形社區(qū)，因此，為了定義社區(qū)，WCC測量節(jié)點x與集合S中的節(jié)點形成的三角形的比率，而不是x在整個圖中形成的三角形的數(shù)量。2018年，Qiao等[5]提出了Picaso的自上而下策略，根據(jù)社區(qū)的特征，有些邊的權重會消失，有些邊的權重像山峰一樣升起。算法包含兩個階段（山模型的構建和社區(qū)合并更新），經(jīng)過實驗分析表明，Picaso算法可以處理大型的網(wǎng)絡，并且具有良好的 效率。

自下而上的方法：從局部結構開始擴展到整個網(wǎng)絡，在這個過程中，逐步形成各種社區(qū)[6]。許多不同的想法實現(xiàn)了自下而上的檢測方法，如模塊度優(yōu)化[7-9]、標簽傳播等。模塊度優(yōu)化是找到一個從指定節(jié)點開始的子圖，使子圖增加一個節(jié)點或者刪除一個節(jié)點都會降低模塊度值，最終找到的社區(qū)滿足模塊度值最大，實現(xiàn)社區(qū)的檢測[10]。2004年，Newman首先定義了模塊度概念并提出模塊度算法[11]，之后提出Louvain算法，該算法在模塊度算法基礎上做了進一步的改進[12]，將層次聚類與模塊度優(yōu)化有效結合，分為兩個階段進行迭代劃分檢測。Louvain算法被認為是當前較為高效的社區(qū)檢測算法之一；標簽傳播的基本思想是利用樣本間的關系建立完全圖模型，將圖模型中每個節(jié)點作為中心節(jié)點進行迭代標簽更新，迭代過程中利用一階鄰居標簽對中心節(jié)點的標簽進行更新。2007年，Raghavan等[2]將標簽傳播思想引入社區(qū)檢測任務，提出了標簽傳播算法，該算法僅以網(wǎng)絡結構為指導，每個節(jié)點都用一個唯一的標簽初始化，并且在每一步每個節(jié)點都獲得了它的大多數(shù)鄰居當前擁有的標簽。通過不斷迭代，密集的節(jié)點組傾向于獲得相同的標簽，從而形成一個社區(qū)。該算法具有線性的時間復雜度，更適用于社區(qū)結構已知的網(wǎng)絡。但是LPA算法也存在穩(wěn)定性較差的問題，其示意如圖1所示。

圖1 標簽傳播算法示意 Figure 1 Schematic diagram of label propagation algorithm

從圖1可知，根據(jù)節(jié)點更新順序的不同，分別按照①號線條和②號線條更新時，產(chǎn)生的社區(qū)檢測結果不同。例如，當標簽按照①號線條傳播時，節(jié)點標簽更新順序為6、7、8，6號節(jié)點鄰居的標簽分別為黃色、紅色、藍色節(jié)點各一個，在不同類別鄰居標簽數(shù)量相同的情況下，6號節(jié)點隨機選擇了紅色，造成最終整個社區(qū)全都為紅色節(jié)點。此外，在更新策略方面，同步更新可能引起標簽震蕩的問題，也會造成算法的不穩(wěn)定[13]，其結果如圖2所示。

圖2 人工網(wǎng)絡同步更新的結果 Figure 2 Schematic diagram of manual network label synchronization update

后來，研究人員在LPA的基礎上做了不同程度的優(yōu)化，來適應更多的應用場景[14-18]：為了避免LPA將所有節(jié)點劃分到同一社區(qū)，Barber和Clark[19]提出了一種模塊化標簽傳播算法（LPAm），將社區(qū)檢測問題轉化為求目標函數(shù)最大值問題，但容易陷入局部最優(yōu)解的情況。為了解決上述問題，Liu等[20]在LPAm的基礎上，融合多步貪婪凝聚算法，提出了基于模塊度最大化的標簽傳播LPAm+，將多對社區(qū)融合，避免局部最大值的出現(xiàn)。Li[21]探索了在LPA的基礎上引入方向性的方法，提出了約束定向的標簽傳播算法，將邊的方向轉化為邊的權重，探索了定向化模塊的劃分，但并未考慮邊自身的權重信息。Zhang等[22]提出了一種基于節(jié)點重要性和標簽影響的算法，融合貝葉斯定理來計算節(jié)點的重要性，對節(jié)點的重要性進行了有效評估，但該方法只考慮了周圍節(jié)點的信息，并沒有融合邊的信息，使標簽影響能力的計算有所欠缺。

現(xiàn)有LPA的改進工作主要針對節(jié)點標簽初始化、節(jié)點的標簽選擇策略、節(jié)點的標簽更新順序等方面進行改進，并沒有考慮節(jié)點之間的影響。在網(wǎng)絡中已有信息的利用上，也沒有很好的策略。針對以上不足，本文提出了一種新的節(jié)點之間影響力計算方法，并引入廣度優(yōu)先傳播的思想來有效利用已知信息。

2 TS-LPA

本文引入擴展鄰域的概念來表示節(jié)點傳播信息的能力（即節(jié)點的影響力），通過綜合節(jié)點影響力和邊的權重信息計算節(jié)點之間的影響概率，算法的基本思想概括如下。

1) 構建網(wǎng)絡圖，利用擴展鄰域核心度的方法來計算節(jié)點的重要性，并根據(jù)網(wǎng)絡的拓撲結構，綜合利用鄰居信息得到節(jié)點的影響力。

2) 結合節(jié)點影響力和邊的信息計算單個節(jié)點對不同鄰居的影響概率，并進行均一化表示，構建網(wǎng)絡的節(jié)點影響概率矩陣。

3) 在節(jié)點的設置方面，根據(jù)節(jié)點的影響力確定種子節(jié)點選取策略，利用矢量來表示節(jié)點的類標簽，提高迭代效率。

4) 標簽迭代更新過程中，利用廣度優(yōu)先搜索方式搜索種子節(jié)點信息，根據(jù)搜索結果，對標簽更新的類標簽向量進行進一步更新。

2.1 節(jié)點影響力計算

現(xiàn)實中復雜網(wǎng)絡的節(jié)點地位是不平等的，不同節(jié)點對網(wǎng)絡結構和性能的影響可能會有很大的差異，網(wǎng)絡的傳播效應會受到一些重要節(jié)點的影響。例如，在傳銷的運作中，總經(jīng)理、經(jīng)理、主任、業(yè)務員等人員在組織運作過程中扮演著重要的角色。這種現(xiàn)實職位的重要性同樣反映在交易網(wǎng)絡中，總經(jīng)理的賬號往往周圍鄰居節(jié)點數(shù)更多或者邊的交易金額、交易次數(shù)權重更大，更大限度地影響著網(wǎng)絡的結構和性能。

結合現(xiàn)實的分析，為了更有效地對節(jié)點的重要性進行衡量，本文采用節(jié)點的擴展鄰域核心度[23]來量化節(jié)點的傳播能力，在此基礎上，綜合考慮節(jié)點與其鄰居節(jié)點之間邊的權重及鄰居節(jié)點的度數(shù)，擴展得到節(jié)點綜合影響力Node值。

定義1對于給定的網(wǎng)絡G= (V,E)，其中表示網(wǎng)絡的節(jié)點集，E表示網(wǎng)絡的邊集。節(jié)點綜合影響力Node值的計算如式(1)所示。

其中，E Ncoreness(i)[23]表示節(jié)點i的擴展鄰域核心度，Wij表示節(jié)點i與節(jié)點j之間邊的權重，N(i)表示節(jié)點i的一階鄰居節(jié)點集合，dj代表節(jié)點j的度數(shù)。

2.2 節(jié)點之間影響概率的計算

LPA的節(jié)點標簽選擇策略具有隨機性，造成了社區(qū)檢測的不穩(wěn)定。此外，考慮周圍鄰居節(jié)點對更新節(jié)點的影響時并未涉及節(jié)點權重和邊權重的影響。如圖3所示，A、C、D與B進行業(yè)務往來，A與B進行了5次業(yè)務往來，涉及金額10 000元，C、D和B各進行了1次業(yè)務往來，涉及金額500元，根據(jù)標簽傳播算法，節(jié)點B應該劃入C、D所屬的社區(qū)，但實際上節(jié)點A對節(jié)點B的影響概率更大，這顯然與實際不符。

圖3 一個人工生成的網(wǎng)絡 Figure 3 An artificially generated network

為了解決此類問題，本文考慮鄰居節(jié)點對待更新節(jié)點的影響，從節(jié)點的綜合影響力、節(jié)點與鄰居節(jié)點之間邊的權重兩方面來考慮，使待更新節(jié)點的所有鄰居節(jié)點的標簽都對其產(chǎn)生一定限度的影響，從而使待更新節(jié)點的影響因素多樣化，提高節(jié)點標簽更新的準確性?？紤]到在實際應用網(wǎng)絡（如傳銷金融網(wǎng)絡）中，若利用交易平均金額來表示邊的權值，不同邊的權重可能在幾百到幾萬之間不等，那么待更新節(jié)點的不同鄰居節(jié)點影響力與邊的權重的乘積會相差過大，不利于標簽影響概率的計算。因此，本文在兩者相乘的基礎上，引入ln函數(shù)來弱化這種影響，利用百分比來表示節(jié)點對不同鄰居的影響程度，使節(jié)點的標簽對各個鄰居節(jié)點都有一定限度的影響概率。綜上所述，節(jié)點之間影響概率CL如定義2所示。

定義2對于給定的網(wǎng)絡G=（V,E），節(jié)點之間影響概率CL值的計算如式(2)所示。

其中， CL(j→i)代表節(jié)點j到節(jié)點i的傳播概率，N(i)表示節(jié)點i的一階鄰居節(jié)點集合，Wij表示節(jié)點i與鄰居節(jié)點j之間邊的權重。

2.3 節(jié)點的設置

在種子節(jié)點的選取方面，由于網(wǎng)絡中節(jié)點的影響力具有明顯的差異性，如何有效地選取網(wǎng)絡中有影響力節(jié)點的問題顯得尤為重要，選擇網(wǎng)絡中影響力大的節(jié)點作為種子節(jié)點有利于社區(qū)的形成與劃分，能夠將信息更好地傳播到網(wǎng)絡中，相反，如果選擇影響力較小的節(jié)點，則不利于社區(qū)的形成，從而增加迭代次數(shù)，浪費算法的執(zhí)行時間。

因此，本文在計算得到的節(jié)點的綜合影響力的基礎上，將節(jié)點綜合影響力從大到小排序，構建節(jié)點影響力的排序表N，根據(jù)排序表N選取一定比例數(shù)據(jù)組成種子節(jié)點集合Seed。

在節(jié)點標簽的設置上，本文利用標簽向量來更詳細地描述節(jié)點的社區(qū)類別信息。一方面，通過矢量化對節(jié)點的社區(qū)標簽類別進行表示，這樣在每一次的迭代中保證節(jié)點可能的社區(qū)類別標簽都能夠得到更新。如圖4所示，節(jié)點3處于淡藍色社區(qū)和紫色社區(qū)重疊地方，且兩個社區(qū)對它的影響相差不大時，傳統(tǒng)的標簽傳播方法在每一次迭代時只選擇淡藍色或者紫色一種作為類別，具有一定的絕對性，在使用矢量化表示后，3號節(jié)點社區(qū)類別標簽則可以表示為（0.45,0.55）的形式，在每一次迭代時都能夠對兩個社區(qū)類別標簽同時進行更新。

圖4 具有兩個社區(qū)的網(wǎng)絡示意 Figure 4 Schematic diagram of a network with two communities

此外，經(jīng)過若干次迭代后，兩個社區(qū)對更新節(jié)點的影響差距逐漸變大，使節(jié)點的社區(qū)類別的確定更加明確。另外，節(jié)點社區(qū)類別的矢量化表示有利于提高算法的執(zhí)行效率。

綜上，節(jié)點社區(qū)類別標簽的設置策略如下：設網(wǎng)絡節(jié)點的集合為，其中，m(m≤n)個節(jié)點為已知標簽節(jié)點，(n?m)個節(jié)點為未知標簽節(jié)點，節(jié)點類別數(shù)c已知，定義一個c維的實值向量Ri∈Rc作為節(jié)點的標簽向量，在標簽向量初始化時，若節(jié)點vi為已知標簽的節(jié)點，且該節(jié)點屬于第p類，則Ri的第p維數(shù)值置為1，其余維度數(shù)值置為0。若節(jié)點vi為未知標簽的節(jié)點，則Ri所有維度數(shù)值均置為?1，于是，問題轉化為如何利用(vi,Ri)(1 ≤i≤m)的 數(shù) 據(jù) 預 測{vm+1, … ,vn}的標簽數(shù)據(jù){Rm+1, … ,Rn}。

將輸入的數(shù)據(jù)進行處理，計算節(jié)點更新順序、影響概率、節(jié)點標簽等信息，并利用矩陣向量的形式進行存儲，TS-LPA的數(shù)據(jù)預處理過程如下。

算法1TS-LPA的數(shù)據(jù)預處理過程

輸入圖G的鄰接矩陣A，部分節(jié)點的標簽

label

輸出節(jié)點之間影響概率值CL，節(jié)點種子集合Seed，排序后節(jié)點影響力V_Sort，節(jié)點的初始化標簽向量R_init

1) V_node = Node(A) //計算節(jié)點的影響力Node值

2) V_Sort = Sort(V_node) //根據(jù)節(jié)點重要性對節(jié)點進行

3) Seed = seedChoice(label,V_Sort)//選擇種子節(jié)點

4) for ?v∈V

5) for ?u∈N(v) //對于節(jié)點v的所有鄰居節(jié)點

2.4 節(jié)點標簽的分階段更新策略

LPA的不穩(wěn)定性表現(xiàn)在算法更新過程中更新標簽的選擇，為了更好地利用鄰居節(jié)點標簽類別來進行標簽更新，本文提出了兩階段更新 策略。

第一階段：網(wǎng)絡中每一個節(jié)點都有一個標簽向量Ri，代表節(jié)點對于各個類別的隸屬度，當算法開始傳播的時候，待更新節(jié)點的所有鄰居節(jié)點都對該節(jié)點的標簽產(chǎn)生影響，鄰居節(jié)點的標簽向量Ri與節(jié)點之間的影響概率CL共同影響待更新節(jié)點的標簽。設Li為第一階段節(jié)點更新后的標簽向量。第一階段節(jié)點標簽向量更新式如式(3)所示。

其中，N(i)表示待更新節(jié)點i的一階鄰居節(jié)點的集合，C L(j→i)表示節(jié)點j到節(jié)點i的傳播概率，Rj表示節(jié)點j的標簽預測向量。

第二階段：在標簽更新時，待更新節(jié)點的鄰居節(jié)點標簽大部分是未知標簽，若一個節(jié)點的社區(qū)類別是不確定的，那么對其鄰居節(jié)點的標簽影響說服力較弱。因此，為了減輕未知鄰居節(jié)點對待更新節(jié)點的支配程度，除鄰居節(jié)點的影響外，加入附近已知標簽節(jié)點對待更新節(jié)點的影響，共同完成節(jié)點的標簽更新。具體策略如下：以待更新節(jié)點為起點，應用廣度優(yōu)先搜索方式逐層向外搜索，直到出現(xiàn)已知標簽節(jié)點所在層次，或查詢超過3層時終止搜索。搜索到已知標簽集合K，在集合K中標簽數(shù)量最多的社區(qū)類別c1，會在第一階段標簽更新的基礎上修改Li。因為在標簽迭代更新過程中，搜索到的社區(qū)類別c1對待更新節(jié)點的影響較大，為了體現(xiàn)這種影響力，本文將β的取值設為0.5～1。第一階段節(jié)點標簽預測向量更新如式(4)所示。

其中，Ri表示最終節(jié)點i的標簽預測向量，z= 1,… ,c，Ri(z)表示節(jié)點i對第z個社區(qū)的隸屬度，Li表示第一階段節(jié)點i的標簽預測向量，c表示社區(qū)類別的數(shù)量。

2.5 節(jié)點迭代傳播目標函數(shù)設置

定義一個函數(shù)Yf，該函數(shù)旨在停止算法的迭代，當函數(shù)Yf的值變化很小時，節(jié)點標簽趨于穩(wěn)定，算法迭代停止。函數(shù)Yf如式(5)所示。

Ri(t)表示節(jié)點i當前第t次迭代的標簽預測向量，Ri(t?1)表示節(jié)點i第t?1次迭代的標簽預測向量，n表示節(jié)點集合V中節(jié)點的數(shù)量。

利用算法預處理階段得到的數(shù)據(jù)，進行算法的標簽傳播。標簽迭代傳播后，每個節(jié)點被分配到對應的標簽，從而確定社區(qū)檢測的結果。TS-LPA的標簽傳播過程如算法2所示。

算法2TS-LPA的標簽傳播過程

輸入網(wǎng)絡G=(V,E)，最大迭代次數(shù)t_ max，圖G的鄰接矩陣A，節(jié)點之間影響概率值CL，網(wǎng)絡種子集合Seed，排序后節(jié)點影響力V_Sort，節(jié)點的初始化標簽向量 R_init

輸出網(wǎng)絡中最終的社區(qū)劃分結果P= {P1,P2,… ,Pn}

2.6 算法復雜度分析

對于給定的網(wǎng)絡G= (V,E)，其中V表示網(wǎng)絡的節(jié)點集，E表示網(wǎng)絡的邊集。大小為n，大小為m，TS-LPA的時間復雜度分析如下。

計算網(wǎng)絡中節(jié)點重要性Node(i)的時間復雜度是O(m+n)，節(jié)點重要性排序的時間復雜度為O(nlogn)，集合V的每個節(jié)點標簽預測向量的初始化時間復雜度為O(n)，迭代一次的時間復雜度為O(n)，則迭代t次時間復雜度為O(nt)，有約束的廣度優(yōu)先搜索的時間復雜度為O( 3ndi)，其中di表示節(jié)點i的度數(shù)。綜合的時間復雜度為O(m+n( 3 +t+ 3di) +nlogn)。

3 實驗與分析

為了驗證算法的性能，本文在真實數(shù)據(jù)集和人工數(shù)據(jù)集上分別進行了實驗。實驗環(huán)境是Windows10 64位版本，處理器為intel Core i5-8250U CPU @ 1.8 GHz，內(nèi)存容量為8 GB，編程語言采用Python。

3.1 評價指標

標準化互信息[24]是一種衡量社區(qū)檢測算法結果與真實網(wǎng)絡在結構上是否一致的方法。通過比較社區(qū)檢測的結果與標準社區(qū)結構的相似度，從而衡量社區(qū)檢測的質量，對于已知社區(qū)結構的社區(qū)檢測，可以衡量算法劃分社區(qū)與標準社區(qū)之間的相似度。

對于給定的網(wǎng)絡G= (V,E)，網(wǎng)絡G劃分為kt個社區(qū)，在每個社區(qū)i中，每個節(jié)點v都被分配了標簽lvp=i，則真實劃分T的熵計算 如下：

其中，kp代表預測社區(qū)檢測P的社區(qū)個數(shù)，代表真實社區(qū)i和預測社區(qū)j中相同節(jié)點的個數(shù)。經(jīng)過最大值(H(T) +H(P))/2正規(guī)化得到標準互信息量公式為

3.2 基于真實數(shù)據(jù)集實驗分析

本文實驗采用5種標準的真實網(wǎng)絡數(shù)據(jù)集對數(shù)據(jù)進行社區(qū)的劃分，選取的數(shù)據(jù)集分別是Karate、Dolphins、Football、Political blogs共4種公認的真實網(wǎng)絡數(shù)據(jù)集和傳銷組織數(shù)據(jù)集（MLM Organization）。其參數(shù)如表1所示。

表1 真實網(wǎng)絡數(shù)據(jù)集參數(shù)Table 1 Real network data set parameters

將TS-LPA與經(jīng)典的LPA、LPAM、LPAM+、半監(jiān)督社區(qū)檢測算法（S_LPA[25]、KLPA[26]）進行比較，對于LPA和S_LPA兩種不穩(wěn)定的算法，將算法運行10次后求其平均NMI值。通過表2可以看出，TS-LPA與基于LPA的改進算法有更好的社區(qū)結構劃分能力。在小規(guī)模的社區(qū)檢測中，TS-LPA的算法性能與最優(yōu)的算法相差不大，在涉及節(jié)點數(shù)量較多的社區(qū)檢測中，TS-LPA表現(xiàn)出較強的社區(qū)檢測能力，從而能夠有效地對節(jié)點所屬社區(qū)進行判斷，該算法利用節(jié)點的重要性和種子節(jié)點等因素，有效提高了社區(qū)節(jié)點劃分的質量，并且極大地消除了隨機性，具有更好的穩(wěn)定性。

表2 真實數(shù)據(jù)集實驗數(shù)據(jù)比較Table 2 Comparison of experimental data of real data sets

TS-LPA在Dolphins數(shù)據(jù)集、Football數(shù)據(jù)集，以及MLM Organization數(shù)據(jù)集上的社區(qū)劃分結果如圖5所示。在圖5(a)中，Dolphins劃分為兩個社區(qū)，社區(qū)的結構相對清晰，社區(qū)成員劃分與真實情況總體一致。在圖5(b)中，F(xiàn)ootball數(shù)據(jù)集被劃分為12個社區(qū)，藍色的80、82、90這3個節(jié)點為已知節(jié)點，由于這3個節(jié)點所屬社區(qū)屬于一個管理組社區(qū)，負責對其他球隊社區(qū)進行組織與管理，該社區(qū)成員與各個社區(qū)聯(lián)系比較緊密，所以社區(qū)檢測的識別度較小，無法形成小規(guī)模社區(qū)。但是除此之外其余社區(qū)檢測結構比較清晰，根據(jù)節(jié)點的標簽可以判斷，實驗結果各個社區(qū)的組成部分與真實情況社區(qū)的組成部分具有較高的一致性。在圖5(c)中，MLM Organization數(shù)據(jù)集被劃分為10個社區(qū)，由于傳銷組織數(shù)據(jù)網(wǎng)絡多為自我中心網(wǎng)絡，多數(shù)下線以頭目為中心組成傳銷組織團伙，所以易形成網(wǎng)絡社區(qū)。非重要傳銷成員之間，社區(qū)的結構比較清晰。

圖5 TS-LPA在3個真實數(shù)據(jù)集劃分結果 Figure 5 TS-LPA partition results in three real data sets

3.3 基于人工數(shù)據(jù)集實驗分析

為了測試本文算法在不同網(wǎng)絡中的適用性，本文選取人工LFR基準網(wǎng)絡進行實驗分析，并與半監(jiān)督社區(qū)檢測算法（S_LPA、KLPA）進行比較，選取NMI值作為社區(qū)檢測準確度的評價標準，對于不穩(wěn)定S_LPA，計算10次求平均值。人工合成網(wǎng)絡分別包含1 000個節(jié)點和2 000個節(jié)點，具體參數(shù)如表3所示。其中，N代表網(wǎng)絡中節(jié)點的數(shù)量，K代表網(wǎng)絡的平均度值，mu代表網(wǎng)絡混合參數(shù)，表示不同社區(qū)節(jié)點邊數(shù)占網(wǎng)絡總邊數(shù)的比例，mu取值為0～1。mu值越小，人工合成的社區(qū)結構越清晰；mu值越大，人工合成的社區(qū)結構越模糊。maxk代表網(wǎng)絡中最大度值，minc和maxc分別表示網(wǎng)絡中社區(qū)結構的最小值和最大值。在不同mu值下，各個算法實驗結果如圖6和圖7所示。

圖6 當N = 1 000時不同算法數(shù)據(jù)比較 Figure 6 Comparison of data of different algorithms when N = 1 000

圖7 當N = 2 000時不同算法數(shù)據(jù)比較 Figure 7 Comparison of data of different algorithms when N = 2 000

表3 人工合成網(wǎng)絡參數(shù)Table 3 Artificial synthesis network parameters

由圖6和圖7可以看出，當mu<0.5時，網(wǎng)絡社區(qū)的結構比較清晰，3種算法對社區(qū)的劃分有較高的準確性。當mu>0.5時，網(wǎng)絡社區(qū)的結構模糊，3種算法的社區(qū)檢測的準確性開始下降。當N=1 000，mu>0.5時，TS-LPA對社區(qū)檢測的NMI值明顯優(yōu)于其余兩種算法，當N=2 000，mu>0.55時，TS-LPA整體高于其余兩種算法的NMI值，但不明顯?？傮w來看，TS-LPA在人工合成網(wǎng)絡的性能優(yōu)于KLPA和S_LPA。

3.4 參數(shù)的設置

TS-LPA引入?yún)?shù)β來確定種子節(jié)點在更新過程中標簽影響能力的大小，最終影響社區(qū)結構的劃分，將TS-LPA在Political blogs數(shù)據(jù)集和nc1（mu = 0.2）數(shù)據(jù)集選取不同的β參數(shù)進行實驗。實驗選用NMI值作為評價的標準。實驗結果如圖8所示，當β選取在特殊的值時，社區(qū)檢測的NMI值相對較高。在不同的社交網(wǎng)絡中，由于種子集合的選取和網(wǎng)絡拓撲結構的不同，已知標簽節(jié)點對未知標簽節(jié)點的影響程度有所差異，因此，不同的網(wǎng)絡結構需要不同的參數(shù)進行對應。

圖8 不同數(shù)據(jù)集不同的β參數(shù)實驗結果 Figure 8 Different β parameter detection results of different data sets

3.5 算法穩(wěn)定性試驗

LPA節(jié)點更新順序的隨機性和標簽選擇策略的隨機性造成了算法的不穩(wěn)定，多次運行的結果出現(xiàn)較大偏差。本文提出的TS-LPA在選擇節(jié)點更新順序時，通過對節(jié)點影響力進行排序來使更新順序穩(wěn)定；通過引入標簽傳播和廣度優(yōu)先的策略，確定了兩階段標簽更新策略，消除了隨機性。如圖9所示，通過將TS-LPA在4個數(shù)據(jù)集上各進行15次運算，得到各個運行結果呈現(xiàn)一條直線，通過實驗進行了驗證。

圖9 TS-LPA在不同數(shù)據(jù)集多次運行結果 Figure 9 The results of multiple runs of the TS-LPA on different data sets

4 結束語

本文在標簽傳播算法的基礎上，提出了一種基于標簽傳播的兩階段社區(qū)檢測算法，該算法綜合考慮節(jié)點的局部影響力和全局影響力來計算節(jié)點在網(wǎng)絡中的綜合影響力，使節(jié)點影響力的量化更加具體。此外，所提算法引入節(jié)點影響力信息和邊的權重信息來計算節(jié)點之間的影響概率，使其更接近真實網(wǎng)絡。在傳播迭代過程中，通過未知節(jié)點鄰域內(nèi)已知節(jié)點的信息，實現(xiàn)對網(wǎng)絡中節(jié)點的社區(qū)檢測，實現(xiàn)標簽傳播過程中標簽的兩階段調(diào)整，提高社區(qū)檢測的準確度。實驗結果證明，TS-LPA能夠有效提高社區(qū)檢測的準確性和穩(wěn)定性。

在接下來的工作中，將進一步考慮引入方向等信息和融合其他經(jīng)典的算法來實現(xiàn)社區(qū)檢測，提高社區(qū)檢測的穩(wěn)定性；對算法進行優(yōu)化，減小算法運行的時間和空間復雜度。