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

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

2(云南省無線傳感器重點(diǎn)實(shí)驗(yàn)室,昆明 650500)

現(xiàn)實(shí)生活中的事物都可以用復(fù)雜網(wǎng)絡(luò)[1]模型來表示. 大數(shù)據(jù)[2]背景下,復(fù)雜網(wǎng)絡(luò)的規(guī)模不斷變大. 研究表明,復(fù)雜網(wǎng)絡(luò)不僅具有小世界、無標(biāo)度等特性外,還呈現(xiàn)出明顯的社區(qū)結(jié)構(gòu)[3]. 社區(qū)結(jié)構(gòu)能夠更好地理解網(wǎng)絡(luò)中的拓?fù)?從而發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的規(guī)律,對網(wǎng)絡(luò)進(jìn)行預(yù)測和改造. 如社交網(wǎng)絡(luò)分析、控制疾病傳播等.

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

本文利用節(jié)點(diǎn)的K-Shell[7]指數(shù)對原始網(wǎng)絡(luò)進(jìn)行預(yù)處理：去除邊緣層的節(jié)點(diǎn),賦予核心層節(jié)點(diǎn)標(biāo)簽. 然后利用改進(jìn)算法對預(yù)處理網(wǎng)絡(luò)進(jìn)行標(biāo)簽傳播. 網(wǎng)絡(luò)的預(yù)處理在一定程度縮小了網(wǎng)絡(luò)規(guī)模,減少了初始標(biāo)簽個數(shù),加快了算法的收斂速度. 同時改進(jìn)算法降低了隨機(jī)性,提高了算法的準(zhǔn)確性和穩(wěn)定性.

1 LPA算法分析

1.1 LPA算法

標(biāo)簽傳播算法用給定節(jié)點(diǎn)的標(biāo)簽信息來對未給定標(biāo)簽的節(jié)點(diǎn)的標(biāo)簽進(jìn)行預(yù)測. 初始時,網(wǎng)絡(luò)中每個節(jié)點(diǎn)分配一個唯一的標(biāo)簽; 其次,隨機(jī)選擇節(jié)點(diǎn)進(jìn)行標(biāo)簽更新; 根據(jù)式(1)選擇其相鄰節(jié)點(diǎn)中出現(xiàn)頻率最高的標(biāo)簽. 經(jīng)過若干次迭代,網(wǎng)絡(luò)中擁有相同標(biāo)簽的節(jié)點(diǎn)構(gòu)成一個社區(qū).

Cx(t)為節(jié)點(diǎn)x在t次迭代時的標(biāo)簽,Nl(x)為節(jié)點(diǎn)x的標(biāo)簽為l的鄰節(jié)點(diǎn)的集合.

1.2 現(xiàn)狀

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

隨著大數(shù)據(jù)時代的到來,使得可供研究的數(shù)據(jù)越來越豐富. 復(fù)雜網(wǎng)絡(luò)規(guī)模不斷增大,網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)不斷增加. 標(biāo)簽傳播算法除現(xiàn)有的準(zhǔn)確性和穩(wěn)定性問題外,大規(guī)模復(fù)雜網(wǎng)絡(luò)導(dǎo)致算法的運(yùn)算量加倍增加,收斂速度減慢,失去了原始算法高效的特點(diǎn).

2 改進(jìn)的KLPA算法

2.1 網(wǎng)絡(luò)分層

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

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

K值將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分到不同的層,即節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置.

定義1. 核心層：網(wǎng)絡(luò)中處于核心位置的節(jié)點(diǎn),它們在網(wǎng)絡(luò)中起決定性用. 核心層節(jié)點(diǎn)的重要性往往大于其它層的節(jié)點(diǎn).

定義2. 邊緣層：網(wǎng)絡(luò)中處于邊緣位置的節(jié)點(diǎn),作用相當(dāng)于網(wǎng)絡(luò)中的“路人”. 邊緣層節(jié)點(diǎn)的影響力是整個網(wǎng)絡(luò)中最小的.

網(wǎng)絡(luò)分層對改進(jìn)標(biāo)簽傳播算法具有很大的幫助,尤其針對算法的初始化階段.

2.2 預(yù)處理階段

分析LPA的結(jié)果發(fā)現(xiàn),節(jié)點(diǎn)的標(biāo)簽種類數(shù)遠(yuǎn)遠(yuǎn)少于初始標(biāo)簽的種類數(shù),大多數(shù)標(biāo)簽隨著迭代更新而消失. 最終剩余的標(biāo)簽通常是初始時影響力較大的節(jié)點(diǎn)的標(biāo)簽,它們在傳播中起主導(dǎo)作用. 這些節(jié)點(diǎn)往往是每個社區(qū)的中心.

網(wǎng)絡(luò)中具有較大影響力的節(jié)點(diǎn)通常處于核心層,它們的標(biāo)簽決定著社區(qū)劃分結(jié)果. 初始時只賦予核心層的節(jié)點(diǎn)標(biāo)簽,其余層節(jié)點(diǎn)不賦予標(biāo)簽. 可以大大減少初始的標(biāo)簽,避免出現(xiàn)零散、小的社區(qū),有助于提高劃分的準(zhǔn)確性.

網(wǎng)絡(luò)中存在一些“無關(guān)緊要”的節(jié)點(diǎn),其影響力相對較小,如邊緣層節(jié)點(diǎn). 在傳播過程中它們對鄰居節(jié)點(diǎn)標(biāo)簽并無影響,只是單純地服從更新. 但隨著網(wǎng)絡(luò)規(guī)模的增大,邊緣層節(jié)點(diǎn)的數(shù)量急劇增多. 它們不斷地重復(fù)更新不僅增加了運(yùn)算量,還放慢了收斂速度.

如果將邊緣層節(jié)點(diǎn)去除,不僅減少節(jié)點(diǎn)個數(shù),縮小網(wǎng)絡(luò)的規(guī)模,對算法的結(jié)果幾乎無影響,從而提高了算法的有效性.

預(yù)處理階段：僅賦予核心層的節(jié)點(diǎn)標(biāo)簽,同時去除邊緣層節(jié)點(diǎn),對預(yù)處理網(wǎng)絡(luò)進(jìn)行標(biāo)簽更新.

2.3 更新階段

預(yù)處理階段從網(wǎng)絡(luò)整體出發(fā)簡化初始網(wǎng)絡(luò). 而更新階段,則發(fā)生在網(wǎng)絡(luò)的局部. 更新節(jié)點(diǎn)的標(biāo)簽與其鄰居節(jié)點(diǎn)的標(biāo)簽有關(guān),它與鄰居節(jié)點(diǎn)的影響力大小相關(guān).K核分解是全局刻畫節(jié)點(diǎn)的影響力,并不能充分體現(xiàn)節(jié)點(diǎn)的局部影響力.

Kitsak等認(rèn)為度能刻畫節(jié)點(diǎn)周圍局部特征[9]. 因此引入歸一化度值作為節(jié)點(diǎn)的局部影響力.

為更加全面地衡量節(jié)點(diǎn)的影響力,將全局影響力k值和局部影響力lo相結(jié)合,得出節(jié)點(diǎn)在網(wǎng)絡(luò)中的綜合影響力.

原始算法中選擇其鄰居節(jié)點(diǎn)中出現(xiàn)頻率最高的標(biāo)簽作為更新節(jié)點(diǎn)的標(biāo)簽. 更新節(jié)點(diǎn)的標(biāo)簽除與鄰居節(jié)點(diǎn)的影響力大小相關(guān)外,還與鄰居中出現(xiàn)的標(biāo)簽個數(shù)相關(guān). 選擇其鄰居中影響力最大的標(biāo)簽.

Nl(x)是x的標(biāo)簽為l的鄰接節(jié)點(diǎn)集. 對于節(jié)點(diǎn)x,其標(biāo)簽為：

當(dāng)更新節(jié)點(diǎn)的鄰節(jié)點(diǎn)都沒有標(biāo)簽時,則選擇下一節(jié)點(diǎn)進(jìn)行更新; 如果鄰居節(jié)點(diǎn)有標(biāo)簽時,則根據(jù)式(7)選擇其中具有最大影響力的標(biāo)簽.

更新時確定的節(jié)點(diǎn)更新順序可有效降低隨機(jī)性.預(yù)處理僅賦予核心層節(jié)點(diǎn)標(biāo)簽,標(biāo)簽分布在網(wǎng)絡(luò)的中心. 為提高更新效率,節(jié)點(diǎn)應(yīng)從網(wǎng)絡(luò)中心向邊緣(節(jié)點(diǎn)影響力降序順序)大致有序進(jìn)行更新.

2.4 后處理階段

預(yù)處理網(wǎng)絡(luò)的社區(qū)劃分結(jié)束后,對邊緣層節(jié)點(diǎn)的標(biāo)簽進(jìn)行確定. 由于邊緣層節(jié)點(diǎn)的影響力相對較小,極易受到其鄰居中影響力大的節(jié)點(diǎn)影響. 因此其標(biāo)簽由鄰居中影響力最大的節(jié)點(diǎn)的標(biāo)簽所決定.

最后擁有相同標(biāo)簽的節(jié)點(diǎn)在同一個社區(qū).

算法分3個步驟：

(1)預(yù)處理階段

網(wǎng)絡(luò)進(jìn)行K核分解,劃分成核心-邊緣層. 賦予核心層節(jié)點(diǎn)標(biāo)簽,并去除邊緣層節(jié)點(diǎn).

(2)標(biāo)簽更新階段-預(yù)處理網(wǎng)絡(luò)

計(jì)算節(jié)點(diǎn)的綜合影響力,按影響力降序順序依次更新節(jié)點(diǎn);

依據(jù)式(7)選擇標(biāo)簽作為更新節(jié)點(diǎn)的標(biāo)簽;

若節(jié)點(diǎn)標(biāo)簽不再變化,算法結(jié)束.

(3)后處理階段

邊緣層節(jié)點(diǎn)的標(biāo)簽,根據(jù)式(8)選擇其鄰居中具有最大影響力的節(jié)點(diǎn)的標(biāo)簽.

最后,具有相同標(biāo)簽的節(jié)點(diǎn)劃分到同一個社區(qū).

相對于原始算法,改進(jìn)算法的預(yù)處理階段縮小了網(wǎng)絡(luò)規(guī)模,減小了更新時節(jié)點(diǎn)的運(yùn)算量改進(jìn)的更新策略降低了隨機(jī)性,加快了算法的收斂速度.

3 實(shí)驗(yàn)與分析

仿真工具M(jìn)ATLAB(matlab2012a,Win 7 64位,4 GB內(nèi)存). 為驗(yàn)證算法的有效性,實(shí)驗(yàn)數(shù)據(jù)采用真實(shí)網(wǎng)絡(luò)和LFR人工合成網(wǎng)絡(luò). 算法中存在隨機(jī)性,對實(shí)驗(yàn)運(yùn)行1000次后取均值.

3.1 真實(shí)網(wǎng)絡(luò)

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

網(wǎng)絡(luò)被劃分為4層,邊緣層的節(jié)點(diǎn)K=1,核心層節(jié)點(diǎn)K=4.將邊緣層節(jié)點(diǎn)去除后,得到一個53個節(jié)點(diǎn)和150條邊組成的新網(wǎng)絡(luò). 節(jié)點(diǎn)數(shù)減少14.5%,邊減少5.6%. 圖1為算法的劃分結(jié)果. 網(wǎng)絡(luò)被劃分為兩大社區(qū),與實(shí)際社區(qū)對比,節(jié)點(diǎn)的劃分準(zhǔn)確率為98%.為充分了解算法性能,將改進(jìn)算法與LPA和LPAD算法進(jìn)行實(shí)驗(yàn)對比,具體的實(shí)驗(yàn)數(shù)據(jù)結(jié)果如表1所示.

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

圖1 海豚網(wǎng)劃分圖

表1 海豚網(wǎng)數(shù)據(jù)結(jié)果

同時還對其他網(wǎng)絡(luò)進(jìn)行分析—Karate網(wǎng)絡(luò)、Football聯(lián)賽網(wǎng)絡(luò)、Polbooks聯(lián)賽網(wǎng)絡(luò),采用模塊度函數(shù)Q值、標(biāo)準(zhǔn)化互信息NMI值和迭代次數(shù)來對比算法性能,結(jié)果表2所示. 由表2可知KLPA算法的Q值和 NMI值大于LPA和 LPAD算法,說明KLPA算法獲得的社區(qū)質(zhì)量相對較高,社區(qū)劃分的準(zhǔn)確性也高于其他兩種算法. KLPA算法的迭代次數(shù)明顯低于LPA和LPAD算法,算法的收斂速度加快.

表2 實(shí)驗(yàn)網(wǎng)絡(luò)結(jié)果

3.2 LFR網(wǎng)絡(luò)

LFR基準(zhǔn)網(wǎng)絡(luò)常用來測試社區(qū)發(fā)現(xiàn)算法的性能.當(dāng)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)明顯時(0 0.45時),網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)變得越來越復(fù)雜,社區(qū)劃分效果也就變得較差.針對社區(qū)結(jié)構(gòu)復(fù)雜這種情況,對算法的性能進(jìn)行比. 網(wǎng)絡(luò)參數(shù)設(shè)置：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可知,無論網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)為1000或2000,當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)變得復(fù)雜時,兩種算法的準(zhǔn)確性均有所下降,但KLPA算法的NMI值明顯大于LPA算法.說明當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)較復(fù)雜時,KLPA算法的社區(qū)發(fā)現(xiàn)準(zhǔn)確性相對較高,具有比LPA算法更好的性能. 當(dāng)mu增大到0.65時,網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)變得模糊. 各社區(qū)間連接更加緊密,相互滲透,節(jié)點(diǎn)間的差異變小,算法很難發(fā)揮作用,準(zhǔn)確性大大降低,兩種算法失效.

圖2 LFR網(wǎng)絡(luò)NMI對比

同時對兩種算法的迭代次數(shù)進(jìn)行對比發(fā)現(xiàn),KLPA算法的迭代次數(shù)遠(yuǎn)遠(yuǎn)小于原始算法. 說明改進(jìn)算法加快了收斂速度,提高了效率. 當(dāng)mu>0.65時,LPA算法失效,迭代次數(shù)也就失去意義,如圖3所示.

圖3 迭代次數(shù)對比

4 結(jié)論

隨著網(wǎng)絡(luò)規(guī)模的增大,現(xiàn)有算法除準(zhǔn)確性和穩(wěn)定性問題外,算法的收斂速度也減緩. 本文從整體上利用K-Shell指數(shù)將網(wǎng)絡(luò)分層,一定程度上縮小網(wǎng)絡(luò)規(guī)模.并在局部對算法的更新策略加以改進(jìn). 仿真實(shí)驗(yàn)證明KLPA算法不僅可以縮小網(wǎng)絡(luò)規(guī)模,并能提高社區(qū)劃分的準(zhǔn)確性和穩(wěn)定性. 加快算法的收斂速度.

1 劉濤,陳忠,陳曉榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用研究概述. 系統(tǒng)工程,2005,23(6)：1-7.

2 周濤. 網(wǎng)絡(luò)大數(shù)據(jù)——復(fù)雜網(wǎng)絡(luò)的新挑戰(zhàn)：如何從海量數(shù)據(jù)獲取信息? 電子科技大學(xué)學(xué)報(bào),2013,42(1)：7-8.

3 劉發(fā)升,羅延榕. 基于多種群遺傳算法的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn). 計(jì)算機(jī)應(yīng)用研究,2012,29(4)：1237-1240.

4 張俊麗,常艷麗,師文. 標(biāo)簽傳播算法理論及其應(yīng)用研究綜述. 計(jì)算機(jī)應(yīng)用研究,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 趙卓翔,王軼彤,田家堂,等. 社會網(wǎng)絡(luò)中基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)新算法. 計(jì)算機(jī)研究與發(fā)展,2011,48(S2)：8-15.

7 顧亦然,王兵,孟繁榮. 一種基于K-Shell的復(fù)雜網(wǎng)絡(luò)重要節(jié)點(diǎn)發(fā)現(xiàn)算法. 計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(9)：70-74.

8 任曉龍,呂琳媛. 網(wǎng)絡(luò)重要節(jié)點(diǎn)排序方法綜述. 科學(xué)通報(bào),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]