基于節點重要性與相似性的標簽傳播算法①

林天森,孫飛翔

（華南師范大學 計算機學院,廣州 510631）

在現實世界中,存在著各種各樣的復雜網絡,如:社交網絡、萬維網、神經網絡等.這些網絡可以用圖來表示,對網絡的研究可以轉化為對圖論問題的研究.如圖論中的聚類問題,目的是挖掘復雜網絡的社區結構,使得類內節點聯系緊密,類間節點聯系稀疏.挖掘復雜網絡的社區結構對于研究網絡結構和應用具有非常重要的意義,如識別社交網絡中的頂級傳播者[1],根據用戶關系進行興趣或好友推薦[2,3]和通信網絡中的故障恢復[4]等.

為了挖掘復雜網絡的社區結構,學者們提出了許多社區發現的算法.Girvan等人[5]提出了GN算法,該算法的主要思想是每次刪除邊介數最高的邊,直到網絡中每個節點表示一個社區為止,GN算法的時間復雜度為O（m2n）,其中,m表示網絡的邊數,n表示網絡的節點數.Newman等人[6]提出了一種模塊度最大化的貪婪算法FN,該算法的時間復雜度為O（（m+n）n）.Pons等人[7]基于隨機游走提出的Walktrap算法,其主要思想是采用隨機游走算法計算節點的相似性矩陣,根據相似性矩陣合并社區,直到所有節點合并為一個社區為止.Raghavan等人[8]提出了標簽傳播算法（Label Propagation Algorithm,LPA）,該算法的主要優點是時間復雜度低,適用于在大型網絡上的社區發現.

多數典型標簽傳播類算法在標簽更新時,沒有考慮節點重要性和相似性對節點更新的綜合影響,可能導致影響力小的節點反過來影響具有較大影響力的節點,造成結果準確性低.本文基于節點重要性與相似性提出了一種改進的標簽傳播算法（Label Propagation Algorithm based on node Importance and Similarity,LPA_IS）.LPA_IS算法根據節點重要性提出了種子節點集和算法更新序列的獲取方法,并為任意種子節點分配唯一的標簽.在標簽更新過程中,基于節點重要性與相似性提出了一種標簽綜合影響力的計算方法,任意節點根據其鄰居標簽的綜合影響力更新自身的標簽,提高算法的準確性和穩定性.

1 相關工作

LPA算法的主要思想是,首先為圖中每個節點分配唯一的標簽,標簽代表節點所在的社區.當節點標簽更新時,根據式（1）選擇鄰居標簽中數量最多的作為節點的待更新標簽,當鄰居中標簽數量最多不止一個時,則隨機選擇一個.重復上述操作,直到所有節點的標簽趨于穩定或達到最大迭代次數時,則停止更新.

其中,T（i）表示節點i鄰居中標簽的集合,N（i）表示節點i的鄰居節點集,lj表示節點j的標簽,δ（l,lj）表示克羅內克函數[9],如果l=lj時,則δ（l,lj）=1,否則δ（l,lj）=0.

在LPA算法中,初始化序列和標簽選擇時具有隨機性,導致社區劃分時存在準確性低和穩定性差的缺陷.為了提高LPA算法的準確性和穩定性,近年來,許多學者對LPA算法進行改進,大致分為以下3種.基于帶約束的目標函數優化方法:LPAm[10]、LPAm+[11]和LPAh[9].利用目標函數的優化提高社區劃分質量,但沒有解決LPA穩定性差的問題.基于節點在網絡中的重要性對LPA算法進行改進的方法:NIBLPA[12]、IPLPA[13]和S-LPA[14].根據節點重要性計算標簽的影響力,進而改變算法的更新序列和標簽更新方法.然而,這些算法沒有考慮到網絡中節點之間的相似性.基于節點在網絡中的相似性進行改進的方法:NILPA[15]和HPI-LPA[16].通過計算節點與鄰居之間的相似性獲取節點的更新標簽,提高算法的準確性.

2 LPA_IS算法

2.1 節點重要性

節點重要性能夠衡量節點在網絡中的影響程度.主要的方法有:度中心性、介數中心性、接近中心性、k-shell算法[17]等.

k-shell算法能夠反映出節點在網絡中的全局影響力,但不能反映出同一層節點之間的差異和節點在網絡中的局部影響力,以及節點間的聯系程度.本文基于文獻[13]和集聚系數[18]提出了一種綜合衡量節點重要性的方法如式（2）所示.

其中,NKsd（j）表示Ksd（j）進行歸一化后的值,Cj表示節點j的集聚系數,α1和α2的取值是0到1之間的常數,NI（i）表示節點i的重要性.Ksd與NKsd的計算公式如下所示:

其中,Ks（i）表示節點i的ks值[17],t表示刪除節點i時的迭代次數,Ksd（i）表示融合節點i迭代次數的ks值.集聚系數Ci的計算如式（5）所示.

其中,ei表示節點i與其任意兩個鄰居節點形成的三角形個數,ki表示節點i的度數.Ci值越大說明鄰居節點之間聯系越緊密.

2.2 節點相似性

在標簽選擇時,本文將節點相似性作為衡量標簽綜合影響力的標準之一.根據網絡的局部信息計算節點相似性的方法有以下兩種:基于共同鄰居數的CN指標[19],基于共同鄰居節點度數的指標具體有Jaccard指標[19]、HPI指標[20]、RA指標[21]等.

本文選取RA指標作為計算節點相似性的方法.RA指標的計算如式（6）所示,s（i,j）表示節點i和j的相似性,s（i,j）值越大說明節點i和j的相似性程度越高,則它們越有可能屬于同一個社區.

2.3 種子節點集

本文基于節點重要性升序排列獲取算法的更新序列,并根據式（7）計算種子節點集,其中,i∈V,V表示網絡的節點集,S表示種子節點集.在算法初始化時,對選取的種子節點分配唯一的標簽.在標簽更新過程中,重要性值小的節點會受到鄰居中種子節點的影響,則這些節點的標簽將更新為種子節點的標簽,這有利于提高種子節點在網絡中的影響力和減少算法的迭代次數.

2.4 綜合影響力

在標簽更新過程中,節點選擇其鄰居中綜合影響力最大的標簽,作為節點的待更新標簽.本文基于節點重要性與相似性提出了一種計算標簽綜合影響力的方法.標簽綜合影響力的計算如式（8）所示.

2.5 算法描述

本文提出的LPA_IS算法,首先根據式（2）計算節點重要性,并獲取算法的更新序列.然后,基于節點重要性根據式（7）計算網絡的種子節點集,并為任意種子節點分配唯一的標簽.最后,根據式（8）計算節點鄰居中標簽的綜合影響力,通過式（9）選擇綜合影響力最大的標簽作為節點的待更新標簽.節點標簽的更新公式如下所示.

LPA_IS算法的具體描述如算法1所示.

2.6 復雜度分析

設n為網絡的節點數,m為網絡的邊數,k為網絡的平均度數,S為網絡的種子節點集.①計算節點重要性的復雜度為O（n）,獲取種子節點集的復雜度為O（n）,對任意種子節點初始化標簽的復雜度為O（|S|）,S的大小遠遠小于n,故可忽略不計,利用桶排序對節點重要性升序排列的復雜度為O（n）,因此LPA_IS算法初始化的復雜度為O（3×n）=O（n）;②計算節點與其鄰居之間相似性的復雜度為O（k×k）,利用式（8）計算標簽綜合影響力的復雜度為O（k）;③每一次迭代,節點進行標簽更新的復雜度為O（n×（k×k+k））=O（n×k×k）.假設算法的迭代次數為T,故LPA_IS算法的總時間復雜度為O（T×k×k×n+n）.

3 實驗結果與分析

實驗所使用的對比算法包括LPA、LPAm、LPAh、HPI-LPA和S-LPA,均用Python實現,部分算法存在隨機性,實驗結果取運行100次后的均值.實驗環境為Windows 10操作系統,內存8.00 GB,硬件配置Inter（R）Core（TM）i7-7770 CPU,4.00 GB.

3.1 實驗數據

實驗選取9個真實網絡數據集,它們來自不同的真實應用場景[9,14,22,23],網絡具體信息如表1所示.

表1 真實網絡數據集

本文采用由Lancichinetti等人[24]提出的LFR基準程序人工合成2組網絡,具體參數設置如表2所示,其中,N表示節點數,k表示平均度數,maxk表示最大度數,minc表示最小社區內的節點數,maxc表示最大社區內的節點數,mu表示社區的混合參數,mu值越大表示網絡結構越模糊,算法越難識別社區結構.

表2 人工合成網絡數據集

3.2 評價指標

3.2.1 標準化互信息

若已知網絡的真實劃分,則使用標準化互信息（Normalized Mutual Information,NMI）[25]作為評價指標.NMI的取值為[0,1].若NMI值為1,則說明算法劃分后的社區與網絡的真實劃分相同.NMI的定義如式（10）所示,其中,X表示網絡的真實劃分,Y表示算法得到的社區劃分,H（X|Y）表示X在Y上的規范化條件熵.

3.2.2 平均模塊度

當網絡的真實社區劃分未知時,選取模塊度Q[26]作為實驗的評價指標.假設算法運行了t次,每次得到的模塊度值為 Q1,Q2,···,Qt,采用 Qavg表示平均模塊度,Qavg的計算方式如式（11）所示.

3.2.3 模塊度標準差

在平均模塊度Qavg的基礎上,本文還采用模塊度標準差Qstd作為實驗的評價指標.Qstd的計算方式如式（12）所示.

3.3 實驗過程和結果分析

（1）真實網絡上的實驗

從表3中可以看出,在平均模塊度的對比上,LPA_IS算法在R1、R3和R4網絡上的Qavg值低于其它算法,而在其它網絡上的Qavg值比其它5種算法好.在模塊度的標準差方面,LPA_IS算法的Qstd值都為0,說明本文提出的LPA_IS算法具有較好的穩定性.在真實網絡數據集中,R1、R2、R3和R4網絡存在真實的社區劃分,在不同算法上比較數據集的NMI值,從表4中可以看出,LPA_IS算法在R3網絡上的NMI值比其它5種算法好,而在R1網絡上的NMI值與S-LPA算法相同都為1,說明在R1網絡上的社區劃分與真實網絡劃分一致.

表3 真實網絡模塊度對比

表4 真實網絡NMI對比

在算法運行的平均迭代次數方面,從圖1中可以看出,雖然LPA_IS算法在R2、R3和R5網絡上的平均迭代次數多于其它算法,但在其它網絡上的平均迭代次數比其它5種算法少,這是因為LPA_IS算法利用標簽綜合影響力更新節點標簽,避免了很多不必要的更新.

圖1 真實網絡平均迭代次數對比

綜上所述,在真實網絡數據集中,LPA_IS算法不僅能夠提高算法的準確性和穩定性,而且能夠有效地減少算法的迭代次數.

（2）人工合成網絡上的實驗

從圖2（a）可以看出,當參數mu≤0.6時,即社區結構比較明顯時,6種算法都能較好的發現社區結構,因此NMI值都比較高.當0.6

圖2 LFR基準合成網絡上NMI對比

4 總結

針對LPA算法的缺點,本文基于節點重要性與相似性提出了一種改進的標簽傳播算法（LPA_IS）.算法首先根據改進的k-shell分解算法和集聚系數計算節點重要性.其次,基于節點重要性提出了種子節點集和算法更新序列的獲取方法,并對任意種子節點分配唯一的標簽.最后,根據節點重要性與相似性計算標簽的綜合影響力,任意節點根據其鄰居標簽的綜合影響力更新自身的標簽.在真實網絡和人工合成網絡上的實驗結果表明,本文提出的LPA_IS算法與其它5種典型標簽傳播類算法相比,不僅提高了社區發現的準確性和穩定性,而且減少了算法的迭代次數.