融合Leader Rank和標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法?

翟鎮(zhèn)新 於躍成 谷 雨

（江蘇科技大學(xué)計算機學(xué)院 鎮(zhèn)江 212000）

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，信息量成爆炸式增長以及人與人之間的關(guān)系不斷地變化，社會網(wǎng)絡(luò)的規(guī)模也越來越大。社會網(wǎng)絡(luò)具有信息大、無標(biāo)識、社區(qū)結(jié)構(gòu)等特性，其中社區(qū)結(jié)構(gòu)是社會網(wǎng)絡(luò)的基本性質(zhì)，即一個網(wǎng)絡(luò)可以分為若干個社區(qū)，社區(qū)內(nèi)節(jié)點相似度較高且連接相對緊密，社區(qū)間節(jié)點相似度較低且相對稀疏。對社區(qū)的研究有很多重要的意義，例如可以找到用戶組成的群組，投放相關(guān)的商業(yè)廣告；挖掘群組的最新討論話題，將其快速推薦給感興趣的用戶；預(yù)測社會網(wǎng)絡(luò)的未來變化。這些價值實現(xiàn)的前提，就是社區(qū)的發(fā)現(xiàn)。

為了能夠?qū)崿F(xiàn)社區(qū)的劃分，近代學(xué)者提出了很多優(yōu)秀的社區(qū)發(fā)現(xiàn)方法［1～5］，如基于隨機游走的方法、基于結(jié)構(gòu)相似性度量的聚合方法及圖分割方法等，這些算法主要依據(jù)網(wǎng)絡(luò)結(jié)構(gòu)進行劃分，在用于數(shù)據(jù)規(guī)模較大的社會網(wǎng)絡(luò)時，迭代周期較長，算法復(fù)雜度較高。因此，更多學(xué)者將注重點放在提高社區(qū)的發(fā)現(xiàn)效率及穩(wěn)定性上。

2007年，Raghavan等［6］首次將標(biāo)簽傳播算法（LPA）運用到復(fù)雜的社會網(wǎng)絡(luò)中用于社區(qū)發(fā)現(xiàn)，社區(qū)的發(fā)現(xiàn)效率也因此得到了顯著的提高。LPA無需預(yù)先知道社區(qū)的個數(shù)，僅依據(jù)于社會網(wǎng)絡(luò)的自身結(jié)構(gòu)發(fā)現(xiàn)社區(qū)，算法復(fù)雜度較低，被廣泛運用于大規(guī)模的社會網(wǎng)絡(luò)中。但是LPA在每一的迭代過程中存在著隨機性，致使社區(qū)發(fā)現(xiàn)的結(jié)果不一樣，穩(wěn)定性較差。

LPA產(chǎn)生隨機性的主要起因，沒有充分考慮節(jié)點自身的影響力以及將所有節(jié)點平等看待。本文引入LeaderRank［7］算法計算節(jié)點的影響力，根據(jù)LeaderRank計算的影響力值排序并采取一定的選取策略，找出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點，在網(wǎng)絡(luò)節(jié)點初始化時給這些關(guān)鍵節(jié)點賦予唯一的標(biāo)簽，節(jié)點的更新順序?qū)⒏鶕?jù)其LeaderRank值由高到低進行更新，然后在標(biāo)簽傳播更新的過程中，考慮節(jié)點之間的傳播特性，不斷迭代更新，直到大部分節(jié)點標(biāo)簽不在發(fā)生變化或者迭代次數(shù)達到最大，即完成社區(qū)發(fā)現(xiàn)。

2 相關(guān)工作

2.1 標(biāo)簽傳播算法

標(biāo)簽傳播算法（LPA）的基本思想：一個給定的節(jié)點x擁有n個鄰居節(jié)點x1，x2，…，xn，其鄰居節(jié)點都有唯一的標(biāo)簽，給定節(jié)點x的標(biāo)簽將由其鄰居節(jié)點的標(biāo)簽信息所決定。標(biāo)簽傳播算法可簡述為以下幾點。

1）節(jié)點標(biāo)簽初始化時，為每個節(jié)點賦予唯一的標(biāo)簽，用來標(biāo)識節(jié)點所在的社區(qū)。

2）對圖中所有的節(jié)點開始迭代更新，節(jié)點標(biāo)簽將會接受鄰居節(jié)點的標(biāo)簽信息，選擇鄰居節(jié)點中標(biāo)簽數(shù)量最多的標(biāo)簽。當(dāng)多個標(biāo)簽數(shù)量相同時，那么將會隨機選取其中一個標(biāo)簽作為更新節(jié)點的標(biāo)簽。經(jīng)過多次迭代，使得圖中所有的節(jié)點趨于穩(wěn)定，社區(qū)結(jié)構(gòu)也將顯現(xiàn)出來

3）根據(jù)每個節(jié)點的標(biāo)簽，將所有的節(jié)點進行劃分，標(biāo)簽相同的節(jié)點將劃分為同一社區(qū)。

圖1為標(biāo)簽傳播過程的一個簡單案例，由圖可以明顯看出，標(biāo)簽為a的節(jié)點在接受鄰居節(jié)點的標(biāo)簽信息后，由于標(biāo)簽c的節(jié)點數(shù)量為2，根據(jù)上述原理，標(biāo)簽為a的節(jié)點將更新為標(biāo)簽c。

上述算法的有兩種更新方式：同步更新和異步更新。采用同步更新將會在二分圖上產(chǎn)生循環(huán)震蕩的問題。如圖2所示，假設(shè)在t-1時刻如圖2右圖所示，t時刻如圖2左圖所示，如此循環(huán)下去將無法形成真正的社區(qū)。異步更新，即目標(biāo)節(jié)點在t時刻的標(biāo)簽是依據(jù)于其部分鄰居節(jié)點在t時刻的標(biāo)簽和另一部分鄰居節(jié)點在t-1時刻的標(biāo)簽。

圖2 標(biāo)簽震蕩

標(biāo)簽傳播算法具有線性的時間復(fù)雜度，以被廣泛地運用于大規(guī)模的社會網(wǎng)絡(luò)中，但是該算法在節(jié)點更新順序和標(biāo)簽傳播過程中存在著隨機性，將會形成“無意義”的小型社區(qū)或者大型社區(qū)。

因此，為了使得標(biāo)簽傳播算法更加高效穩(wěn)定，很多研究人員進行了改進。趙卓翔等［8］在標(biāo)簽的傳播過程中綜合考慮了邊的權(quán)重、每個標(biāo)簽的個數(shù)以及需更新節(jié)點的鄰居節(jié)點的度，提出了平均權(quán)重的概念。Zhao等［9］提出了基于標(biāo)簽熵的標(biāo)簽傳播算法，通過節(jié)點標(biāo)簽的熵值決定標(biāo)簽傳播過程中節(jié)點的更新順序，消除節(jié)點更新順序中的隨機性?？敌癖虻龋?0］通過Jaccard系數(shù)計算節(jié)點之間的相似度，決定節(jié)點標(biāo)簽的更新選擇。張鑫等［11］在標(biāo)簽傳播過程中加入了鄰居節(jié)點的影響力，從而提高社區(qū)發(fā)現(xiàn)的穩(wěn)定性。馬秀等［12］利用k-shell方法計算節(jié)點的影響力，但k-shell方法只是一種粗粒度的劃分，對節(jié)點影響力的計算不夠精確。Yan等［13］利用pagerank計算節(jié)點的影響力，提出了LPAP算法，但pagerank中的“跳轉(zhuǎn)概率”影響著最終社區(qū)劃分的穩(wěn)定性。

2.2 Leader Rank算法

LeaderRank算法是對PageRank算法的優(yōu)化，和PageRank算法比較，LeaderRank無需預(yù)先設(shè)置參數(shù)，即“跳轉(zhuǎn)概率”，因此避免了參數(shù)的不同影響計算節(jié)點影響力的準確性，非常適合大規(guī)模的社交網(wǎng)絡(luò)。

LeaderRank算法被用于計算網(wǎng)絡(luò)中節(jié)點的影響力，在整個網(wǎng)絡(luò)圖中加入了一個背景節(jié)點G，該節(jié)點與原圖中的所有節(jié)點均相互鏈接，使得整個網(wǎng)絡(luò)圖成為強連通圖。

首先對背景節(jié)點G分配0個資源單位的S值（即LeaderRank值），除背景節(jié)點G以外的節(jié)點均分配1個資源單位的S值，使用式（1）計算每個節(jié)點的S值，直至達到穩(wěn)態(tài)，使用式（2）將背景節(jié)點G的S值平均分給每個節(jié)點。

其中，在初始狀態(tài)下除背景節(jié)點以外的節(jié)點si(0)=1，背景節(jié)點sg(0)=0。節(jié)點i與節(jié)點j之間存在鏈接關(guān)系，那么aij=1，反之，aij=0。kj表示節(jié)點j的度表示節(jié)點j隨機游走到節(jié)點i的概率。

其中：tc表示穩(wěn)定時刻，si(tc)表示節(jié)點i在穩(wěn)定時刻的S值，sg(tc)表示背景節(jié)點G在穩(wěn)定時刻的S值。

3 融合Leader Rank和標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)方法

本文主要是引入LeaderRank算法計算節(jié)點的影響力，從節(jié)點標(biāo)簽的初始化、節(jié)點更新順序以及傳播過程中節(jié)點標(biāo)簽的更新選擇三個方面對LPA進行改進，提出了一種新的標(biāo)簽傳播算法LLPA。整體算法流程圖如圖3所示。

圖3 算法流程圖

3.1 節(jié)點初始化

在節(jié)點初始化時，LLPA算法會選擇部分節(jié)點作為關(guān)鍵節(jié)點組成關(guān)鍵節(jié)點集，只為關(guān)鍵節(jié)點賦予唯一的標(biāo)簽，這些關(guān)鍵節(jié)點為整個網(wǎng)絡(luò)圖中影響力和重要性較大的節(jié)點。希望關(guān)鍵節(jié)點盡可能地輻射到網(wǎng)絡(luò)圖中所有的節(jié)點，和LPA相比，減少了不必要的判斷開銷，提高了效率。

將采用LeaderRank算法計算節(jié)點的S值，然后采取一定的選取策略選取出K個重要的節(jié)點。選取策略為1）關(guān)鍵節(jié)點的S值必須大于所有節(jié)點的平均值；2）統(tǒng)計每個節(jié)點的S值大于其鄰居節(jié)點S值的個數(shù)lnum，若lnum與其鄰居節(jié)點個數(shù)n的比值大于0.5。

3.2 節(jié)點更新順序

為了避免圖2所示的循環(huán)震蕩，LLPA算法將采用異步更新的方法。網(wǎng)絡(luò)圖中有著影響力大的節(jié)點，也有影響力小的節(jié)點，在節(jié)點標(biāo)簽傳播達到穩(wěn)定狀態(tài)時，影響力小的標(biāo)簽會被影響力大的標(biāo)簽所替代，若隨機優(yōu)先更新了影響力小的節(jié)點，這將是無意義的標(biāo)簽更新。

按照LeaderRank計算節(jié)點的S值，對節(jié)點進行降序排列，節(jié)點的更新順序依據(jù)于排序結(jié)果，消除了節(jié)點更新時的隨機性，減少了更新過程中無意的判斷。

3.3 標(biāo)簽傳播能力

LPA算法在傳播過程中，當(dāng)有多個數(shù)量相同的標(biāo)簽時，LPA就會隨機選取其中的一個標(biāo)簽，這將會使得社區(qū)劃分結(jié)果充滿不確定性。為了降低LPA在標(biāo)簽傳播過程中的隨機性，本文將利用標(biāo)簽傳播特性解決這一問題。

傳統(tǒng)的標(biāo)簽傳播算法在一定程度上考慮了標(biāo)簽傳播特性，即假定兩節(jié)點之間都是平等的，能直接相互傳播。在現(xiàn)實的網(wǎng)絡(luò)中，考慮到節(jié)點的影響力，根據(jù)相關(guān)參考文獻［14］，節(jié)點有標(biāo)簽傳播和標(biāo)簽接受兩種能力，影響力小的節(jié)點容易接受標(biāo)簽，影響力大的節(jié)點更容易將標(biāo)簽傳播給影響力相對小的標(biāo)簽，其如式（3）所示。

其中ki-＞j表示節(jié)點i到節(jié)點j的傳播能力的度量，ki-＞j越接近于1，節(jié)點i的影響力相對于節(jié)點j就越大，節(jié)點i的標(biāo)簽就更容易傳播到節(jié)點j；反之，ki-＞j越接近于0，節(jié)點j的影響力相對于節(jié)點i較大，節(jié)點i就不易將節(jié)點傳播到節(jié)點j。si表示節(jié)點i的影響力值（即LeaderRank值）。

在此基礎(chǔ)上，對節(jié)點i的鄰居中的每一個標(biāo)簽t計算其傳播能力，如式（4）所示。

其中C（t）表示標(biāo)簽為t的節(jié)點集合。

故對于一個節(jié)點i來說，其標(biāo)簽選擇如式（5）所示。

3.4 社區(qū)劃分算法LLPA

LLPA算法的偽代碼：

輸入：圖G（V，E）；

輸出：社區(qū)劃分結(jié)果

1）計算出網(wǎng)絡(luò)圖中的關(guān)鍵節(jié)點列表N，為每個關(guān)鍵節(jié)點賦予唯一的標(biāo)簽；

2）計算節(jié)點的S值（即LeaderRank值），將所有節(jié)點按照S值由高到低排序；

3）迭代次數(shù)t=1；

4）按照S值的排序，更新每個節(jié)點的標(biāo)簽：

5）檢查迭代次是否達到最大值或者網(wǎng)絡(luò)中的節(jié)點標(biāo)簽信息不再發(fā)生變化達到穩(wěn)定狀態(tài)。否則在t+1時刻，返回步驟3）繼續(xù)迭代更新。

LLPA算法與傳統(tǒng)的算法相比，主要考慮節(jié)點之間的傳播能力，消除標(biāo)簽傳播過程中的隨機性。選取種子節(jié)點，按順序更新節(jié)點，減少了標(biāo)簽傳播過程中無意的判斷開銷和資源的逆流。

LLPA算法的時間復(fù)雜度：選取種子節(jié)點集的時間消耗主要分為兩步。計算節(jié)點的S值（即LeaderRank值）和種子節(jié)點的選取，將這兩步的時間相加，即O(n2+n)。一次迭代過程（一次節(jié)點標(biāo)簽傳播過程）所需時間為O(m)，那么總的時間為O(n2+n+m)。

4 實驗及結(jié)果分析

實驗數(shù)據(jù)集為三個小規(guī)模的數(shù)據(jù)集和一個大規(guī)模的數(shù)據(jù)集。所有實驗均采用python語言實現(xiàn)，實驗環(huán)境為Windows10，python2.7。

4.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)集主要選取了Karate（美國空手道聯(lián)盟數(shù)據(jù)）、Football（美國橄欖球數(shù)據(jù)）、Dolphins（海豚網(wǎng)絡(luò)數(shù)據(jù)）以及C-DBLP（計算機文獻集成數(shù)據(jù)）這三個比較廣泛使用的數(shù)據(jù)集。

表1 數(shù)據(jù)集參數(shù)

4.2 社區(qū)劃分評價標(biāo)準

1）模塊度［15］。復(fù)雜網(wǎng)絡(luò)劃分社區(qū)質(zhì)量的評判指標(biāo)，其定義為假定一個復(fù)雜網(wǎng)絡(luò)被劃分為n個社區(qū)，定義一個n*n的對稱矩陣a，那么對稱矩陣中元素aij表示社區(qū)i和社區(qū)j之間相互連接邊的數(shù)量與總邊數(shù)的比例，表示在同一個社區(qū)內(nèi)節(jié)點之間邊的數(shù)量與總邊數(shù)的比例，表示所有與社區(qū)i內(nèi)的節(jié)點存在相互連接的邊的數(shù)量與總邊數(shù)的比例。

2）NMI［16］。標(biāo)準化互信息（NMI），衡量一個方法下社區(qū)劃分結(jié)果與標(biāo)準劃分的社區(qū)相似程度，其公式如下：

其中，N表示劃分出的社區(qū)集合與真實社區(qū)集合的并集，Nij表示社區(qū)i和社區(qū)j的交集即公共的節(jié)點，Nj表示N中第j行所有元素的集合。

4.3 實驗結(jié)果及分析

4.3.1 實驗1-小規(guī)模數(shù)據(jù)實驗

實驗1主要選取了Karate、Football、Dolphins三種常用的真實數(shù)據(jù)集，對LPA算法、LPAP算法以及本文所提出的LLPA算法進行測試。表2為數(shù)據(jù)集在三種算法上進行測試得出Q值，表3為數(shù)據(jù)集在三種算法上進行測試得出NMI值。

表2 小規(guī)模數(shù)據(jù)集實驗得出的Q值

從表2和表3可以清晰地看出，在三個真實的數(shù)據(jù)集中，LPAP算法和LLPA算法本在Q值和NMI值上均優(yōu)于傳統(tǒng)的LPA算法，因數(shù)據(jù)集數(shù)據(jù)量小網(wǎng)絡(luò)結(jié)構(gòu)較為簡單，LPAP和LLPA整體差距較小，但本文LLPA算法的Q值和NMI值依然是最大的，即社區(qū)劃分結(jié)果是最好的。

表3 小規(guī)模數(shù)據(jù)集實驗得出的NMI值

4.3.2 實驗2-大規(guī)模數(shù)據(jù)實驗

實驗2采用C-DBLP數(shù)據(jù)集，分別運行LPA算法、LPAP算法、LLPA算法，最大迭代次數(shù)均設(shè)置為100。實驗結(jié)果如表4所示。

表4 大規(guī)模數(shù)據(jù)實驗得出的Q值和NMI值

從表4可以看出，在數(shù)據(jù)量較大數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜的數(shù)據(jù)集上，傳統(tǒng)標(biāo)簽傳播算法發(fā)現(xiàn)社區(qū)的質(zhì)量是最低的，LPAP、LLPA算法依然有著很好的優(yōu)勢，由于pagerank算法存在“跳轉(zhuǎn)概率”參數(shù)的影響，使得LLPA在各項指標(biāo)方面優(yōu)于LPAP。經(jīng)上述實驗證明，LLPA算法能夠有效地提高社區(qū)發(fā)現(xiàn)的質(zhì)量，有著較強的穩(wěn)定性。

5 結(jié)語

本文分析了標(biāo)簽傳播算法的優(yōu)缺點，從節(jié)點影響力入手，不再平等地對待每個節(jié)點。借鑒Lead?erRank算法，計算每個節(jié)點的影響力。在此基礎(chǔ)上采取一定的選取策略，獲取關(guān)鍵節(jié)點列表并為關(guān)鍵節(jié)點賦予唯一的標(biāo)簽。節(jié)點的更新順序依據(jù)于節(jié)點的影響力，優(yōu)先更新影響力較大的節(jié)點，防止資源的“逆流”。在標(biāo)簽的傳播過程中，考慮節(jié)點之間的傳播特性，消除節(jié)點標(biāo)簽更新過程中的隨機性，使得最終社區(qū)的劃分更加穩(wěn)定。