羅仕龍 龔凱 唐朝生 周靖

1)(西南財(cái)經(jīng)大學(xué)經(jīng)濟(jì)信息工程學(xué)院,成都 611130)

2)(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,焦作 454000)

加權(quán)網(wǎng)絡(luò)中基于冗余邊過濾的k-核分解排序算法?

羅仕龍1)龔凱1)?唐朝生2)周靖1)

1)(西南財(cái)經(jīng)大學(xué)經(jīng)濟(jì)信息工程學(xué)院,成都 611130)

2)(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,焦作 454000)

加權(quán)網(wǎng)絡(luò),k-核分解,冗余邊,傳播影響力

1 引 言

現(xiàn)實(shí)社會(huì)中的許多系統(tǒng)都可以很自然地抽象成復(fù)雜網(wǎng)絡(luò)[1],例如航空網(wǎng)絡(luò)[2]、在線虛擬網(wǎng)絡(luò)[3]、社會(huì)網(wǎng)絡(luò)[4]等.在這些復(fù)雜網(wǎng)絡(luò)中,鑒別重要節(jié)點(diǎn)的研究工作對(duì)于預(yù)防基礎(chǔ)設(shè)施遭受攻擊[5]、阻止傳染病在人群中爆發(fā)[6?8]、抑制謠言信息在社會(huì)上擴(kuò)散[9]等方面有著非常重要的理論意義和指導(dǎo)作用.一般而言,重要節(jié)點(diǎn)是指具有重要傳播影響力的少數(shù)節(jié)點(diǎn)[10],通過傳播途徑快速地影響網(wǎng)絡(luò)上大多數(shù)節(jié)點(diǎn).因此,如何有效地度量網(wǎng)絡(luò)節(jié)點(diǎn)的傳播影響力既是發(fā)現(xiàn)重要節(jié)點(diǎn)的主要方法,也是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的熱點(diǎn)問題[11,12].

近年來,復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的核數(shù)研究引起了學(xué)者們的高度關(guān)注[13?15].核數(shù)(core)是指節(jié)點(diǎn)在網(wǎng)絡(luò)上的位置核心性[16],基本思想是通過遞歸過程移除網(wǎng)絡(luò)中當(dāng)前度數(shù)小于或等于k值的剩余節(jié)點(diǎn),剩下最大核數(shù)的節(jié)點(diǎn)組成網(wǎng)絡(luò)核心層.Kitsak等[17]基于k-核分解思想(k-shell decomposition),提出用核數(shù)度量節(jié)點(diǎn)的傳播影響力,取得了相比度數(shù)[18]和介數(shù)[19]更準(zhǔn)確的排序結(jié)果.k-核分解法優(yōu)點(diǎn)在于方法簡單且計(jì)算復(fù)雜度低,但存在排序結(jié)果粗?；热毕?國內(nèi)外學(xué)者對(duì)此提出了許多改良措施[20?25],這些研究多數(shù)都是基于無權(quán)網(wǎng)絡(luò)結(jié)構(gòu).有些學(xué)者[26?28]利用權(quán)重信息定義加權(quán)度數(shù)以替換核分解過程中的當(dāng)前剩余度,提出了加權(quán)網(wǎng)絡(luò)上的k-核排序算法.

最新實(shí)證研究發(fā)現(xiàn)[29],一些網(wǎng)絡(luò)上存在局域連接稠密的特殊構(gòu)型是導(dǎo)致k-核分解無效的根本原因之一.對(duì)此,文獻(xiàn)[30]提出過濾某些邊來減少稠密結(jié)構(gòu)對(duì)k-核分解過程造成干擾的方法,指出邊是否為應(yīng)該過濾的冗余邊(redundant links)取決于邊在傳播過程中具備的擴(kuò)散性(diffusion im-portance),并利用邊兩端節(jié)點(diǎn)的外部連邊數(shù)度量邊的擴(kuò)散性,但這種方法并不適用于加權(quán)網(wǎng)絡(luò).我們考慮到現(xiàn)實(shí)網(wǎng)絡(luò)上邊含有權(quán)重的普遍性,利用節(jié)點(diǎn)的權(quán)重特征重新定義邊的擴(kuò)散性,提出適用于加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)的基于冗余邊過濾的k-核分解排序算法: filter-core.仿真結(jié)果顯示,利用節(jié)點(diǎn)的權(quán)重特征過濾冗余邊后求得的節(jié)點(diǎn)核數(shù),能夠更準(zhǔn)確地度量加權(quán)網(wǎng)絡(luò)上重要節(jié)點(diǎn)的傳播影響力.本文結(jié)構(gòu)如下:首先提出節(jié)點(diǎn)權(quán)重和權(quán)重分布指數(shù)的計(jì)算方法,求出節(jié)點(diǎn)傳播系數(shù),根據(jù)兩端節(jié)點(diǎn)的傳播系數(shù)計(jì)算出邊的擴(kuò)散系數(shù),過濾該系數(shù)低于閾值的所有網(wǎng)絡(luò)邊;接著,在剩余網(wǎng)絡(luò)上實(shí)施k-核分解求出節(jié)點(diǎn)核數(shù);最后通過世界貿(mào)易網(wǎng)、線蟲腦細(xì)胞網(wǎng)和科學(xué)家合著網(wǎng)等真實(shí)加權(quán)網(wǎng)絡(luò)上的SIR(susceptible-infected-recovered)傳播仿真,分別與其他加權(quán)k-核分解法[26?28]的排序準(zhǔn)確性進(jìn)行比較分析.實(shí)驗(yàn)結(jié)果表明,本文算法能夠更準(zhǔn)確地識(shí)別加權(quán)網(wǎng)絡(luò)上具有重要傳播影響力的核心節(jié)點(diǎn)及核心層.

2 算法理論

最新研究證實(shí)[29],k-分解法在許多真實(shí)網(wǎng)絡(luò)上失效的根本原因之一是這些網(wǎng)絡(luò)中存在著局域連接稠密的微觀構(gòu)型,這些微觀構(gòu)型可以是稠密三角形,或是其他能夠形成稠密回路的特殊構(gòu)型.這些微觀構(gòu)型會(huì)導(dǎo)致k-分解過程把網(wǎng)絡(luò)上局域區(qū)域連接稠密的一些節(jié)點(diǎn)誤判為核心節(jié)點(diǎn),而這些節(jié)點(diǎn)影響力受限于連接稠密的局部區(qū)域,并不具備重要影響力;同時(shí),這些微觀構(gòu)型的稠密性也容易導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)的鄰居重疊程度過高,造成多源傳播覆蓋區(qū)域出現(xiàn)太多重疊,嚴(yán)重地制約多源傳播影響力.對(duì)此,文獻(xiàn)[30]提出一種過濾網(wǎng)絡(luò)冗余邊來減少稠密結(jié)構(gòu)從而提高k-核分解準(zhǔn)確性的方法,指出邊是否應(yīng)該過濾取決于該邊在傳播過程中具備的擴(kuò)散性,例如無權(quán)網(wǎng)絡(luò)上邊兩端節(jié)點(diǎn)的外部連邊數(shù)越多,意味著傳播途徑越廣,這條邊的擴(kuò)散性越強(qiáng).受到上述思想的啟發(fā),我們考慮到現(xiàn)實(shí)網(wǎng)絡(luò)上邊含有權(quán)重的普遍性[31],提出利用節(jié)點(diǎn)的權(quán)重特征重新定義邊的擴(kuò)散性.一般地,加權(quán)網(wǎng)絡(luò)上節(jié)點(diǎn)權(quán)重等于邊的權(quán)重和,其大小意味著該節(jié)點(diǎn)對(duì)周圍鄰居影響程度的強(qiáng)弱,同時(shí),邊的權(quán)重分布特征又意味著該節(jié)點(diǎn)在傳播過程中傳播途徑的多樣性或局限性[32].因此,我們認(rèn)為具備高權(quán)重且權(quán)重呈均勻分布特征的節(jié)點(diǎn)間的邊,能夠在傳播過程中起到很重要的擴(kuò)散作用.簡單地說,加權(quán)網(wǎng)絡(luò)上邊的擴(kuò)散性依賴于兩端節(jié)點(diǎn)的權(quán)重,也依賴于兩端節(jié)點(diǎn)的權(quán)重分布特征.本文用符號(hào)Iij表示邊的擴(kuò)散系數(shù),Ii表示節(jié)點(diǎn)的傳播系數(shù),Di表示節(jié)點(diǎn)權(quán)重,Hi表示節(jié)點(diǎn)權(quán)重分布指數(shù).這里,Iij通過計(jì)算邊兩端節(jié)點(diǎn)的傳播系數(shù)Ii求出:

利用邊的權(quán)重定義節(jié)點(diǎn)權(quán)重時(shí),最常見的做法是按照網(wǎng)絡(luò)邊的權(quán)重均值進(jìn)行歸一化處理[26],但這樣處理后的權(quán)重是一個(gè)絕對(duì)值.我們提出節(jié)點(diǎn)權(quán)重的計(jì)算公式如下:

這里wij表示邊eij的實(shí)際權(quán)重.為了量化節(jié)點(diǎn)的權(quán)重分布特征,參考文獻(xiàn)[33]中的度分布異質(zhì)指數(shù),本文提出權(quán)重分布指數(shù)Hi的計(jì)算式:

在附錄A中,我們利用Kendall[34]相關(guān)系數(shù)τ進(jìn)一步分析本文所提出的權(quán)重特征指標(biāo)與節(jié)點(diǎn)傳播影響力之間的相關(guān)性,結(jié)果表明τ(Ii)>τ(Di)>τ(Hi).

利用邊過濾后實(shí)施k-核數(shù)分解的思想, filtercore算法分成過濾和分解兩個(gè)階段.首先,在過濾階段,計(jì)算并求出原始網(wǎng)絡(luò)上所有邊的擴(kuò)散系數(shù)Iij.如果該系數(shù)小于閾值θ,則視為冗余邊進(jìn)行過濾,直至剩余網(wǎng)絡(luò)中所有邊的系數(shù)Iij都大于閾值.這里要根據(jù)具體情況進(jìn)行算法閾值θ的選取:選值過大會(huì)嚴(yán)重破壞網(wǎng)絡(luò)結(jié)構(gòu),得到的核數(shù)不能代表節(jié)點(diǎn)在原始網(wǎng)絡(luò)上的核心性;選值太小又無法實(shí)施有效地過濾.對(duì)此,我們遵循文獻(xiàn)[26]中提出的過濾后網(wǎng)絡(luò)核心層規(guī)模趨穩(wěn)作為選取閾值θ的依據(jù).接著,在核數(shù)分解階段,移除剩余網(wǎng)絡(luò)中當(dāng)前度數(shù)等于1的所有節(jié)點(diǎn),被移除后的節(jié)點(diǎn)處在網(wǎng)絡(luò)的邊緣核層,核數(shù)ks=1;繼續(xù)移除剩余度數(shù)等于2的網(wǎng)絡(luò)節(jié)點(diǎn),核數(shù)ks=2;直至所有節(jié)點(diǎn)都被賦予相應(yīng)的核數(shù)后,核數(shù)分解結(jié)束.此時(shí),最大核數(shù)的節(jié)點(diǎn)稱為網(wǎng)絡(luò)核心節(jié)點(diǎn),最大核數(shù)的核層稱為網(wǎng)絡(luò)核心層. filter-core算法在過濾階段的計(jì)算復(fù)雜度為分解階段[35]的計(jì)算復(fù)雜度為O(N+E),其中N表示網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模數(shù),E表示網(wǎng)絡(luò)邊數(shù).經(jīng)過數(shù)學(xué)推導(dǎo)可知,算法的計(jì)算復(fù)雜度為O(N+E3/2).

為了驗(yàn)證 filter-core算法與其他加權(quán)k-核分解法的排序優(yōu)劣,本文選用三種適用于加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)的k-核分解法:weighted degree方法[26]通過重新定義度數(shù)和權(quán)重的乘積關(guān)系作為k-核分解過程中使用的剩余度數(shù)(本文簡稱m-core),s-core算法[27]是利用節(jié)點(diǎn)的邊權(quán)重和進(jìn)行核數(shù)分解,weightedk-shell方法[28]將節(jié)點(diǎn)度數(shù)與權(quán)重的線性相加定義成核數(shù)分解時(shí)的剩余度數(shù)(本文簡稱p-core).

3 實(shí)驗(yàn)數(shù)據(jù)和算法應(yīng)用

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

本文實(shí)驗(yàn)數(shù)據(jù)選用三個(gè)真實(shí)加權(quán)網(wǎng)絡(luò):世界貿(mào)易網(wǎng)(ITN)[36]、線蟲腦細(xì)胞網(wǎng)(CEL)[37]和科學(xué)家合著網(wǎng)(SCIE)[38],來檢驗(yàn) filter-core算法度量節(jié)點(diǎn)傳播影響力的準(zhǔn)確性.其中,ITN權(quán)重表示國家之間的貿(mào)易額,權(quán)重分布接近廣延指數(shù)特征;CEL權(quán)重表示秀麗隱桿線蟲的細(xì)胞數(shù)量,權(quán)重冪率系數(shù)等于1.76±0.08;SCIE權(quán)重表示科學(xué)家之間合作發(fā)表的論文數(shù)量,權(quán)重分布呈指數(shù)特征.表1統(tǒng)計(jì)了網(wǎng)絡(luò)結(jié)構(gòu)特征量,?k?表示平均度,l表示節(jié)點(diǎn)間平均最短路徑,C表示聚類系數(shù)[39].可以看出,ITN表現(xiàn)出高聚類系數(shù)與短路徑的小世界特性,又具有度數(shù)分布服從無標(biāo)度的性質(zhì)[40].相反,CEL聚類系數(shù)偏低且路徑短,更接近隨機(jī)網(wǎng)絡(luò)結(jié)構(gòu).SCIE具有高聚類系數(shù)和路徑長的雙重特征,呈現(xiàn)規(guī)則網(wǎng)絡(luò)的特性.上述網(wǎng)絡(luò)表征不同的結(jié)構(gòu)特征,能夠更好地評(píng)估算法在真實(shí)加權(quán)網(wǎng)絡(luò)上的有效性.

表1 網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)特征量Table 1.Structural properties of real weighted networks.

圖1 核心層的節(jié)點(diǎn)規(guī)模隨閾值的變化 (a)ITN;(b)CEL;(c)SCIEFig.1.Scale of the max-core for different redundant link thresholds θ in weighted networks:(a)ITN;(b)CEL;(c)SCIE.

3.2 算法實(shí)際應(yīng)用

根據(jù)算法理論可知,閾值θ選取是根據(jù)過濾結(jié)束后網(wǎng)絡(luò)核心層規(guī)模是否趨穩(wěn)為依據(jù),圖1描述的是 filter-core算法應(yīng)用在具體網(wǎng)絡(luò)上的閾值選取過程.圖中橫坐標(biāo)表示閾值θ,縱坐標(biāo)表示核心層的節(jié)點(diǎn)規(guī)模數(shù).由圖1可見,隨著閾值θ的不斷增長,初期臃腫的核心層規(guī)模逐漸縮減,達(dá)到一定值時(shí),核心層規(guī)?；沮呌诜€(wěn)定.例如ITN網(wǎng)絡(luò)閾值θ=0時(shí),核心層規(guī)模數(shù)等于152;當(dāng)閾值θ>2.2時(shí),規(guī)模數(shù)在很長一段都穩(wěn)定在13附近.依據(jù)以上分析,得出θ(ITN)=2.3,θ(CEL)=2.5,θ(SCIE)=8.

為了進(jìn)一步分析 filter-core算法求出的核數(shù)能夠代表節(jié)點(diǎn)在原始網(wǎng)絡(luò)上的核心性,圖2描述了過濾閾值處的剩余網(wǎng)絡(luò)的完整情況,圖中縱坐標(biāo)表示極大連通系數(shù)gcc.極大連通系數(shù)是指過濾后最大連通網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模占原始網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模的比例,系數(shù)越大,說明剩余網(wǎng)絡(luò)的結(jié)構(gòu)完整性越高.觀察不難發(fā)現(xiàn)(圓圈符號(hào)),三個(gè)網(wǎng)絡(luò)在過濾閾值處都保持著較高的網(wǎng)絡(luò)完整性(gcc(ITN)=1,gcc(CEL)=0.84,gcc(SCIE)=0.54).相反,如果連邊擴(kuò)散系數(shù)Iij是根據(jù)兩端節(jié)點(diǎn)權(quán)重進(jìn)行計(jì)算(倒三角符號(hào)),將會(huì)明顯削弱剩余網(wǎng)絡(luò)的結(jié)構(gòu)完整性(gcc(ITN)=1,gcc(CEL)=0.74,gcc(SCIE)=0.05).同樣,如果按照兩端節(jié)點(diǎn)權(quán)重分布指數(shù)進(jìn)行計(jì)算時(shí)(上三角符號(hào)),剩余網(wǎng)絡(luò)結(jié)構(gòu)也會(huì)受到嚴(yán)重破壞.經(jīng)比較分析可知, filter-core算法選取閾值過濾后的剩余網(wǎng)絡(luò)結(jié)構(gòu)保持著較高的完整性,分解所得的核數(shù)能夠從很大程度上代表節(jié)點(diǎn)在原始網(wǎng)絡(luò)上的核心位置.

圖2 (網(wǎng)刊彩色)過濾閾值與剩余網(wǎng)絡(luò)完整性 (a)ITN;(b)CEL;(c)SCIEFig.2.(color online)Giant connected component gcc as the function of link filter threshold θ in weighted networks:(a)ITN;(b)CEL;(c)SCIE.

4 傳播模型與指標(biāo)

本文采用SIR模型[26]仿真加權(quán)網(wǎng)絡(luò)上的傳播過程.SIR模型是把節(jié)點(diǎn)按照健康狀態(tài)劃分成三類:易感態(tài)S是指當(dāng)前未感染但存在感染可能性的節(jié)點(diǎn),感染態(tài)I是指當(dāng)前患病且具有感染能力的節(jié)點(diǎn),康復(fù)態(tài)R是指已治愈且不再對(duì)傳播行為產(chǎn)生任何影響的節(jié)點(diǎn).感染節(jié)點(diǎn)以感染概率λ將傳染病傳給鄰居,感染節(jié)點(diǎn)以康復(fù)率β(取值等于1)進(jìn)行治愈并免疫.在加權(quán)網(wǎng)絡(luò)的傳播過程中,節(jié)點(diǎn)間的感染概率并非恒等[41].權(quán)重在傳播路徑上發(fā)揮著極其重要的作用,感染概率與節(jié)點(diǎn)同其自身鄰居間的權(quán)重關(guān)系密切相關(guān).根據(jù)文獻(xiàn)[26],感染概率λ的計(jì)算公式如下:

參數(shù)m表征疾病感染性的強(qiáng)弱或者謠言迷惑性的強(qiáng)弱等.傳播模型用符號(hào)M表示節(jié)點(diǎn)的傳播影響力:

其中Mi(n)表示節(jié)點(diǎn)vi在第n次傳播結(jié)束后的感染節(jié)點(diǎn)數(shù),Mi表示節(jié)點(diǎn)vi在ntol次傳播過程的感染節(jié)點(diǎn)平均數(shù).本文對(duì)每個(gè)網(wǎng)絡(luò)進(jìn)行ntol=105次的獨(dú)立重復(fù)實(shí)驗(yàn).

圖3描述了節(jié)點(diǎn)核數(shù)ks、節(jié)點(diǎn)傳播影響力均值?M?和模型參數(shù)m三者間的變化關(guān)系,圖中點(diǎn)線表示核數(shù)ks.觀察可見,高核數(shù)節(jié)點(diǎn)的傳播影響力總是大于核數(shù)居中和核數(shù)偏低的節(jié)點(diǎn).也就是說,當(dāng)參數(shù)m固定時(shí),核數(shù)ks越大,節(jié)點(diǎn)傳播影響力越強(qiáng).進(jìn)一步分析發(fā)現(xiàn),當(dāng)固定核數(shù)ks時(shí),參數(shù)m與節(jié)點(diǎn)傳播影響力?M?之間呈正相關(guān).參數(shù)m取值范圍有嚴(yán)格限制,取值太高會(huì)導(dǎo)致感染概率λ增大,造成任意節(jié)點(diǎn)都會(huì)以很高概率感染網(wǎng)絡(luò)其他節(jié)點(diǎn),無法有效地驗(yàn)證算法的優(yōu)劣.對(duì)此,參考原模型的取值方法,得出不同網(wǎng)絡(luò)的參數(shù)值:m(ITN)=6,m(CEL)=2,m(SCIE)=3.

基于SIR模型仿真,本文利用傳播誤差率ε、傳播發(fā)散性σ、傳播時(shí)間T和感染規(guī)模R等指標(biāo)比較分析 filter-core與其他加權(quán)k-核分解法的排序準(zhǔn)確性.傳播誤差率是指核數(shù)排序的結(jié)果與節(jié)點(diǎn)實(shí)際傳播影響力排序結(jié)果的符合度[17]:

其中p代表節(jié)點(diǎn)比例,Mfilter-core(p)表示按照k-核算法( filter-core)進(jìn)行核數(shù)降序的節(jié)點(diǎn)傳播影響力M的均值,Meff(p)表示根據(jù)節(jié)點(diǎn)實(shí)際傳播影響力降序的M均值.ε越小,說明排序結(jié)果的準(zhǔn)確性越高.傳播發(fā)散性σ是指核心節(jié)點(diǎn)的傳播影響力M與核心層里所有節(jié)點(diǎn)的平均傳播影響力的離散程度,即標(biāo)準(zhǔn)差:

其中ψ表示核心節(jié)點(diǎn)的集合,|ψ|表示核心節(jié)點(diǎn)的數(shù)量.σ越大,說明節(jié)點(diǎn)間的傳播影響力的離散程度越高.傳播時(shí)間T和感染規(guī)模R是指核心層里的核心節(jié)點(diǎn)作為多源傳播節(jié)點(diǎn),在傳播時(shí)間內(nèi)感染的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù).在規(guī)定傳播時(shí)間T內(nèi),感染規(guī)模R越大,說明整個(gè)核心層的傳播影響力越強(qiáng).

圖3 (網(wǎng)刊彩色)不同核數(shù)節(jié)點(diǎn)的傳播影響力隨m值的變化趨勢 (a)ITN;(b)CEL;(c)SCIEFig.3.(color online)Comparison of?M?vs.m for different cores in weighted networks:(a)ITN;(b)CEL;(c)SCIE.

5 結(jié)果分析

圖4描述了核數(shù)分解排序后的節(jié)點(diǎn)比例p與傳播誤差率ε的變化,橫坐標(biāo)表示按照核數(shù)降序的節(jié)點(diǎn)比例,縱坐標(biāo)表示傳播誤差率,圓圈符號(hào)(倒三角、方塊、十字)表示采用 filter-core算法(m-core,s-core,p-core)分解得到的核數(shù)排序結(jié)果,數(shù)值ε越低,說明排序準(zhǔn)確性越高.觀察圖4(a)不難發(fā)現(xiàn),f i lter-core核數(shù)排序后的誤差率最低;其次是s-core和p-core,這兩者排序的結(jié)果幾乎重疊但誤差率都不低;誤差率最高的是m-core分解后的核數(shù)排序.進(jìn)一步觀察圖4(b)和圖4(c)可見,我們提出的算法在CEL網(wǎng)絡(luò)和SCIE網(wǎng)絡(luò)上依然保持著較大優(yōu)勢,能夠很好地度量加權(quán)網(wǎng)絡(luò)上具有重要傳播影響力的少數(shù)節(jié)點(diǎn).

圖4 (網(wǎng)刊彩色)傳播誤差率隨節(jié)點(diǎn)比例的變化 (a)ITN;(b)CEL;(c)SCIEFig.4.(color online)The imprecision index ε as the function of node ratio p in weighted networks:(a)ITN;(b)CEL;(c)SCIE.

圖5 (網(wǎng)刊彩色)核心層節(jié)點(diǎn)的傳播發(fā)散性隨m值的變化 (a)—(c)ITN;(d)—(f)CEL;(g)—(i)SCIEFig.5.(color online)Standard deviation σ of each node’s spreading in fluence for max-core vs.m in weighted networks:(a)–(c)ITN;(d)–(f)CEL;(g)–(i)SCIE.

在k-核分解法中,最大核數(shù)的節(jié)點(diǎn)集構(gòu)成了網(wǎng)絡(luò)核心層,而處在核心層里的所有節(jié)點(diǎn)應(yīng)當(dāng)具有近似相同的傳播影響力[30].對(duì)此,進(jìn)一步比較分析if lter-core算法與其他加權(quán)k-核分解法找到的核心層節(jié)點(diǎn)在傳播發(fā)散性方面的優(yōu)劣表現(xiàn),如圖5所示.整體而言, filter-core算法在三個(gè)網(wǎng)絡(luò)上的傳播發(fā)散值σ在大多數(shù)時(shí)候都是最低,也就是說,本文算法找到的網(wǎng)絡(luò)核心層,其內(nèi)部核心節(jié)點(diǎn)之間的傳播影響力表現(xiàn)得最接近.觀察圖5(d)—(f)可以發(fā)現(xiàn),CEL網(wǎng)絡(luò)上的傳播參數(shù)m取值偏小時(shí), filter-core算法相比其他算法在傳播發(fā)散方面的優(yōu)勢并沒有受到影響,造成該現(xiàn)象的原因與網(wǎng)絡(luò)權(quán)重和網(wǎng)絡(luò)結(jié)構(gòu)都有關(guān):CEL網(wǎng)絡(luò)的權(quán)重分布具有冪率分布特征,這種分布特征有利于本文算法在參數(shù)m較小時(shí)依然能夠區(qū)分出具有重要擴(kuò)散性的網(wǎng)絡(luò)邊,有助于提高冗余邊過濾的效果.另外,k-核分解法不適用于Barabási-Albert(BA)無標(biāo)度網(wǎng)絡(luò)[20],根據(jù)表1結(jié)構(gòu)特征量分析得知,CEL網(wǎng)絡(luò)結(jié)構(gòu)更接近隨機(jī)網(wǎng)絡(luò).經(jīng)上述分析可知, filter-core算法更適用于權(quán)重分布具備冪率特征且結(jié)構(gòu)不具備BA無標(biāo)度的加權(quán)網(wǎng)絡(luò).

圖6描述了 filter-core算法與其他k-核分解法找到的核心層節(jié)點(diǎn)作為多源傳播節(jié)點(diǎn)時(shí),傳播時(shí)間T與感染規(guī)模R之間的變化.由圖6可見,ITN網(wǎng)絡(luò)感染規(guī)模R≈80%時(shí), filter-core算法的傳播時(shí)間T=2,相反其他算法的傳播時(shí)間T都大于6;在CEL網(wǎng)絡(luò)中,當(dāng)傳播時(shí)間T=8時(shí),相比score算法(m-core,p-core)感染規(guī)模R≈77%(70%,69%), filter-core算法的感染規(guī)模更高(R≈80%);在SCIE網(wǎng)絡(luò)中, filter-core算法在傳播時(shí)間T=10的感染規(guī)模R≈61%,明顯強(qiáng)過s-core算法(mcore,p-core)在相同傳播時(shí)間內(nèi)的感染情況(55%,53%,37%).分析可知, filter-core找到的核心層節(jié)點(diǎn)在多數(shù)傳播時(shí)間內(nèi)的感染規(guī)模都明顯高于其他k-核分解法.上述結(jié)果進(jìn)一步驗(yàn)證了我們算法能夠更準(zhǔn)確地度量加權(quán)網(wǎng)絡(luò)上核心節(jié)點(diǎn)的傳播影響力.

圖6 (網(wǎng)刊彩色)核心層節(jié)點(diǎn)的傳播時(shí)間與感染規(guī)模之間的變化 (a)—(c)ITN;(d)—(f)CEL;(g)—(i)SCIEFig.6.(color online)Spreading time T vs.number of recovered R pro files in weighted networks:(a)–(c)ITN;(d)–(f)CEL;(g)–(i)SCIE.

6 結(jié)論與展望

真實(shí)網(wǎng)絡(luò)上存在局域連接稠密的特殊構(gòu)型是導(dǎo)致k-核分解結(jié)果粗粒化的本質(zhì)原因之一.本文考慮到現(xiàn)實(shí)網(wǎng)絡(luò)上存在權(quán)重的普遍性,利用節(jié)點(diǎn)權(quán)重和權(quán)重分布定義邊的擴(kuò)散性進(jìn)而實(shí)施邊過濾,提出適用于加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)的基于冗余邊過濾的k-核分解排序算法: filter-core.通過對(duì)世界貿(mào)易網(wǎng)、線蟲腦細(xì)胞網(wǎng)和科學(xué)家合著網(wǎng)等真實(shí)數(shù)據(jù)的SIR傳播實(shí)驗(yàn)表明,該算法的傳播誤差率相比其他加權(quán)k-核分解法的值更低,該結(jié)果表明我們算法得出的節(jié)點(diǎn)核數(shù)能夠更準(zhǔn)確地度量加權(quán)網(wǎng)絡(luò)上重要節(jié)點(diǎn)的傳播影響力;利用傳播發(fā)散性、傳播時(shí)間和感染規(guī)模等指標(biāo)進(jìn)行比較分析,結(jié)果進(jìn)一步表明該算法能夠更準(zhǔn)確地識(shí)別加權(quán)網(wǎng)絡(luò)上具有重要傳播影響力的網(wǎng)絡(luò)核心層.

本文利用權(quán)重特征和邊過濾的思想對(duì)加權(quán)網(wǎng)絡(luò)上節(jié)點(diǎn)的核數(shù)排序進(jìn)行了研究,該工作有助于人們進(jìn)一步發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)上的重要節(jié)點(diǎn)以提高傳播效率或阻止疾病傳染及謠言傳播等,同時(shí)也為深入研究真實(shí)網(wǎng)絡(luò)的核心層結(jié)構(gòu)等后續(xù)工作提供了有力的支持.

感謝審稿專家對(duì)文章提出的寶貴意見和建議,這對(duì)本文研究工作的完善和提高起到了非常重要的作用.

附錄A 權(quán)重特征指標(biāo)與節(jié)點(diǎn)傳播影響力之間的相關(guān)性

這里采用Kendallτ相關(guān)系數(shù),基于真實(shí)加權(quán)網(wǎng)絡(luò)世界貿(mào)易網(wǎng)(ITN)、線蟲腦細(xì)胞網(wǎng)(CEL)和科學(xué)家合著網(wǎng)(SCIE),分析節(jié)點(diǎn)的權(quán)重特征指標(biāo)傳播系數(shù)Ii((2)式)、權(quán)重Di((3)式)和權(quán)重分布指數(shù)Hi((4)式)與節(jié)點(diǎn)的傳播影響力M((6)式)之間的相關(guān)性.觀察圖A1可見,綜合考慮權(quán)重和權(quán)重分布的節(jié)點(diǎn)傳播系數(shù)Ii與節(jié)點(diǎn)傳播影響力M的相關(guān)系數(shù)τ(ITN)=0.861,τ(CEL)=0.744,τ(SCIE)=0.371,明顯高于節(jié)點(diǎn)權(quán)重Di與傳播影響力M之間的相關(guān)系數(shù)τ(ITN)=0.738,τ(CEL)=0.648,τ(SCIE)=0.221,也明顯高于權(quán)重分布指數(shù)的相關(guān)系數(shù)τ(ITN)=0.531,τ(CEL)=0.597,τ(SCIE)=0.103. 結(jié)果表明,加權(quán)網(wǎng)絡(luò)上利用節(jié)點(diǎn)權(quán)重和權(quán)重分布能夠更準(zhǔn)確地反映出節(jié)點(diǎn)在傳播中的重要性,也進(jìn)一步說明利用邊兩端節(jié)點(diǎn)的傳播系數(shù)Ii可以更有效地度量邊在傳播過程中發(fā)揮的擴(kuò)散作用.

圖A1節(jié)點(diǎn)的權(quán)重特征指標(biāo)與傳播影響力之間的相關(guān)性 (a)—(c)ITN;(d)—(f)CEL;(g)—(i)SCIEFig.A1.M vs.measuring index pro files in weighted networks:(a)–(c)ITN;(d)–(f)CEL;(g)–(i)SCIE.

[1]Wang X F,Li X,Chen G R 2012Network Science:an Introduction(Beijing:Higher Education Press)pp3–18(in Chinese)[汪小帆,李翔,陳關(guān)榮2012網(wǎng)絡(luò)科學(xué)導(dǎo)論(北京:高等教育出版社)第3—18頁]

[2]Liu H K,Zhou T 2007Acta Phys.Sin.56 106(in Chinese)[劉宏鯤,周濤 2007物理學(xué)報(bào) 56 106]

[3]Zhang Z K,Liu C,Zhan X X,Lu X,Zhang C X,Zhang Y C 2016Phys.Rep.651 1

[4]Liu C,Zhan X X,Zhang Z K,Sun G Q,Hui P M 2015New J.Phys.17 113045

[5]Cohen R,Erez K,Benavraham D,Havlin S 2001Phys.Rev.Lett.86 3682

[6]Liu J G,Lin J H,Guo Q,Zhou T 2016Sci.Rep.6 21380

[7]Keeling M J,Rohani P 2008Modeling Infectious Diseases in Humans and Animals(Princeton:Princeton University Press)p366

[8]Gong K,Tang M,Hui P M,Zhang H F,Younghae D,Lai Y C 2013Plos One8 e83489

[9]Liu C,Zhang Z K 2014Commun.Nonlinear Sci.19 896

[10]Crucitti P,Latora V,Marchiori M,Rapisarda A 2004Physica A340 388

[11]Liu J G,Ren Z M,Guo Q,Wang B H 2013Acta Phys.Sin.62 178901(in Chinese)[劉建國,任卓明,郭強(qiáng),汪秉宏2013物理學(xué)報(bào)62 178901]

[12]Ren X L,Lü L Y 2014Chin.Sci.Bull.59 1175(in Chinese)[任曉龍,呂琳媛 2014科學(xué)通報(bào) 59 1175]

[13]Rombach M P,Porter M A,Fowler J H,Mucha P J 2014Siam J.Appl.Math.74 167

[14]Bassett D S,Wymbs N F,Rombach M P,Porter M A,Mucha P J,Grafton S T 2013Plos Comput.Biol.9 e1003171

[15]Liu J G,Ren Z M,Guo Q,Chen D B 2014Plos One9 e104028

[16]Seidman S B 1983Social Networks5 269

[17]Kitsak M,Gallos L K,Havlin S,Liljeros F,Muchnik L,Stanley H E,Makse H A 2010Nat.Phys.6 888

[18]Chen D,Lü L,Shang M S,Zhang Y C,Zhou T 2012Physica A391 1777

[19]Freeman L 1977Sociometry40 35

[20]Zeng A,Zhang C J 2013Phys.Lett.A377 1031

[21]Hou B,Yao Y,Liao D 2012Physica A391 4012

[22]Liu J G,Ren Z M,Guo Q 2013Physica A392 4154

[23]Hu Q C,Yin Y S,Ma P F,Gao Y,Zhang Y,Xing C X 2013Acta Phys.Sin.62 140101(in Chinese)[胡慶成,尹龑燊,馬鵬斐,高旸,張勇,邢春曉2013物理學(xué)報(bào)62 140101]

[24]Ren Z M,Liu J G,Shao F,Hu Z L,Guo Q 2013Acta Phys.Sin.62 108902(in Chinese)[任卓明,劉建國,邵鳳,胡兆龍,郭強(qiáng)2013物理學(xué)報(bào)62 108902]

[25]Cao J X,Dong D,Xu S,Zheng X,Liu B,Luo J Z 2015Chin.J.Comput.38 238(in Chinese)[曹玖新,董丹,徐順,鄭嘯,劉波,羅軍舟2015計(jì)算機(jī)學(xué)報(bào)38 238]

[26]Garas A,Schweitzer F,Havlin S 2012New J.Phys.14 83030

[27]Eidsaa M,Almaas E 2013Phys.Rev.E88 062819

[28]Wei B,Liu J,Wei D,Gao C,Deng Y 2015Physica A420 277

[29]Liu Y,Tang M,Zhou T,Do Y 2015Sci.Rep.5 9602

[30]Liu Y,Tang M,Zhou T,Do Y 2015Sci.Rep.5 13172

[31]Barrat A,Barthélemy M,Pastor-Satorras R,Vespignani A 2004Proc.Natl.Acad.Sci.USA101 3747

[32]Yan W,Zhou T,Wang J,Fu Z Q,Wang B H 2005Chin.Phys.Lett.22 510

[33]Hu H B,Wang X F 2008Physica A387 3769

[34]Kendall M G 1938Biometrika30 81

[35]Batagelj V,Zaversnik M 2003 arXiv:cs/0310049v1

[36]Lee K M,Yang J S,Kim G,Lee J,Goh K I,Kim I M 2011Plos One6 e18443

[37]Watts D J,Strogatz S H 1998Nature393 440

[38]Newman M E J 2006Phys.Rev.E74 036104

[39]Saram?ki J,Kivel? M,Onnela J P,Kaski K,Kertész J 2007Phys.Rev.E75 027105

[40]Li X,Jin Y Y,Chen G R 2003Physica A328 287

[41]Yan G,Fu Z Q,Chen G 2008Eur.Phys.J.B65 591

A ranking approach based onk-shell decomposition method by filtering out redundant link in weighted networks?

Luo Shi-Long1)Gong Kai1)?Tang Chao-Sheng2)Zhou Jing1)

1)(School of Economic Information Engineering,Southwestern University of Finance and Economics,Chengdu 611130,China)

2)(School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000,China)

16 December 2016;revised manuscript

21 June 2017)

Thek-shell decomposition method of identifying the in fluential nodes which accelerate spread or hinder propagation,plays an important role in analyzing the spreading performance of complex network,but it is too coarse in terms of ranking granularity.Recent study shows that the accuracy of thek-shell decomposition method in determining node coreness is significantly affected by the mutually densely connected local structures.Existing approach tries to filter out the confusion of the classicalk-shell decomposition method,caused by such densely local structures,through rede fining a diffusion importance value which is the number of out-leaving links at/from the nodes connected by a link.This value is used to quantify the potential in fluence of a link in spreading process.However,the existing approach is not suitable for ubiquitously weighted networks.In this paper,we develop a new ranking approach( filter-core)to identify the node spreading in fluence in weighted network.Here,we concern that the redundant links,although they are less important in the spreading process,form mutually densely connected local structures,which lead to the classicalk-shell decomposition method unable to accurately determine the coreness of node in network.By rede fining a new diffusion importance value for each link based on the weights of its connected nodes and the weight distribution,we filter out the redundant links which have a relatively low diffusion importance in the spreading process.After filtering out all redundant links and applying the classicalk-shell decomposition method to the residual network,we obtain a new coreness for each node,which is more accurate to indicate spreading in fluence of node in the original network.Our approach is applied to three real weighted networks,i.e.,the international trading network,the neural network of C.elegans,and the coauthorship network of scientists.And the susceptible-infected-recovered epidemic spreading model is used to make a comparison of performance between our approach and other threek-shell methods(including the weighted degree decomposition method,the s-core decomposition method,and the weightedk-shell method)in terms of four quantitative indices,i.e.,the imprecision function,the standard deviation of infected fraction of max coreness node,the spreading time,and the number of recovered nodes at the end of spreading process.The experimental results show that our proposed approach is more accurate to identify the in fluential spreaders than the weighted degree decomposition method,the score decomposition method,and the weightedk-shell method,and also helps to more accurately decompose the network core structure for an optimal analysis in weighted network.

weighted networks,k-shell decomposition,redundant link,spreading in fluence

PACS:89.75.–k,89.75.Fb,05.10.–aDOI:10.7498/aps.66.188902

*Project supported by the National Natural Science Foundation of China(Grant No.61602331),the Fundamental Research Funds for the Central Universities of Ministry of Education of China(Grant Nos.JBK170133,JBK160130,JBK150503),the Scientific Research Foundation of the Education Department of Sichuan Province,China(Grant No.17ZB0434),and the Collaborative Innovation Center for Electronic Finance and Financial Regulation.

?Corresponding author.E-mail:gongkai1210@swufe.edu.cn

(2016年12月16日收到;2017年6月21日收到修改稿)

k-核分解排序法對(duì)于度量復(fù)雜網(wǎng)絡(luò)上重要節(jié)點(diǎn)的傳播影響力具有重要的理論意義和應(yīng)用價(jià)值,但其排序粗?；娜毕菀膊蝗莺鲆?最新研究發(fā)現(xiàn),一些真實(shí)網(wǎng)絡(luò)中存在局域連接稠密的特殊構(gòu)型是導(dǎo)致上述問題的根本原因之一.當(dāng)前的解決方法是利用邊兩端節(jié)點(diǎn)的外部連邊數(shù)度量邊的擴(kuò)散性,采取過濾網(wǎng)絡(luò)邊來減少這種稠密結(jié)構(gòu)給k-核分解過程造成的干擾,但這種方法并沒有考慮現(xiàn)實(shí)網(wǎng)絡(luò)上存在權(quán)重的普遍性.本文利用節(jié)點(diǎn)權(quán)重和權(quán)重分布重新定義邊的擴(kuò)散性,提出適用于加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)的基于冗余邊過濾的k-核分解排序算法: filter-core.通過世界貿(mào)易網(wǎng)、線蟲腦細(xì)胞網(wǎng)和科學(xué)家合著網(wǎng)等真實(shí)網(wǎng)絡(luò)的SIR(susceptible-infectedrecovered)傳播模型的仿真結(jié)果表明,該算法相比其他加權(quán)k-核分解法,能夠更準(zhǔn)確地度量加權(quán)網(wǎng)絡(luò)上具有重要傳播影響力的核心節(jié)點(diǎn)及核心層.

10.7498/aps.66.188902

?國家自然科學(xué)基金(批準(zhǔn)號(hào):61602331)、中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(批準(zhǔn)號(hào):JBK170133,JBK160130,JBK150503)、四川省教育廳科研基金(批準(zhǔn)號(hào):J17ZB0434)和互聯(lián)網(wǎng)金融創(chuàng)新及監(jiān)管協(xié)同創(chuàng)新中心資助的課題.

?通信作者.E-mail:gongkai1210@swufe.edu.cn