基于加權(quán)聚類集成的標(biāo)簽傳播算法

張美琴，白亮，王俊斌

現(xiàn)實(shí)世界中存在各種各樣的復(fù)雜系統(tǒng)，網(wǎng)絡(luò)則是這些系統(tǒng)的普遍存在形式，如人際關(guān)系網(wǎng)，因特網(wǎng)、大型電力網(wǎng)格等。為了能清晰地發(fā)現(xiàn)網(wǎng)絡(luò)中的信息，需要挖掘網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。 社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特性，整個(gè)網(wǎng)絡(luò)是由若干個(gè)“社區(qū)”構(gòu)成的，每個(gè)社區(qū)內(nèi)部的節(jié)點(diǎn)之間的連接相對非常緊密，而各個(gè)社區(qū)之間的連接卻比較稀疏。利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，能更準(zhǔn)確地發(fā)現(xiàn)社區(qū)。網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)，有助于更好地了解社區(qū)結(jié)構(gòu)、理解網(wǎng)絡(luò)的功能和特性、預(yù)測復(fù)雜網(wǎng)絡(luò)的行為，在社會網(wǎng)絡(luò)、信息推薦、精準(zhǔn)營銷等領(lǐng)域都有很大的應(yīng)用價(jià)值。

目前提出的代表性社區(qū)發(fā)現(xiàn)算法有潛在空間算法[1]、譜聚類算法[2-3]、模塊最大化算法[4-8]、標(biāo)簽傳播算法等，根據(jù)不同的科學(xué)需要，這些算法有不同的社區(qū)定義或類定義[9]。其中，由Raghavan等[10]在2007年提出的標(biāo)簽傳播算法(LPA)由于其擁有線性時(shí)間復(fù)雜度而被廣泛應(yīng)用于處理大規(guī)模網(wǎng)絡(luò)。然而，該算法中每個(gè)節(jié)點(diǎn)的標(biāo)簽更新取決于其鄰居節(jié)點(diǎn)，更新效果受節(jié)點(diǎn)初始輸入和標(biāo)簽更新順序的影響。因此LPA算法的最終結(jié)果存在不確定性，影響了社區(qū)劃分的準(zhǔn)確性和穩(wěn)定性?；贚PA結(jié)果的不穩(wěn)定性，眾多學(xué)者提出了對LPA 的改進(jìn)算法[11?18]。例如，Barber等[11]在 2009年提出使用模塊度最大化的變體作為約束的LPA算法(LPAm)，該算法將標(biāo)簽傳播算法轉(zhuǎn)化為等價(jià)優(yōu)化問題處理； Liu等[12]在2010年針對LPAm算法可能會出現(xiàn)社區(qū)劃分陷入局部極大值的問題，提出一種改進(jìn)的標(biāo)簽傳播算法(LPAm+)，其核心是將LPAm算法與多步貪婪凝聚算法(MSG)融合，最大限度地減少模塊空間，避免出現(xiàn)局部最大值； Xie等在2011年發(fā)表的文獻(xiàn)[13]中提出了針對提高社區(qū)檢測速度和提高社區(qū)質(zhì)量的改進(jìn)LPA算法； He等[14]在2014年使用了PageRank來衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，提出了基于節(jié)點(diǎn)重要性的LPA算法； Sun等[15]在2015年提出基于中心的標(biāo)簽傳播算法(CenLP)，通過高密度鄰居節(jié)點(diǎn)的相似性使節(jié)點(diǎn)按特定順序更新標(biāo)簽； Li等[16]在2017年提出改進(jìn)的LPA算法Stepping LPA-S算法，它通過模塊度和目標(biāo)函數(shù)DN來度量節(jié)點(diǎn)或子網(wǎng)的相似性，其標(biāo)簽通過相似性進(jìn)行傳播，最終獲得了比LPA更準(zhǔn)確的結(jié)果。

雖然已有多種改進(jìn)的LPA算法被提出，但依然存在穩(wěn)定性和精確性不高的問題[17?18]。聚類集成技術(shù)正是解決聚類算法結(jié)果不穩(wěn)定和不精確的重要方法之一。目前，多種聚類集成技術(shù)也已得到發(fā)展[19?21]。因此，本文通過將聚類集成技術(shù)與標(biāo)簽傳播算法融合，提出了基于加權(quán)聚類集成的標(biāo)簽傳播算法。該算法通過引入模塊度來評估每次LPA結(jié)果的重要性，加強(qiáng)了每個(gè)基聚類的有效性，最后采用聚類集成技術(shù)實(shí)現(xiàn)提高社區(qū)發(fā)現(xiàn)結(jié)果的穩(wěn)定性和準(zhǔn)確性。

1 基于加權(quán)聚類集成的標(biāo)簽傳播算法

1.1 標(biāo)簽傳播算法(LPA)

標(biāo)簽傳播算法(LPA)的核心思想是每個(gè)節(jié)點(diǎn)的標(biāo)簽通過其出現(xiàn)次數(shù)最多的鄰居節(jié)點(diǎn)的標(biāo)簽來決定自身的標(biāo)簽，通過不斷迭代，節(jié)點(diǎn)的標(biāo)簽變化達(dá)到穩(wěn)定后，將最終具有相同標(biāo)簽的節(jié)點(diǎn)劃分為一個(gè)社區(qū)，完成社區(qū)劃分。其最大的特點(diǎn)是簡單、高效，缺點(diǎn)是每次迭代結(jié)果不穩(wěn)定，準(zhǔn)確率不高。在文獻(xiàn)[10]中給出了該算法的具體描述如下。

1)為所有節(jié)點(diǎn)初始化一個(gè)唯一的標(biāo)簽，每個(gè)標(biāo)簽代表一個(gè)社區(qū)。

2)產(chǎn)生隨機(jī)遍歷順序遍歷所有節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)選擇其出現(xiàn)次數(shù)最多的鄰居節(jié)點(diǎn)標(biāo)簽來更新自身的標(biāo)簽，以此達(dá)到標(biāo)簽的傳播。

3)若存在節(jié)點(diǎn)的鄰居節(jié)點(diǎn)標(biāo)簽數(shù)出現(xiàn)多個(gè)最大值，則隨機(jī)選其中一個(gè)最大值所對應(yīng)的標(biāo)簽來更新該節(jié)點(diǎn)的標(biāo)簽。重復(fù)2)，直到標(biāo)簽更新穩(wěn)定，停止迭代。

4)將具有相同標(biāo)簽的節(jié)點(diǎn)劃分為一個(gè)社區(qū)。

該算法的時(shí)間復(fù)雜度為O(n+m)O(n+m)，其中，n代表為結(jié)點(diǎn)分配標(biāo)簽的時(shí)間，m代表每次迭代更新的時(shí)間。

1.2 基于加權(quán)聚類集成的標(biāo)簽傳播算法

在介紹本文提出的新算法之前，首先給出網(wǎng)絡(luò)、模塊度、基聚類集、節(jié)點(diǎn)加權(quán)相似性度量等相關(guān)概念如下。

第t次運(yùn)行標(biāo)簽傳播算法所產(chǎn)生的單個(gè)聚類結(jié)果為一個(gè)基聚類，將多個(gè)標(biāo)簽傳播算法的結(jié)果融合來代替單個(gè)標(biāo)簽傳播算法的結(jié)果，使用聚類集成技術(shù)從結(jié)果集中發(fā)現(xiàn)最一致的結(jié)果。然而，聚類集成的結(jié)果會受到單個(gè)基聚類質(zhì)量的影響，為了提高聚類結(jié)果的穩(wěn)定性，因此提出加權(quán)相似性度量。

基于以上定義，提出基于加權(quán)聚類集成的標(biāo)簽傳播算法。 用LPA算法對復(fù)雜網(wǎng)絡(luò)進(jìn)行次聚類，聚類產(chǎn)生的結(jié)果形成一個(gè)的基聚類集矩陣，然后根據(jù)定義4融入模塊度在基聚類集上求出一個(gè)維的節(jié)點(diǎn)加權(quán)相似性矩陣，最后通過層次聚類算法產(chǎn)生最終的結(jié)果。其聚類過程如圖1所示。

圖1 算法框架Fig. 1 The framework of the proposed algorithm

具體算法步驟如下：

2 實(shí)驗(yàn)分析

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

為了驗(yàn)證本文提出的算法的有效性，選取了5個(gè)不同規(guī)模的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，分別為football、dolphins、karate、web、word 數(shù)據(jù)集。其中football數(shù)據(jù)集是由美國橄欖球聯(lián)賽中球隊(duì)的比賽關(guān)系構(gòu)成的網(wǎng)絡(luò)，共包含115支球隊(duì)。Dolphins數(shù)據(jù)集是由新西蘭的一個(gè)海豚群體組成的海豚關(guān)系網(wǎng)，網(wǎng)絡(luò)中的邊表示兩只海豚之間的頻繁接觸次數(shù)。Karate數(shù)據(jù)集是一個(gè)由34個(gè)空手道俱樂部成員之間的關(guān)系構(gòu)成的社會網(wǎng)絡(luò)，網(wǎng)絡(luò)中的邊表示兩個(gè)俱樂部成員經(jīng)常出現(xiàn)在俱樂部活動之外的其他場合的次數(shù)。Web數(shù)據(jù)集是某網(wǎng)站上所有網(wǎng)頁構(gòu)成的關(guān)系網(wǎng)，節(jié)點(diǎn)代表網(wǎng)頁，邊代表超鏈接。Word數(shù)據(jù)集是名詞形容詞搭配網(wǎng)絡(luò)。數(shù)據(jù)集的信息描述如表1所示。

表 1 數(shù)據(jù)集描述Table 1 Description of network data sets

2.2 評價(jià)指標(biāo)

本文使用標(biāo)準(zhǔn)互信息(normalized mutual information， NMI)和調(diào)整蘭德系數(shù)(adjusted rand Index，ARI)來評價(jià)最終聚類質(zhì)量。

標(biāo)準(zhǔn)互信息(NMI)和調(diào)整蘭德系數(shù)(ARI)常常用于社區(qū)劃分質(zhì)量的評價(jià)，能有效衡量給定社區(qū)劃分結(jié)果與真實(shí)網(wǎng)絡(luò)劃分的相似程度。NMI的定義為

ARI的定義為

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

為了測試新算法的有效性，使其分別與5個(gè)現(xiàn)有的LPA的改進(jìn)算法在真實(shí)數(shù)據(jù)集上進(jìn)行了比較測試，這些LPA的改進(jìn)算法包括LPA[10]、LPA_S[16]、LPAm[11]、LPAm+[12]、BGLL[18]。分別從NMI和ARI兩個(gè)評價(jià)指標(biāo)將新算法與經(jīng)典算法進(jìn)行了比較，每個(gè)算法在每個(gè)數(shù)據(jù)集上都運(yùn)行了100次，實(shí)驗(yàn)結(jié)果如表2～3所示。通過對實(shí)驗(yàn)結(jié)果的對比分析顯示，新算法的實(shí)驗(yàn)效果在football、dolphins、web、word 數(shù)據(jù)集上都有明顯的提高，即其社區(qū)劃分更接近于真實(shí)社區(qū)的劃分，尤其是在 dolphins 數(shù)據(jù)集，該算法的效果較其他算法高出10%多。雖然在karate數(shù)據(jù)集上新算法的實(shí)驗(yàn)結(jié)果并非最高，但也表明新算法在大部分?jǐn)?shù)據(jù)集上的表現(xiàn)仍然具有很大優(yōu)勢。同時(shí)，對于算法本身的性能的測評中，由于該算法只涉及因運(yùn)行LPA算法次數(shù)的差異所形成的基聚類集的維度的不同對算法最終結(jié)果所造成的影響，因此本文也對運(yùn)行不同次標(biāo)簽傳播算法得出的最終社區(qū)劃分結(jié)果進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，隨著運(yùn)行次數(shù)的增多，社區(qū)劃分結(jié)果越穩(wěn)定，且運(yùn)行到一定次數(shù)時(shí)，社區(qū)劃分效果均能趨于平穩(wěn)。綜上所述，本文提出的基于加權(quán)聚類集成的標(biāo)簽傳播算法較其他算法在NMI和ARI上都有良好的表現(xiàn)，且算法本身表現(xiàn)也收斂，因此新算法能在社區(qū)劃分的結(jié)果上更接近于實(shí)際社區(qū)劃分情況，提高了社區(qū)發(fā)現(xiàn)的精確性。

表 2 不同算法的 NMI值比較Table 2 Clustering results of different algorithms with respect to NMI

表 3 不同算法的 ARI值比較Table 3 Clustering results of different algorithms with respect to ARI

3 結(jié)束語

本文主要利用聚類集成技術(shù)對LPA進(jìn)行了改進(jìn)，提出了基于加權(quán)聚類集成的標(biāo)簽傳播算法。該算法首先執(zhí)行多次LPA產(chǎn)生多個(gè)標(biāo)簽傳播結(jié)果作為基聚類集，并計(jì)算出每次LPA結(jié)果的模塊度值作為對應(yīng)基聚類的權(quán)重，然后計(jì)算出融入權(quán)值后的節(jié)點(diǎn)相似性矩陣，最后采用層次聚類方法得到最終的社區(qū)劃分結(jié)果。在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，新算法在NMI和ARI兩個(gè)評價(jià)指標(biāo)上效果都有所提高，表明新算法可以獲得更好的社區(qū)發(fā)現(xiàn)結(jié)果，提高了社區(qū)發(fā)現(xiàn)的精確性。