基于標(biāo)簽傳播的兩階段社區(qū)檢測(cè)算法

孫學(xué)良，王巍，黃俊恒，辛國(guó)棟，王佰玲

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

0 引言

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

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

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

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

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

2) 結(jié)合網(wǎng)絡(luò)局部拓?fù)浣Y(jié)構(gòu)信息，本文采用擴(kuò)展鄰域的思想對(duì)節(jié)點(diǎn)的中心性進(jìn)行度量，并在此基礎(chǔ)上提出一種新的評(píng)價(jià)指標(biāo)來衡量節(jié)點(diǎn)之間的影響概率。

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

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

1 相關(guān)工作

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

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

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

圖1 標(biāo)簽傳播算法示意 Figure 1 Schematic diagram of label propagation algorithm

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

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

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

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

2 TS-LPA

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

1) 構(gòu)建網(wǎng)絡(luò)圖，利用擴(kuò)展鄰域核心度的方法來計(jì)算節(jié)點(diǎn)的重要性，并根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，綜合利用鄰居信息得到節(jié)點(diǎn)的影響力。

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

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

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

2.1 節(jié)點(diǎn)影響力計(jì)算

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

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

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

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

2.2 節(jié)點(diǎn)之間影響概率的計(jì)算

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

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

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

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

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

2.3 節(jié)點(diǎn)的設(shè)置

在種子節(jié)點(diǎn)的選取方面，由于網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力具有明顯的差異性，如何有效地選取網(wǎng)絡(luò)中有影響力節(jié)點(diǎn)的問題顯得尤為重要，選擇網(wǎng)絡(luò)中影響力大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)有利于社區(qū)的形成與劃分，能夠?qū)⑿畔⒏玫貍鞑サ骄W(wǎng)絡(luò)中，相反，如果選擇影響力較小的節(jié)點(diǎn)，則不利于社區(qū)的形成，從而增加迭代次數(shù)，浪費(fèi)算法的執(zhí)行時(shí)間。

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

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

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

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

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

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

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

輸入圖G的鄰接矩陣A，部分節(jié)點(diǎn)的標(biāo)簽

label

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

1) V_node = Node(A) //計(jì)算節(jié)點(diǎn)的影響力Node值

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

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

4) for ?v∈V

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

2.4 節(jié)點(diǎn)標(biāo)簽的分階段更新策略

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

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

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

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

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

2.5 節(jié)點(diǎn)迭代傳播目標(biāo)函數(shù)設(shè)置

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

Ri(t)表示節(jié)點(diǎn)i當(dāng)前第t次迭代的標(biāo)簽預(yù)測(cè)向量，Ri(t?1)表示節(jié)點(diǎn)i第t?1次迭代的標(biāo)簽預(yù)測(cè)向量，n表示節(jié)點(diǎn)集合V中節(jié)點(diǎn)的數(shù)量。

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

算法2TS-LPA的標(biāo)簽傳播過程

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

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

2.6 算法復(fù)雜度分析

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

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

3 實(shí)驗(yàn)與分析

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

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

標(biāo)準(zhǔn)化互信息[24]是一種衡量社區(qū)檢測(cè)算法結(jié)果與真實(shí)網(wǎng)絡(luò)在結(jié)構(gòu)上是否一致的方法。通過比較社區(qū)檢測(cè)的結(jié)果與標(biāo)準(zhǔn)社區(qū)結(jié)構(gòu)的相似度，從而衡量社區(qū)檢測(cè)的質(zhì)量，對(duì)于已知社區(qū)結(jié)構(gòu)的社區(qū)檢測(cè)，可以衡量算法劃分社區(qū)與標(biāo)準(zhǔn)社區(qū)之間的相似度。

對(duì)于給定的網(wǎng)絡(luò)G= (V,E)，網(wǎng)絡(luò)G劃分為kt個(gè)社區(qū)，在每個(gè)社區(qū)i中，每個(gè)節(jié)點(diǎn)v都被分配了標(biāo)簽lvp=i，則真實(shí)劃分T的熵計(jì)算 如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 參數(shù)的設(shè)置

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

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

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

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

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

4 結(jié)束語

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

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