基于網絡預處理的改進標簽傳播算法①

孫生才, 范 菁, 曲金帥, 王玉紅

1(云南民族大學 電氣信息工程學院,昆明 650500)

2(云南省無線傳感器重點實驗室,昆明 650500)

現實生活中的事物都可以用復雜網絡[1]模型來表示. 大數據[2]背景下,復雜網絡的規模不斷變大. 研究表明,復雜網絡不僅具有小世界、無標度等特性外,還呈現出明顯的社區結構[3]. 社區結構能夠更好地理解網絡中的拓撲,從而發現網絡中隱藏的規律,對網絡進行預測和改造. 如社交網絡分析、控制疾病傳播等.

目前,各種社區發現算法被提出并不斷地改進. 其中2007年Raghavan等提出的標簽傳播算法[4](Label Propagation Algorithm,LPA)最典型. LPA算法因簡單且具有接近線性的時間復雜度常用于處理大規模復雜網絡. 由于算法中存在過多的隨機策略,導致社區發現的準確性和穩定性較差. LPA算法因此得到不斷改進.如Barber等提出基于模塊度目標函數標簽傳播算法(LPAm)[5]來防止將網絡劃分成一個社區,但導致形成大量的小社區影響劃分結果. 趙卓翔等提出基于標簽影響值的社區發現算法(LIB)[6]來提高社區發現的質量,但計算時需要用到邊的權重,而網絡中邊的權值很難確定. 隨著網絡規模不斷增大,改進算法也面臨巨大的挑戰.

本文利用節點的K-Shell[7]指數對原始網絡進行預處理：去除邊緣層的節點,賦予核心層節點標簽. 然后利用改進算法對預處理網絡進行標簽傳播. 網絡的預處理在一定程度縮小了網絡規模,減少了初始標簽個數,加快了算法的收斂速度. 同時改進算法降低了隨機性,提高了算法的準確性和穩定性.

1 LPA算法分析

1.1 LPA算法

標簽傳播算法用給定節點的標簽信息來對未給定標簽的節點的標簽進行預測. 初始時,網絡中每個節點分配一個唯一的標簽; 其次,隨機選擇節點進行標簽更新; 根據式(1)選擇其相鄰節點中出現頻率最高的標簽. 經過若干次迭代,網絡中擁有相同標簽的節點構成一個社區.

Cx(t)為節點x在t次迭代時的標簽,Nl(x)為節點x的標簽為l的鄰節點的集合.

1.2 現狀

LPA算法中存在著大量的隨即策略. 初始時每個節點分配一個標簽,形成一些小的、零散的社區,導致有意義的社區不能形成,同時放慢了收斂速度; 節點的更新順序是隨機的,導致最終的結果多樣性,穩定性自然而然降低; 在更新過程中,忽略節點間重要性的差異,影響力小的節點有可能反過來影響具有較大影響力的節點,導致結果準確性降低.

隨著大數據時代的到來,使得可供研究的數據越來越豐富. 復雜網絡規模不斷增大,網絡中節點數不斷增加. 標簽傳播算法除現有的準確性和穩定性問題外,大規模復雜網絡導致算法的運算量加倍增加,收斂速度減慢,失去了原始算法高效的特點.

2 改進的KLPA算法

2.1 網絡分層

在人際關系網中,人與人間的影響力是有差異的.有人是起決定性作用的“領導”,而有人則是無關緊要的“路人”.同理,復雜網絡中節點間影響力[8]亦如此. 節點的影響力與節點在網絡中所處的位置有關：通常,影響力大的節點處在網絡中的核心位置,相反影響力小的節點處在網絡中的邊緣位置. K核分解可以很好地衡量出節點在網絡中的所處的位置,將網絡劃分成核心—邊緣的層次,衡量節點在全局重要程度.

K核分解(K-core Decomposition)：將網絡中所有度為1的節點刪除,刪除后若還有度為1的節點,則繼續刪除度為1的節點,直到網絡中剩余節點的度都大于1為止,刪除節點的K值為1. 同理K值等于2的節點亦如此,依次類推. 分解過程結束后,每個節點的K值都被確定.

K值將網絡中的節點劃分到不同的層,即節點在網絡中所處的位置.

定義1. 核心層：網絡中處于核心位置的節點,它們在網絡中起決定性用. 核心層節點的重要性往往大于其它層的節點.

定義2. 邊緣層：網絡中處于邊緣位置的節點,作用相當于網絡中的“路人”. 邊緣層節點的影響力是整個網絡中最小的.

網絡分層對改進標簽傳播算法具有很大的幫助,尤其針對算法的初始化階段.

2.2 預處理階段

分析LPA的結果發現,節點的標簽種類數遠遠少于初始標簽的種類數,大多數標簽隨著迭代更新而消失. 最終剩余的標簽通常是初始時影響力較大的節點的標簽,它們在傳播中起主導作用. 這些節點往往是每個社區的中心.

網絡中具有較大影響力的節點通常處于核心層,它們的標簽決定著社區劃分結果. 初始時只賦予核心層的節點標簽,其余層節點不賦予標簽. 可以大大減少初始的標簽,避免出現零散、小的社區,有助于提高劃分的準確性.

網絡中存在一些“無關緊要”的節點,其影響力相對較小,如邊緣層節點. 在傳播過程中它們對鄰居節點標簽并無影響,只是單純地服從更新. 但隨著網絡規模的增大,邊緣層節點的數量急劇增多. 它們不斷地重復更新不僅增加了運算量,還放慢了收斂速度.

如果將邊緣層節點去除,不僅減少節點個數,縮小網絡的規模,對算法的結果幾乎無影響,從而提高了算法的有效性.

預處理階段：僅賦予核心層的節點標簽,同時去除邊緣層節點,對預處理網絡進行標簽更新.

2.3 更新階段

預處理階段從網絡整體出發簡化初始網絡. 而更新階段,則發生在網絡的局部. 更新節點的標簽與其鄰居節點的標簽有關,它與鄰居節點的影響力大小相關.K核分解是全局刻畫節點的影響力,并不能充分體現節點的局部影響力.

Kitsak等認為度能刻畫節點周圍局部特征[9]. 因此引入歸一化度值作為節點的局部影響力.

為更加全面地衡量節點的影響力,將全局影響力k值和局部影響力lo相結合,得出節點在網絡中的綜合影響力.

原始算法中選擇其鄰居節點中出現頻率最高的標簽作為更新節點的標簽. 更新節點的標簽除與鄰居節點的影響力大小相關外,還與鄰居中出現的標簽個數相關. 選擇其鄰居中影響力最大的標簽.

Nl(x)是x的標簽為l的鄰接節點集. 對于節點x,其標簽為：

當更新節點的鄰節點都沒有標簽時,則選擇下一節點進行更新; 如果鄰居節點有標簽時,則根據式(7)選擇其中具有最大影響力的標簽.

更新時確定的節點更新順序可有效降低隨機性.預處理僅賦予核心層節點標簽,標簽分布在網絡的中心. 為提高更新效率,節點應從網絡中心向邊緣(節點影響力降序順序)大致有序進行更新.

2.4 后處理階段

預處理網絡的社區劃分結束后,對邊緣層節點的標簽進行確定. 由于邊緣層節點的影響力相對較小,極易受到其鄰居中影響力大的節點影響. 因此其標簽由鄰居中影響力最大的節點的標簽所決定.

最后擁有相同標簽的節點在同一個社區.

算法分3個步驟：

(1)預處理階段

網絡進行K核分解,劃分成核心-邊緣層. 賦予核心層節點標簽,并去除邊緣層節點.

(2)標簽更新階段-預處理網絡

計算節點的綜合影響力,按影響力降序順序依次更新節點;

依據式(7)選擇標簽作為更新節點的標簽;

若節點標簽不再變化,算法結束.

(3)后處理階段

邊緣層節點的標簽,根據式(8)選擇其鄰居中具有最大影響力的節點的標簽.

最后,具有相同標簽的節點劃分到同一個社區.

相對于原始算法,改進算法的預處理階段縮小了網絡規模,減小了更新時節點的運算量改進的更新策略降低了隨機性,加快了算法的收斂速度.

3 實驗與分析

仿真工具MATLAB(matlab2012a,Win 7 64位,4 GB內存). 為驗證算法的有效性,實驗數據采用真實網絡和LFR人工合成網絡. 算法中存在隨機性,對實驗運行1000次后取均值.

3.1 真實網絡

海豚網絡是由棲息在新西蘭的一個寬吻海豚群體所構造出的關系網(含2個家族).節點代表海豚,邊表示兩個海豚之間接觸頻繁,網絡由62個節點和159條邊組成. 采用改進算法對網絡進行社區劃分,分析過程及結果如下所示.

網絡被劃分為4層,邊緣層的節點K=1,核心層節點K=4.將邊緣層節點去除后,得到一個53個節點和150條邊組成的新網絡. 節點數減少14.5%,邊減少5.6%. 圖1為算法的劃分結果. 網絡被劃分為兩大社區,與實際社區對比,節點的劃分準確率為98%.為充分了解算法性能,將改進算法與LPA和LPAD算法進行實驗對比,具體的實驗數據結果如表1所示.

社區劃分方式即社區的劃分種類數,數值越大,說明社區劃分結果越分散、不集中,算法的穩定性也就越差. LPA劃分方式為153種,LPAD為11種,KLPA僅為1種. 比較社區大小發現,LPA和LPAD算法會出現節點個數分別為2或5的零散、小社區,與真實的社區情況不相符. 規范化交互信息(NMI)的值越大,說明社區劃分結果與實際社區越一致. 對比發現LPA的NMI值最低,說明其準確性較低. LPAD的準確性得到提高,而KLPA的準確性最高. 迭代次數越小表明算法收斂越快. KLPA算法的迭代次數最小,加快了收斂速度,依然保持高效的特點.

圖1 海豚網劃分圖

表1 海豚網數據結果

同時還對其他網絡進行分析—Karate網絡、Football聯賽網絡、Polbooks聯賽網絡,采用模塊度函數Q值、標準化互信息NMI值和迭代次數來對比算法性能,結果表2所示. 由表2可知KLPA算法的Q值和 NMI值大于LPA和 LPAD算法,說明KLPA算法獲得的社區質量相對較高,社區劃分的準確性也高于其他兩種算法. KLPA算法的迭代次數明顯低于LPA和LPAD算法,算法的收斂速度加快.

表2 實驗網絡結果

3.2 LFR網絡

LFR基準網絡常用來測試社區發現算法的性能.當網絡中社區結構明顯時(0 0.45時),網絡社區結構變得越來越復雜,社區劃分效果也就變得較差.針對社區結構復雜這種情況,對算法的性能進行比. 網絡參數設置：G1：N=1000,K=15,kmax=50,cmin=20,cmax=50,G2：N=2000,K=15,kmax=50,cmin=20,cmax=50.mu取值在0.4-0.65之間.

從圖2可知,無論網絡中節點個數為1000或2000,當網絡結構變得復雜時,兩種算法的準確性均有所下降,但KLPA算法的NMI值明顯大于LPA算法.說明當網絡結構較復雜時,KLPA算法的社區發現準確性相對較高,具有比LPA算法更好的性能. 當mu增大到0.65時,網絡中的社區結構變得模糊. 各社區間連接更加緊密,相互滲透,節點間的差異變小,算法很難發揮作用,準確性大大降低,兩種算法失效.

圖2 LFR網絡NMI對比

同時對兩種算法的迭代次數進行對比發現,KLPA算法的迭代次數遠遠小于原始算法. 說明改進算法加快了收斂速度,提高了效率. 當mu>0.65時,LPA算法失效,迭代次數也就失去意義,如圖3所示.

圖3 迭代次數對比

4 結論

隨著網絡規模的增大,現有算法除準確性和穩定性問題外,算法的收斂速度也減緩. 本文從整體上利用K-Shell指數將網絡分層,一定程度上縮小網絡規模.并在局部對算法的更新策略加以改進. 仿真實驗證明KLPA算法不僅可以縮小網絡規模,并能提高社區劃分的準確性和穩定性. 加快算法的收斂速度.

1 劉濤,陳忠,陳曉榮. 復雜網絡理論及其應用研究概述. 系統工程,2005,23(6)：1-7.

2 周濤. 網絡大數據——復雜網絡的新挑戰：如何從海量數據獲取信息? 電子科技大學學報,2013,42(1)：7-8.

3 劉發升,羅延榕. 基于多種群遺傳算法的復雜網絡社區結構發現. 計算機應用研究,2012,29(4)：1237-1240.

4 張俊麗,常艷麗,師文. 標簽傳播算法理論及其應用研究綜述. 計算機應用研究,2013,30(1)：21-25.

5 Barber MJ,Clark JW. Detecting network communities by propagating labels under constraints. Physical Review E Statistical Nonlinear & Soft Matter Physics,2009,80(2 Pt 2)：026129.

6 趙卓翔,王軼彤,田家堂,等. 社會網絡中基于標簽傳播的社區發現新算法. 計算機研究與發展,2011,48(S2)：8-15.

7 顧亦然,王兵,孟繁榮. 一種基于K-Shell的復雜網絡重要節點發現算法. 計算機技術與發展,2015,25(9)：70-74.

8 任曉龍,呂琳媛. 網絡重要節點排序方法綜述. 科學通報,2014,59(13)：1175-1197.

9 Kitsak M,Gallos LK,Havlin S,et al. Identification of influential spreaders in complex networks. Nature Physics,2010,6(11)：888-893. [doi：10.1038/nphys1746]