林天森,孫飛翔

（華南師范大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510631）

在現(xiàn)實(shí)世界中,存在著各種各樣的復(fù)雜網(wǎng)絡(luò),如:社交網(wǎng)絡(luò)、萬維網(wǎng)、神經(jīng)網(wǎng)絡(luò)等.這些網(wǎng)絡(luò)可以用圖來表示,對網(wǎng)絡(luò)的研究可以轉(zhuǎn)化為對圖論問題的研究.如圖論中的聚類問題,目的是挖掘復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu),使得類內(nèi)節(jié)點(diǎn)聯(lián)系緊密,類間節(jié)點(diǎn)聯(lián)系稀疏.挖掘復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)對于研究網(wǎng)絡(luò)結(jié)構(gòu)和應(yīng)用具有非常重要的意義,如識別社交網(wǎng)絡(luò)中的頂級傳播者[1],根據(jù)用戶關(guān)系進(jìn)行興趣或好友推薦[2,3]和通信網(wǎng)絡(luò)中的故障恢復(fù)[4]等.

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

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

1 相關(guān)工作

LPA算法的主要思想是,首先為圖中每個節(jié)點(diǎn)分配唯一的標(biāo)簽,標(biāo)簽代表節(jié)點(diǎn)所在的社區(qū).當(dāng)節(jié)點(diǎn)標(biāo)簽更新時,根據(jù)式（1）選擇鄰居標(biāo)簽中數(shù)量最多的作為節(jié)點(diǎn)的待更新標(biāo)簽,當(dāng)鄰居中標(biāo)簽數(shù)量最多不止一個時,則隨機(jī)選擇一個.重復(fù)上述操作,直到所有節(jié)點(diǎn)的標(biāo)簽趨于穩(wěn)定或達(dá)到最大迭代次數(shù)時,則停止更新.

其中,T（i）表示節(jié)點(diǎn)i鄰居中標(biāo)簽的集合,N（i）表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集,lj表示節(jié)點(diǎn)j的標(biāo)簽,δ（l,lj）表示克羅內(nèi)克函數(shù)[9],如果l=lj時,則δ（l,lj）=1,否則δ（l,lj）=0.

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

2 LPA_IS算法

2.1 節(jié)點(diǎn)重要性

節(jié)點(diǎn)重要性能夠衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響程度.主要的方法有:度中心性、介數(shù)中心性、接近中心性、k-shell算法[17]等.

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

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

其中,Ks（i）表示節(jié)點(diǎn)i的ks值[17],t表示刪除節(jié)點(diǎn)i時的迭代次數(shù),Ksd（i）表示融合節(jié)點(diǎn)i迭代次數(shù)的ks值.集聚系數(shù)Ci的計(jì)算如式（5）所示.

其中,ei表示節(jié)點(diǎn)i與其任意兩個鄰居節(jié)點(diǎn)形成的三角形個數(shù),ki表示節(jié)點(diǎn)i的度數(shù).Ci值越大說明鄰居節(jié)點(diǎn)之間聯(lián)系越緊密.

2.2 節(jié)點(diǎn)相似性

在標(biāo)簽選擇時,本文將節(jié)點(diǎn)相似性作為衡量標(biāo)簽綜合影響力的標(biāo)準(zhǔn)之一.根據(jù)網(wǎng)絡(luò)的局部信息計(jì)算節(jié)點(diǎn)相似性的方法有以下兩種:基于共同鄰居數(shù)的CN指標(biāo)[19],基于共同鄰居節(jié)點(diǎn)度數(shù)的指標(biāo)具體有Jaccard指標(biāo)[19]、HPI指標(biāo)[20]、RA指標(biāo)[21]等.

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

2.3 種子節(jié)點(diǎn)集

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

2.4 綜合影響力

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

2.5 算法描述

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

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

2.6 復(fù)雜度分析

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

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)所使用的對比算法包括LPA、LPAm、LPAh、HPI-LPA和S-LPA,均用Python實(shí)現(xiàn),部分算法存在隨機(jī)性,實(shí)驗(yàn)結(jié)果取運(yùn)行100次后的均值.實(shí)驗(yàn)環(huán)境為Windows 10操作系統(tǒng),內(nèi)存8.00 GB,硬件配置Inter（R）Core（TM）i7-7770 CPU,4.00 GB.

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)選取9個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集,它們來自不同的真實(shí)應(yīng)用場景[9,14,22,23],網(wǎng)絡(luò)具體信息如表1所示.

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

本文采用由Lancichinetti等人[24]提出的LFR基準(zhǔn)程序人工合成2組網(wǎng)絡(luò),具體參數(shù)設(shè)置如表2所示,其中,N表示節(jié)點(diǎn)數(shù),k表示平均度數(shù),maxk表示最大度數(shù),minc表示最小社區(qū)內(nèi)的節(jié)點(diǎn)數(shù),maxc表示最大社區(qū)內(nèi)的節(jié)點(diǎn)數(shù),mu表示社區(qū)的混合參數(shù),mu值越大表示網(wǎng)絡(luò)結(jié)構(gòu)越模糊,算法越難識別社區(qū)結(jié)構(gòu).

表2 人工合成網(wǎng)絡(luò)數(shù)據(jù)集

3.2 評價(jià)指標(biāo)

3.2.1 標(biāo)準(zhǔn)化互信息

若已知網(wǎng)絡(luò)的真實(shí)劃分,則使用標(biāo)準(zhǔn)化互信息（Normalized Mutual Information,NMI）[25]作為評價(jià)指標(biāo).NMI的取值為[0,1].若NMI值為1,則說明算法劃分后的社區(qū)與網(wǎng)絡(luò)的真實(shí)劃分相同.NMI的定義如式（10）所示,其中,X表示網(wǎng)絡(luò)的真實(shí)劃分,Y表示算法得到的社區(qū)劃分,H（X|Y）表示X在Y上的規(guī)范化條件熵.

3.2.2 平均模塊度

當(dāng)網(wǎng)絡(luò)的真實(shí)社區(qū)劃分未知時,選取模塊度Q[26]作為實(shí)驗(yàn)的評價(jià)指標(biāo).假設(shè)算法運(yùn)行了t次,每次得到的模塊度值為 Q1,Q2,···,Qt,采用 Qavg表示平均模塊度,Qavg的計(jì)算方式如式（11）所示.

3.2.3 模塊度標(biāo)準(zhǔn)差

在平均模塊度Qavg的基礎(chǔ)上,本文還采用模塊度標(biāo)準(zhǔn)差Qstd作為實(shí)驗(yàn)的評價(jià)指標(biāo).Qstd的計(jì)算方式如式（12）所示.

3.3 實(shí)驗(yàn)過程和結(jié)果分析

（1）真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)

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

表3 真實(shí)網(wǎng)絡(luò)模塊度對比

表4 真實(shí)網(wǎng)絡(luò)NMI對比

在算法運(yùn)行的平均迭代次數(shù)方面,從圖1中可以看出,雖然LPA_IS算法在R2、R3和R5網(wǎng)絡(luò)上的平均迭代次數(shù)多于其它算法,但在其它網(wǎng)絡(luò)上的平均迭代次數(shù)比其它5種算法少,這是因?yàn)長PA_IS算法利用標(biāo)簽綜合影響力更新節(jié)點(diǎn)標(biāo)簽,避免了很多不必要的更新.

圖1 真實(shí)網(wǎng)絡(luò)平均迭代次數(shù)對比

綜上所述,在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中,LPA_IS算法不僅能夠提高算法的準(zhǔn)確性和穩(wěn)定性,而且能夠有效地減少算法的迭代次數(shù).

（2）人工合成網(wǎng)絡(luò)上的實(shí)驗(yàn)

從圖2（a）可以看出,當(dāng)參數(shù)mu≤0.6時,即社區(qū)結(jié)構(gòu)比較明顯時,6種算法都能較好的發(fā)現(xiàn)社區(qū)結(jié)構(gòu),因此NMI值都比較高.當(dāng)0.6

圖2 LFR基準(zhǔn)合成網(wǎng)絡(luò)上NMI對比

4 總結(jié)

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