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

羅仕龍 龔凱 唐朝生 周靖

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

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

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

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

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

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

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

1 引 言

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

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

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

2 算法理論

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

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

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

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

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

為了驗證 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é)點的邊權(quán)重和進行核數(shù)分解,weightedk-shell方法[28]將節(jié)點度數(shù)與權(quán)重的線性相加定義成核數(shù)分解時的剩余度數(shù)(本文簡稱p-core).

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

3.1 實驗數(shù)據(jù)

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

表1 網(wǎng)絡(luò)拓撲的結(jié)構(gòu)特征量Table 1.Structural properties of real weighted networks.

圖1 核心層的節(jié)點規(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 算法實際應(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é)點規(guī)模數(shù).由圖1可見,隨著閾值θ的不斷增長,初期臃腫的核心層規(guī)模逐漸縮減,達到一定值時,核心層規(guī)模基本趨于穩(wěn)定.例如ITN網(wǎng)絡(luò)閾值θ=0時,核心層規(guī)模數(shù)等于152;當(dāng)閾值θ>2.2時,規(guī)模數(shù)在很長一段都穩(wěn)定在13附近.依據(jù)以上分析,得出θ(ITN)=2.3,θ(CEL)=2.5,θ(SCIE)=8.

為了進一步分析 filter-core算法求出的核數(shù)能夠代表節(jié)點在原始網(wǎng)絡(luò)上的核心性,圖2描述了過濾閾值處的剩余網(wǎng)絡(luò)的完整情況,圖中縱坐標(biāo)表示極大連通系數(shù)gcc.極大連通系數(shù)是指過濾后最大連通網(wǎng)絡(luò)的節(jié)點規(guī)模占原始網(wǎng)絡(luò)節(jié)點規(guī)模的比例,系數(shù)越大,說明剩余網(wǎng)絡(luò)的結(jié)構(gòu)完整性越高.觀察不難發(fā)現(xiàn)(圓圈符號),三個網(wǎng)絡(luò)在過濾閾值處都保持著較高的網(wǎng)絡(luò)完整性(gcc(ITN)=1,gcc(CEL)=0.84,gcc(SCIE)=0.54).相反,如果連邊擴散系數(shù)Iij是根據(jù)兩端節(jié)點權(quán)重進行計算(倒三角符號),將會明顯削弱剩余網(wǎng)絡(luò)的結(jié)構(gòu)完整性(gcc(ITN)=1,gcc(CEL)=0.74,gcc(SCIE)=0.05).同樣,如果按照兩端節(jié)點權(quán)重分布指數(shù)進行計算時(上三角符號),剩余網(wǎng)絡(luò)結(jié)構(gòu)也會受到嚴重破壞.經(jīng)比較分析可知, filter-core算法選取閾值過濾后的剩余網(wǎng)絡(luò)結(jié)構(gòu)保持著較高的完整性,分解所得的核數(shù)能夠從很大程度上代表節(jié)點在原始網(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é)點按照健康狀態(tài)劃分成三類:易感態(tài)S是指當(dāng)前未感染但存在感染可能性的節(jié)點,感染態(tài)I是指當(dāng)前患病且具有感染能力的節(jié)點,康復(fù)態(tài)R是指已治愈且不再對傳播行為產(chǎn)生任何影響的節(jié)點.感染節(jié)點以感染概率λ將傳染病傳給鄰居,感染節(jié)點以康復(fù)率β(取值等于1)進行治愈并免疫.在加權(quán)網(wǎng)絡(luò)的傳播過程中,節(jié)點間的感染概率并非恒等[41].權(quán)重在傳播路徑上發(fā)揮著極其重要的作用,感染概率與節(jié)點同其自身鄰居間的權(quán)重關(guān)系密切相關(guān).根據(jù)文獻[26],感染概率λ的計算公式如下:

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

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

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

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

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

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

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

圖4 (網(wǎng)刊彩色)傳播誤差率隨節(jié)點比例的變化 (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é)點的傳播發(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é)點集構(gòu)成了網(wǎng)絡(luò)核心層,而處在核心層里的所有節(jié)點應(yīng)當(dāng)具有近似相同的傳播影響力[30].對此,進一步比較分析if lter-core算法與其他加權(quán)k-核分解法找到的核心層節(jié)點在傳播發(fā)散性方面的優(yōu)劣表現(xiàn),如圖5所示.整體而言, filter-core算法在三個網(wǎng)絡(luò)上的傳播發(fā)散值σ在大多數(shù)時候都是最低,也就是說,本文算法找到的網(wǎng)絡(luò)核心層,其內(nèi)部核心節(jié)點之間的傳播影響力表現(xiàn)得最接近.觀察圖5(d)—(f)可以發(fā)現(xiàn),CEL網(wǎng)絡(luò)上的傳播參數(shù)m取值偏小時, 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較小時依然能夠區(qū)分出具有重要擴散性的網(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)更接近隨機網(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é)點作為多源傳播節(jié)點時,傳播時間T與感染規(guī)模R之間的變化.由圖6可見,ITN網(wǎng)絡(luò)感染規(guī)模R≈80%時, filter-core算法的傳播時間T=2,相反其他算法的傳播時間T都大于6;在CEL網(wǎng)絡(luò)中,當(dāng)傳播時間T=8時,相比score算法(m-core,p-core)感染規(guī)模R≈77%(70%,69%), filter-core算法的感染規(guī)模更高(R≈80%);在SCIE網(wǎng)絡(luò)中, filter-core算法在傳播時間T=10的感染規(guī)模R≈61%,明顯強過s-core算法(mcore,p-core)在相同傳播時間內(nèi)的感染情況(55%,53%,37%).分析可知, filter-core找到的核心層節(jié)點在多數(shù)傳播時間內(nèi)的感染規(guī)模都明顯高于其他k-核分解法.上述結(jié)果進一步驗證了我們算法能夠更準確地度量加權(quán)網(wǎng)絡(luò)上核心節(jié)點的傳播影響力.

圖6 (網(wǎng)刊彩色)核心層節(jié)點的傳播時間與感染規(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é)論與展望

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

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

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

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

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

圖A1節(jié)點的權(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é)報 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)[劉建國,任卓明,郭強,汪秉宏2013物理學(xué)報62 178901]

[12]Ren X L,Lü L Y 2014Chin.Sci.Bull.59 1175(in Chinese)[任曉龍,呂琳媛 2014科學(xué)通報 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é)報62 140101]

[24]Ren Z M,Liu J G,Shao F,Hu Z L,Guo Q 2013Acta Phys.Sin.62 108902(in Chinese)[任卓明,劉建國,邵鳳,胡兆龍,郭強2013物理學(xué)報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計算機學(xué)報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-核分解排序法對于度量復(fù)雜網(wǎng)絡(luò)上重要節(jié)點的傳播影響力具有重要的理論意義和應(yīng)用價值,但其排序粗?；娜毕菀膊蝗莺鲆?最新研究發(fā)現(xiàn),一些真實網(wǎng)絡(luò)中存在局域連接稠密的特殊構(gòu)型是導(dǎo)致上述問題的根本原因之一.當(dāng)前的解決方法是利用邊兩端節(jié)點的外部連邊數(shù)度量邊的擴散性,采取過濾網(wǎng)絡(luò)邊來減少這種稠密結(jié)構(gòu)給k-核分解過程造成的干擾,但這種方法并沒有考慮現(xiàn)實網(wǎng)絡(luò)上存在權(quán)重的普遍性.本文利用節(jié)點權(quán)重和權(quán)重分布重新定義邊的擴散性,提出適用于加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)的基于冗余邊過濾的k-核分解排序算法: filter-core.通過世界貿(mào)易網(wǎng)、線蟲腦細胞網(wǎng)和科學(xué)家合著網(wǎng)等真實網(wǎng)絡(luò)的SIR(susceptible-infectedrecovered)傳播模型的仿真結(jié)果表明,該算法相比其他加權(quán)k-核分解法,能夠更準確地度量加權(quán)網(wǎng)絡(luò)上具有重要傳播影響力的核心節(jié)點及核心層.

10.7498/aps.66.188902

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

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