融合Leader Rank和標簽傳播的社區發現算法?

翟鎮新 於躍成 谷 雨

（江蘇科技大學計算機學院 鎮江 212000）

1 引言

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

為了能夠實現社區的劃分，近代學者提出了很多優秀的社區發現方法［1～5］，如基于隨機游走的方法、基于結構相似性度量的聚合方法及圖分割方法等，這些算法主要依據網絡結構進行劃分，在用于數據規模較大的社會網絡時，迭代周期較長，算法復雜度較高。因此，更多學者將注重點放在提高社區的發現效率及穩定性上。

2007年，Raghavan等［6］首次將標簽傳播算法（LPA）運用到復雜的社會網絡中用于社區發現，社區的發現效率也因此得到了顯著的提高。LPA無需預先知道社區的個數，僅依據于社會網絡的自身結構發現社區，算法復雜度較低，被廣泛運用于大規模的社會網絡中。但是LPA在每一的迭代過程中存在著隨機性，致使社區發現的結果不一樣，穩定性較差。

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

2 相關工作

2.1 標簽傳播算法

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

1）節點標簽初始化時，為每個節點賦予唯一的標簽，用來標識節點所在的社區。

2）對圖中所有的節點開始迭代更新，節點標簽將會接受鄰居節點的標簽信息，選擇鄰居節點中標簽數量最多的標簽。當多個標簽數量相同時，那么將會隨機選取其中一個標簽作為更新節點的標簽。經過多次迭代，使得圖中所有的節點趨于穩定，社區結構也將顯現出來

3）根據每個節點的標簽，將所有的節點進行劃分，標簽相同的節點將劃分為同一社區。

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

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

圖2 標簽震蕩

標簽傳播算法具有線性的時間復雜度，以被廣泛地運用于大規模的社會網絡中，但是該算法在節點更新順序和標簽傳播過程中存在著隨機性，將會形成“無意義”的小型社區或者大型社區。

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

2.2 Leader Rank算法

LeaderRank算法是對PageRank算法的優化，和PageRank算法比較，LeaderRank無需預先設置參數，即“跳轉概率”，因此避免了參數的不同影響計算節點影響力的準確性，非常適合大規模的社交網絡。

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

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

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

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

3 融合Leader Rank和標簽傳播的社區發現方法

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

圖3 算法流程圖

3.1 節點初始化

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

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

3.2 節點更新順序

為了避免圖2所示的循環震蕩，LLPA算法將采用異步更新的方法。網絡圖中有著影響力大的節點，也有影響力小的節點，在節點標簽傳播達到穩定狀態時，影響力小的標簽會被影響力大的標簽所替代，若隨機優先更新了影響力小的節點，這將是無意義的標簽更新。

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

3.3 標簽傳播能力

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

傳統的標簽傳播算法在一定程度上考慮了標簽傳播特性，即假定兩節點之間都是平等的，能直接相互傳播。在現實的網絡中，考慮到節點的影響力，根據相關參考文獻［14］，節點有標簽傳播和標簽接受兩種能力，影響力小的節點容易接受標簽，影響力大的節點更容易將標簽傳播給影響力相對小的標簽，其如式（3）所示。

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

在此基礎上，對節點i的鄰居中的每一個標簽t計算其傳播能力，如式（4）所示。

其中C（t）表示標簽為t的節點集合。

故對于一個節點i來說，其標簽選擇如式（5）所示。

3.4 社區劃分算法LLPA

LLPA算法的偽代碼：

輸入：圖G（V，E）；

輸出：社區劃分結果

1）計算出網絡圖中的關鍵節點列表N，為每個關鍵節點賦予唯一的標簽；

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

3）迭代次數t=1；

4）按照S值的排序，更新每個節點的標簽：

5）檢查迭代次是否達到最大值或者網絡中的節點標簽信息不再發生變化達到穩定狀態。否則在t+1時刻，返回步驟3）繼續迭代更新。

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

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

4 實驗及結果分析

實驗數據集為三個小規模的數據集和一個大規模的數據集。所有實驗均采用python語言實現，實驗環境為Windows10，python2.7。

4.1 實驗數據

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

表1 數據集參數

4.2 社區劃分評價標準

1）模塊度［15］。復雜網絡劃分社區質量的評判指標，其定義為假定一個復雜網絡被劃分為n個社區，定義一個n*n的對稱矩陣a，那么對稱矩陣中元素aij表示社區i和社區j之間相互連接邊的數量與總邊數的比例，表示在同一個社區內節點之間邊的數量與總邊數的比例，表示所有與社區i內的節點存在相互連接的邊的數量與總邊數的比例。

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

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

4.3 實驗結果及分析

4.3.1 實驗1-小規模數據實驗

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

表2 小規模數據集實驗得出的Q值

從表2和表3可以清晰地看出，在三個真實的數據集中，LPAP算法和LLPA算法本在Q值和NMI值上均優于傳統的LPA算法，因數據集數據量小網絡結構較為簡單，LPAP和LLPA整體差距較小，但本文LLPA算法的Q值和NMI值依然是最大的，即社區劃分結果是最好的。

表3 小規模數據集實驗得出的NMI值

4.3.2 實驗2-大規模數據實驗

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

表4 大規模數據實驗得出的Q值和NMI值

從表4可以看出，在數據量較大數據結構較為復雜的數據集上，傳統標簽傳播算法發現社區的質量是最低的，LPAP、LLPA算法依然有著很好的優勢，由于pagerank算法存在“跳轉概率”參數的影響，使得LLPA在各項指標方面優于LPAP。經上述實驗證明，LLPA算法能夠有效地提高社區發現的質量，有著較強的穩定性。

5 結語

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