基于核心節點逐層擴展的標簽傳播社區發現方法*

翟鎮新 於躍成 谷 雨 景道月

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

1 引言

隨著互聯網技術的發展和社會網絡規模的不斷擴大，人與人之間的交流形式發生了巨大變化，人們獲取的信息量也呈爆炸式增長。社會網絡具有信息大、無標識、社區結構等特性，其中社區結構是社會網絡的基本性質。所謂社區結構是指一個網絡可以分為若干個社區，社區內節點相似度較高且連接相對緊密，社區間節點相似度較低且相對稀疏。社區發現可用于社交平臺用戶群組的發現，以實現相關商業廣告的投放；通過社區發現并挖掘群組的最新討論話題，可以向用戶更好地推薦感興趣的話題。

為了能夠實現社區的有效劃分，基于隨機游走的方法［1］、基于模塊度優化的方法［2～3］以及基于圖分割的方法［4～5］被相繼提出。這些方法主要依據網絡結構進行劃分，當應用于數據規模較大的社會網絡時，便會面臨迭代周期較長，算法復雜度較高等一系列問題。

2007 年，KUMARA 等學者［6］首次在面對非常繁瑣的社會網絡時，嘗試將標簽傳播模型（Label Propagation Algorithm，LPA）運用其中做社區發現的研究。實驗結果表明，使用LPA模型的社區發現時間效率等方面指標都有了巨大的突破。該算法模型不需要提前知道真實的社區個數有多少，僅依賴于社會網絡的自身結構。LPA 算法復雜度較低，被廣泛應用于大規模社會網絡的社區發現。

然而，LPA 在每次的迭代過程中存在著隨機性，致使每次社區發現的結果都不一致。造成LPA算法穩定性較差和隨機性較高的主要原因在于該算法沒有充分考慮節點自身的影響力，網絡中所有節點均被平等看待。為此，本文引入LeaderRank［7］算法來計算節點的影響力，在根據影響力值對節點進行排序的基礎上，采取一定的節點選取策略，篩選出網絡中的關鍵節點；接著，在初始化網絡節點時，這些關鍵節點被賦予唯一的標簽，并將這些節點視為初始傳播源；最后，采用逐層更新的方式更新節點標簽。

2 相關工作

2.1 標簽傳播算法

標簽傳播算法（LPA）的基本思想：一個擁有n個鄰居節點x1,x2,…,xn的給定節點x，和該節點x相互連接的節點都有所屬于自身的唯一標簽，那么該節點的標簽信息將由和其相互連接的節點標簽信息共同決定。標簽傳播算法可簡述為

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

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

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

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

圖1 標簽傳播過程

上述算法有兩種更新方式：同步更新和異步更新。采用同步更新將會在二分圖上產生循環震蕩的問題。如圖2 所示，假設p-1 時刻的狀態如圖2（a）所示，p 時刻的狀態如圖2（b）所示，那么如此循環下去將無法形成真正的社區。采用異步更新時，那么該節點的標簽信息將會由和該節點相連接的節點標簽信息中部分p時刻的信息和部分p-1時刻的信息所共同決定。

圖2 標簽震蕩

LPA 模型在時間效率等指標方面有著絕對的優勢，現階段已經在百萬級的復雜網絡中有著較高的使用頻率，但是該算法模型會存在一些無意義的節點標簽更新，往往會導致“無意義”的小型社區或者大型社區的形成，這些都是沒有研究價值的成果。

趙卓翔等［8］綜合考慮了在標簽的傳播過程中邊的權重、每個標簽的個數以及需更新節點的鄰居節點的度，提出了平均權重的概念。Zhao 等學者［9］將LPA算法模型與物理學中熵相結合，形成一種新的算法模型，該模型主要是計算每個節點所擁有標簽的熵值，按照熵值的大小來決定節點更新順序，從而消除原始算法中的節點更新隨意性。康旭彬等［10］采用Jaccard 系數計算節點之間的相似度，并以此決定節點標簽的更新選擇。張鑫等［11］在通過尋找不重疊三角形的方式來優化標簽初始化，并結合鄰居節點的影響力來選擇標簽，提高了社區發現的穩定性。馬秀等［12］利用k-shell 方法計算節點的影響力，但k-shell 方法只是一種粗粒度的劃分，對節點影響力的計算不夠精確。石夢雨等學者在原始標簽傳播算法的基礎上，融合進了LeaderRank算法模型，提出了新的標簽傳播算法（LRLPA）。Zhang 等［16］將節點重要性融入到原始算法中，計算網絡中節點重要性，并以此來替代節點標簽的重要程度，形成了一種新的標簽傳播算法（LPA_NI）。龔宇等［17］將LeaderRank算法與典型的COPRA算法相結合，對發現更加復雜的重疊社區的精準度有了較大的提升。

盡管以上方法在一定程度上提高了LPA 檢測社區的精確度，但這些方法在進行網絡節點初始化時，為所有節點都賦予了唯一標簽。這也意味著，網絡中的所有節點均被平等對待，弱化了核心節點的影響力，變相地抬高了邊緣節點的影響力，忽略了網絡中各節點之間的差異。

2.2 LeaderRank算法

目前用于衡量節點影響力的經典方法有很多，但大多數方法考慮的因素過于單一。如度中心性方法，僅僅從節點的度數進行考慮，忽略了節點自身影響力、鄰域節點影響力等諸多因素。以PageRank 為代表的一類算法中還含有參數，在面對不同網絡結構時，還需進行參數測試的方式來選取最優參數。

LeaderRank 算法由Zhang 等提出，是一種對社會網絡中的節點進行排序的方法。該算法綜合考慮了節點度數、鄰居節點影響力等因素，無需任何參數，能夠自適應網絡結構，符合網絡中的傳播特性，因此被廣泛用于復雜網絡中節點影響力的度量。

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

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

式（2）用于將背景節點vg的S 值平均分給每個節點。其中，tc表示穩定時刻，Si(tc)表示節點vi在穩定時刻的S 值，Sg(tc)表示背景節點vg在穩定時刻的S值，N為網絡G中的節點總數。

3 基于核心節點逐層擴展的標簽傳播社區發現方法

本文在LeaderRank算法的基礎上，對標簽傳播算法的節點初始化進行優化并給出新的標簽傳播策略，提出了一種新的標簽傳播算法CNE_LPA。在對節點初始化時選取核心節點，并為核心節點提供唯一標簽，以減少后續標簽傳播過程中無意義的判斷，提高標簽傳播過程的整體效率。在標簽傳播過程中，本文采用逐層更新的方式更新節點標簽。

3.1 節點初始化

由于CNE_LPA 算法僅選取部分節點作為初始傳播源，為此，從網絡中篩選出的核心節點應盡可能地輻射到所有的節點，并盡可能散落于每個社區之中。為實現上述目的，CNE_LPA 算法首先計算網絡中所有節點S 值的平均值，將S 值大于平均值的節點優先加入核心節點集中，并確保加入核心節點集的節點不是核心節點集中已存在節點的鄰居節點。那么，對于對于網絡G=（V，E），其中V 和E分別為網絡G 的頂點集和邊集，核心節點K 的選取策略可以概述如下。

1）對于?vi∈V，以S（vi）和avg分別表示節點vi的S 值和網絡G 中所有節點S 值的平均值，若S（vi）＞avg，則節點vi將被視為核心節點集K的候選節點；

2）對于?vj∈K，以Neighbor（vj）表示節點vj的鄰居節點，若候選核心節點vi∈Neighbor（vj），那么可以將vi加入核心節點集K。

算法1 核心節點集選取算法

輸入：網絡G=（V，E）

輸出：核心節點集K

算法：

1）對于?vi∈V，計算所有節點S 值的和Snum，即Snum+= S（vi）；

2）計算網絡G 中節點S 值的均值avg=Snum/N，其中N 為網絡G中的節點總數；

3）初始化核心節點集K=?，并將節點集V 拷貝至集合V′，若S（vi）＜avg，將vi從V′中刪除，然后將V′中節點按照其S值進行降序排列；

4）若V′≠?，從節點集V′中任意選取節點vi；否則，跳轉至5）；

（1）將節點集K拷貝至集合K′，跳轉至（2），測試節點vi是否為K中節點的鄰居；否則跳轉至（5）；

（2）從集合K′中任取一個節點vj，如果vi?Neighbor（vj）成立，跳轉至（3）；否則跳轉至（5）；

（3）將節點vj移出集合K′ ，若K′≠?，跳轉至（2）；若K′=?，跳轉至（4）；

（4）將節點vi移入集合K，將節點vi從集合V′中刪除，跳轉至4）；

（5）清空集合K′，將節點vi從集合V′中刪除，跳轉至4）；

5）輸出核心節點集K。

3.2 標簽傳播策略

在標簽傳播過程中，如果待更新節點的鄰域中擁有最大節點數量的標簽不止一個時，傳統LPA算法便會隨機選取其中的一個標簽。這種隨機選取標簽的方式往往導致相同數據集上多次檢測到的社區結果卻不一致。

為了降低LPA 在標簽傳播過程中的隨機性，CNE_LPA 算法選取待更新節點vi鄰域Neighbor（vi）中影響力最大的節點vk的標簽label（vk）作為節點vi的待更新標簽labelnew（vi）。也就是說，如果?vk∈Neighbor（vi），并且對于?vj∈Neighbor（vi），滿足S（vk）≥S（vj），那么labelnew（vi）=label（vk）。直覺上，社會網絡中的節點受到與其相鄰的所有節點的影響，而這些鄰居節點又可能隸屬于不同的社區。這意味著，一個節點的影響力實際上是其在多個社區上的影響力的綜合表現。為簡化起見，如式（3）所示，本文以節點影響力與該節點度的比值來表示該節點在特定社區上的影響力。另外，在節點vi的領域節點中可能存在多個節點與影響力最大的節點vk具有相同標簽的情形，為此，CNE_LPA算法以這些具有相同標簽的節點局部影響力之和來更新該節點的影響力。因此，當節點vi的標簽以節點vk的標簽更新后，節點vi的影響力Snew（vi）將按照式（3）所示的方式進行更新：

其中，Neighbor（vi）表示節點vi的鄰居節點集合，S（vj）表示節點vj的影響力，d（vj）表示節點的度。

由于CNE_LPA 算法對節點標簽采用逐層更新的方式，為此，本文引入多級鄰居節點這一概念。按照網絡層次結構，一級鄰居節點為核心節點的鄰居節點，二級鄰居節點為一級鄰居節點的鄰居節點，以此類推。當進行標簽傳播時，以核心節點集中的核心節點為初始傳播源，首先更新一級鄰居節點標簽；然后再以一級鄰居節點作為傳播源來更新二級鄰居節點；以此類推，直到所有節點的標簽更新完畢。

當節點標簽首次更新時，將采用上述方式更新節點標簽，并根據式（3）更新節點的影響力值。如果在更新過程中節點vi已有標簽，那么在以影響力值最大的標簽label（vk）更新label（vi）之前，需要先計算若以待更新標簽label（vk）更新label（vi）后Snew（vi）的值。如果Snew（vi）＞Sold（vi）成立，以label（vk）更新label（vi），即執行labelnew（vi）=label（vk）；否則label（vi）保持不變。當這個網絡G 中的節點標簽更新的變化率小于設定的閾值時，算法停止。

算法2 標簽傳播算法

輸入：網絡G=（V，E），核心節點集K，節點S值

輸出：網絡節點標簽集L

算法：

1）初始化核心節點集K 中每一節點的標簽，并以Null值初始化其余節點標簽；

2）初始化集合K″=K，V′=V；

3）若K′≠?，繼續執行1）；否則跳轉至4）

（1）若K′≠?，從集合K′中任取一個節點vj，否則跳轉至（4）

//更新K中一個核心節點vj的所有近鄰的標簽

（2）從集合V′中搜索節點vj的鄰居節點集合N=｛vi|vi∈Neighbor（vj）且vi∈V′｝；

①如果N≠?，任取其中一個節點vi；否則，跳轉至（3）；

②在vi的鄰居中搜索S 值最大且標簽值不是Null 的節點vk，即S（vk）=max｛S（vi）|vi∈N且S（vi）≠Null｝；

③根據式（3）計算Snew(vi)，如果Snew(vi)＞Sold(vi)，以label（vk）更新label(vi)，否則保持label(vi)不變；

④將節點vi并入集合K″，跳轉至①；

（3）從V′中刪除節點vj；

（4）K′=K″，K″=?，返回3）

4）結束標簽更新，算法終止。

3.3 CNE_LPA算法描述

CNE_LPA 算法從原始算法的節點初始化過程以及標簽傳播過程兩個方向進行了優化。CNE_LPA算法的總體步驟如下：

輸入：網絡G=（V，E）

輸出：社區C

算法：

1）初始化迭代次數t=1

2）調用算法1，生成重要節點集K；

3）調用算法2，完成節點標簽的一輪更新；

4）t=t+1，如果迭代次數t 小于閾值，返回到步驟2）；否則結束標簽更新；

5）輸出社區劃分C。

3.4 CNE_LPA算法時間復雜度

在復雜網絡G=（V，E）中，有x 個節點和y 條邊，核心節點的候選節點為t，核心節點的個數為k。節點影響力的計算時間復雜度為O(x2)，核心節點的篩選時間復雜度為O(x+t2)，初始化核心節點集中的核心節點時間復雜度為O(k)，節點標簽的更新迭代時間復雜度為O(x+xyk2)，將所有標簽相同的節點劃分為同一個社區的時間復雜度為O(x)。那么CNE_LPA 算法的時間復雜度為O(x2+3x+t2+xyk2)。

4 實驗及結果分析

實驗數據主要采用LFR 人工數據集和五種真實網絡數據集（Zachary，Football，Dolphin，Jazz，Netscience），在這些數據集的基礎上，將使用將使用其他社區檢測算法（LPA，LRLPA）來評估本文提出的CNE_LPA算法的性能。

4.1 實驗數據

1）LFR人工數據集

LFR 準基網絡數據集［13］是如今被廣泛用于評測社區發現算法優劣性的人工數據集。LFR 中的信息如表1所示。實驗數據集如表2所示。

表1 LFR數據集的信息

表2 4組LFR網絡的參數

2）真實數據集

真實數據集如表3所示。

表3 5組真實數據集

4.2 社區劃分評價標準

1）模塊度［14］

復雜網絡劃分社區質量的評判指標如式（6）所示：

其中，m代表社區中邊的數量，kv與kw分別表示節點v 和w 的度，A 為鄰接矩陣。若節點v 和節點w 之間沒有連接關系，那么Avw=0，反之，Avw=1。δ(cv,cw)表示節點v和節點w是否在同一個社區內，若在同一個社區內，δ(cv,cw)=1，否則δ(cv,cw)=0。

2）NMI［15］標準

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

其中，CA為標準社區劃分的結果，CB為算法所檢測到的社區結果，N 代表著節點數，Ci是矩陣C 的第i 行的總和，Cj是矩陣C 的第j 列的總和。Cij是指實際的社區為i但出現在發現社區j中的節點數。

4.3 實驗結果及分析

4.3.1 LFR人工數據集分析

在這些實驗中，由于傳統的LPA算法有著較高的隨機性，將LPA 算法在B1、B2、B3、B4 這四組人工數據集上均運行10次。測試效果如圖3所示，為了能夠體現LPA算法的不穩定，將在四張圖中直接用誤差線進行描述。

圖3 三個算法實驗結果折線圖

從圖中可以明顯看出，隨著社區結構越來越復雜，LPA 算法的波動性也就越來越大，但CNE_LPA和LRLPA 依然能夠穩定地檢測社區。總體來說，CNE_LPA 算法在量化節點標簽的重要程度時，主要考慮了與其相連接的節點的局部重要性，從而導致在更新時，在精準度上有著較大的提高。從穩定性以及社區檢測質量兩方面綜合考慮，CNE_LPA算法相較于其他兩種算法能夠更加穩定精確地實現社區檢測。

4.3.2 真實數據集分析

在本節中，使用模塊化度量將CNE_LPA 算法的性能與之前所提的其他兩種算法進行了比較，其中由于LPA算法的不穩定性，因此以LPA算法運行30次的平均值來做對比。為了評估CNE_LPA算法的準確性，本文將在兩個真實世界采集的網絡節點數據集進行多次試驗，并對實驗結果進行詳細分析。

1）Karate網絡分析

真實的Karate 網絡有兩個預定義的社區，CNE_LPA算法檢測到的結果如圖4所示，不同社區之間用不同的顏色表示。從圖中可以看出，CNE_LPA 算法不但可以準確地檢測出兩個社區，而且在準確劃分社區的基礎上可以發現兩個社區分別以節點1 和節點34 為中心，由此說明CNE_LPA算法能夠發現網絡中潛在的社區結構。

為了比較LPA 和CNE_LPA 算法的穩定性，本文將CNE_LPA 算法和原始算法在這兩個真實數據集上分別運行30次，算法運行結果的模塊度如圖5所示。從圖中可以明顯看出，CNE_LPA 算法有著較高的穩定性，LPA算法波動性較大。

圖5 LPA、CNE_LPA算法在Karate上的Q值變化

2）Dolphin網絡

Dolphin 網絡有兩個預定義的社區。本文在Dolphin 這個數據集上測試CNE_LPA 算法并檢測到如圖6 所示的三個社區，不同社區之間用不同的顏色加以區分。

圖6 CNE_LPA算法實現的社區劃分結果

從圖7 可以看出，LPA 算法因其自身的隨機性，產生較大的波動性，并不能有效地檢測社區。CNE_LPA算法則能夠穩定有效地檢測出社區。

圖7 LPA、CNE_LPA算法計算出的模塊度變化

在表4 中可以看出，從模塊化值以及社區發現數量上綜合考慮，LPA 算法因為其高隨機性的影響，其社區檢測結果有著較大的波動性。CNE_LPA 算法相對于其他兩種算法，則有著較高的模塊度，能夠穩定有效地檢測出社區。

表4 五種真實數據集在不同算法上運行的社區結果

5 結語

本文針對標簽傳播算法的節點初始化進行改進以及給出新的標簽傳播方法，引入LeaderRank算法衡量網絡中節點的影響力，在此基礎上選出核心節點作為初始標簽傳播源，減少了傳播過程中的計算復雜度。算法采用逐層更新的方式進行標簽更新，并且在傳播更新過程中考慮到與更新節點相連接的節點標簽重要性，消除了算法更新時極強的隨意性。多個數據集上的實驗表明，相較于其他算法，CNE_LPA 算法能夠更加穩定有效地實現社區的有效檢測。