基于多階鄰居殼數(shù)的向量中心性度量方法*

王凱莉 鄔春學(xué) 艾均? 蘇湛

(上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院, 上海 200093)

K-殼分解法在度量復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性方面具有重要的理論意義和應(yīng)用價(jià)值.但K-殼方法中, 存在大量殼值相等的節(jié)點(diǎn), 從而無法精確地比較這些具有相同殼值節(jié)點(diǎn)的相對重要性.因此, 本文基于網(wǎng)絡(luò)中節(jié)點(diǎn)自身殼值與其多階鄰居的殼值, 設(shè)計(jì)利用向量的形式來表示節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的相對重要性程度, 提出了多階鄰居殼數(shù)向量中心性方法, 并設(shè)計(jì)了該中心性向量比較方法.通過在七個真實(shí)網(wǎng)絡(luò)中進(jìn)行消息傳播與靜態(tài)攻擊實(shí)驗(yàn), 發(fā)現(xiàn)基于多階鄰居殼數(shù)向量的中心性方法具有計(jì)算復(fù)雜度低, 能夠有效發(fā)現(xiàn)具有高傳播能力的節(jié)點(diǎn), 在傳播實(shí)驗(yàn)中具有優(yōu)越的性能.并在靜態(tài)攻擊實(shí)驗(yàn)過程中傾向于優(yōu)先破壞網(wǎng)絡(luò)中的傳播核心結(jié)構(gòu).多階鄰居殼數(shù)向量中心性方法在保留K-殼中心性信息的前提下, 極大提高了節(jié)點(diǎn)重要性的區(qū)別程度, 平衡了對節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中聯(lián)通結(jié)構(gòu)的重要性的度量和對傳播結(jié)構(gòu)重要性的度量, 因此具有重要理論意義與應(yīng)用價(jià)值.

1 引 言

復(fù)雜網(wǎng)絡(luò)理論可以用來研究多種類型的復(fù)雜系統(tǒng), 這些系統(tǒng)中的主要元素被抽象成節(jié)點(diǎn), 主要元素間的關(guān)系抽象成節(jié)點(diǎn)之間的連邊.近些年來,科學(xué)界見證了復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域誕生了一系列的重要成果[1,2].除了針對邊進(jìn)行預(yù)測應(yīng)用在推薦系統(tǒng)等問題中之外[3,4], 復(fù)雜網(wǎng)絡(luò)模型里中心性研究也具有較高的應(yīng)用價(jià)值[5], 中心性是網(wǎng)絡(luò)拓?fù)渲卸攘抗?jié)點(diǎn)重要程度的一個指標(biāo)[6], 對中心性的研究工作有著非常重要的理論意義, 除了搜索引擎對網(wǎng)頁網(wǎng)絡(luò)的排序外, 還有對恐怖分子和毒品販賣等網(wǎng)絡(luò)進(jìn)行蓄意攻擊[7]、防止傳染病在生物群體中進(jìn)行傳播[8]、阻斷謠言的傳播[9]以及引導(dǎo)有效信息在網(wǎng)絡(luò)中迅速傳播[10]等等應(yīng)用領(lǐng)域[11].因此, 研究網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性程度具有重要的理論意義和應(yīng)用價(jià)值, 也是復(fù)雜網(wǎng)絡(luò)研究中的熱點(diǎn)問題之一[12,13].

經(jīng)典評估節(jié)點(diǎn)重要性的方法有度中心性(Degree)[14]、介數(shù)中心性(BC)[15]、接近中心性[16]和特征向量中心性(EC)等.度中心性僅考慮與該節(jié)點(diǎn)相連的鄰居節(jié)點(diǎn), 結(jié)果存在片面性, 而介數(shù)中心性和接近中心性都需要計(jì)算最短路徑, 計(jì)算過程相對復(fù)雜.于是在2010年Kitsak等[17]提出了K-殼分解法(K-shell), 他們認(rèn)為將網(wǎng)絡(luò)按層把節(jié)點(diǎn)移除, 越靠近殼心的節(jié)點(diǎn)重要性越高.K-殼分解法優(yōu)點(diǎn)在于方法簡單且計(jì)算復(fù)雜度低.研究表明[13], K-殼分解法的排序結(jié)果過于顆?；? 使得很多節(jié)點(diǎn)處在同一殼層上, 節(jié)點(diǎn)的重要性區(qū)分度不大.其次,K-殼分解法在網(wǎng)絡(luò)分解時僅考慮剩余度的影響,這相當(dāng)于認(rèn)為同一層的節(jié)點(diǎn)在外層的鄰居數(shù)目對節(jié)點(diǎn)重要性并不重要, 這樣得到的中心性是不合理的.

國內(nèi)外學(xué)者提出了基于K-殼的改進(jìn)方法.羅仕龍等[18]利用節(jié)點(diǎn)權(quán)重和權(quán)重分布重新定義邊的擴(kuò)散性, 提出適用于加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)的基于冗余邊過濾的 K-殼分解排序算法:filter-shell.Jiang 等[19]受K-殼分解方法去除外圍節(jié)點(diǎn)后網(wǎng)絡(luò)聚類系數(shù)會增大的啟發(fā), 選擇K-殼方法中殼值最高且相互連接的節(jié)點(diǎn)作為核心, 形成初始群來確定網(wǎng)絡(luò)節(jié)點(diǎn)的重要性.Gong和Kang[20]在K-殼方法的基礎(chǔ)上提出了一種新的社區(qū)網(wǎng)絡(luò)識別方法, 該方法能夠識別加速疾病傳播的有影響力的傳播者.朱曉霞等[21]為了對節(jié)點(diǎn)影響力給出具體排序, 在已有的各種最具影響力節(jié)點(diǎn)識別方法的基礎(chǔ)上, 提出了一種基于社團(tuán)結(jié)構(gòu)和K-shell節(jié)點(diǎn)法的節(jié)點(diǎn)影響力識別方法.其基本思想是利用某個節(jié)點(diǎn)處于不同社團(tuán)的鄰居節(jié)點(diǎn)的ks值判斷節(jié)點(diǎn)影響力, 以識別ks值相同的節(jié)點(diǎn)的不同影響力.李慧嘉[22,23]等利用動態(tài)迭代技術(shù), 提出了一種新型的社團(tuán)探測技術(shù), 能夠準(zhǔn)確而快速地識別網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).首先引入一種動態(tài)系統(tǒng), 可以使社團(tuán)歸屬從隨機(jī)狀態(tài)逐步收斂到最優(yōu)劃分, 進(jìn)一步利用嚴(yán)格的數(shù)學(xué)分析給出了社團(tuán)歸屬在離散時間內(nèi)收斂到最優(yōu)的條件.Zhang等[24]根據(jù)度值和核值的差值來識別復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn).在上述研究中討論了對網(wǎng)絡(luò)加權(quán)和引入社團(tuán)等信息來評估節(jié)點(diǎn)的重要性, 但是尚未討論目標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)對目標(biāo)節(jié)點(diǎn)重要性排序的影響.

在本文的研究中, 為了提高網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的區(qū)分度, 同時考慮在相同條件下提高重要節(jié)點(diǎn)的影響力范圍.本文提出了多階鄰居殼數(shù)的向量中心性方法:multi-order K-shell vector(MKV).通過對大量網(wǎng)絡(luò)進(jìn)行SI傳播實(shí)驗(yàn)和靜態(tài)攻擊網(wǎng)絡(luò)實(shí)驗(yàn)來驗(yàn)證MKV方法的有效性, 分別與度中性、K-殼中心性、介數(shù)中心性和特征向量中心性四種中心性方法進(jìn)行比較.實(shí)驗(yàn)結(jié)果表明, MKV方法的計(jì)算復(fù)雜度低, 在對網(wǎng)絡(luò)進(jìn)行靜態(tài)攻擊時, MKV方法能較大程度地破壞網(wǎng)絡(luò).本文提出的中心性方法有效地提高了節(jié)點(diǎn)的重要程度的區(qū)分度, 并且通過傳播實(shí)驗(yàn)分析發(fā)現(xiàn)該中心性方法具有較強(qiáng)的傳播能力.MKV方法能夠發(fā)現(xiàn)具有較強(qiáng)傳播能力的節(jié)點(diǎn),同時這些節(jié)點(diǎn)對網(wǎng)絡(luò)造成的破壞也遠(yuǎn)勝于K-殼方法.通過對真實(shí)的網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn), 對網(wǎng)絡(luò)進(jìn)行攻擊時, MKV方法能較大程度地破壞網(wǎng)絡(luò); 同時在網(wǎng)絡(luò)中進(jìn)行信息傳播時, MKV方法的傳播能力相對較強(qiáng), MKV方法可應(yīng)用于實(shí)際網(wǎng)絡(luò)中快速搜索具有傳播能力強(qiáng)的節(jié)點(diǎn).

2 基于多階鄰居殼數(shù)的向量中心性方法與現(xiàn)有經(jīng)典方法

2.1 基于多階鄰居殼數(shù)的向量中心性方法

本文的算法是基于K-殼分解法進(jìn)行的, K-殼分解法是一個遞歸的過程, 具體的分解過程如下:第一步, 找到網(wǎng)絡(luò)G中所有度值為1的節(jié)點(diǎn), 將度值為1的節(jié)點(diǎn)及其連邊一并刪除, 得到一個子網(wǎng)絡(luò)G1, 再選取子網(wǎng)絡(luò)G1中所有度值為1的節(jié)點(diǎn),將該類節(jié)點(diǎn)及其連邊刪除, 直至子網(wǎng)絡(luò)G2中不包含度值為1的子節(jié)點(diǎn).將這一步驟中刪除節(jié)點(diǎn)的殼值ks定義為1; 第二步, 刪除子網(wǎng)絡(luò)G2中度值為2的節(jié)點(diǎn)及其連邊, 重復(fù)第一步的遞歸過程, 將這一步驟中刪除節(jié)點(diǎn)的殼值ks定義為2.重復(fù)上述過程, 直到所有的點(diǎn)都分解到某個殼中[12].K-殼分解的示意圖如圖1所示.

圖1 K-shell分解法的示意圖Fig.1.A diagram of the K-shell.

發(fā)掘二階鄰居的方法[25]是:1)查找目標(biāo)節(jié)點(diǎn)vi的直接(一階)鄰居集合; 2)查找中包含的所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集且滿足以此類推, 得出節(jié)點(diǎn)vi的多階鄰居.

設(shè)計(jì)該算法的思路是因?yàn)樵贙-殼分解法中節(jié)點(diǎn)的區(qū)分度很低, 需要設(shè)計(jì)一種新的方法提高節(jié)點(diǎn)殼數(shù)所度量的區(qū)分度.本文將節(jié)點(diǎn)自身的殼值與其多階鄰居的殼值構(gòu)造一個向量, 把多階鄰居的殼數(shù)放入權(quán)值不同向量元素中, 通過一個向量而不是一個簡單的數(shù)值來度量節(jié)點(diǎn)的重要性程度, 該向量代表這個節(jié)點(diǎn)在網(wǎng)絡(luò)中能夠波及到的其各階鄰居節(jié)點(diǎn)的殼值的大小.

需要指出的是, 算法中多階鄰居的殼值, 指的是多階低殼值鄰居.計(jì)算目標(biāo)節(jié)點(diǎn)的多階鄰居過程中, 可能會出現(xiàn)部分殼值高于目標(biāo)節(jié)點(diǎn)殼值的鄰居, 在本文設(shè)計(jì)的算法中, 這些鄰居并不統(tǒng)計(jì).

對任意節(jié)點(diǎn)集合V中的節(jié)點(diǎn)vi, 該節(jié)點(diǎn)的多階鄰居節(jié)點(diǎn)集合為Ni.節(jié)點(diǎn)集合Ni中節(jié)點(diǎn)的數(shù)量為ni.設(shè)對每個節(jié)點(diǎn)vi都存在一個m維(每個網(wǎng)絡(luò)中節(jié)點(diǎn)最大的殼值是不同的, 此處的m是隨著網(wǎng)絡(luò)最大殼值的變化而變化的)向量xi, 可將其表示為xi=(xi1,xi2,···,xim)T.每一個向量xi中的元素xij可以通過如下的式子來計(jì)算j=1,2,···,m, 其中Mj(vk)是一個給定的中心性指標(biāo), 在本文的情況下, 是節(jié)點(diǎn)vk的 K-shell中心性,vk∈Ni.Cj(x)是一個如下給出的函數(shù).

圖2 MKV 算法實(shí)現(xiàn)流程圖Fig.2.MKV algorithm implementation flow chart.

通過流程圖可以看出, 算法通過不斷迭代, 將低殼數(shù)節(jié)點(diǎn)的信息記錄在對應(yīng)的高殼數(shù)鄰居的向量中, 故此最終形成的向量, 帶有該節(jié)點(diǎn)低殼數(shù)鄰居的信息, 而階數(shù)在同一網(wǎng)絡(luò)中固定不變, 在不同網(wǎng)絡(luò)中則不盡相同.

基于多階鄰居殼數(shù)的向量中心性構(gòu)造的基本思想是本文希望將一個簡單的殼值按照某種方式展開成一個向量.一方面, 該方法可以使得節(jié)點(diǎn)的重要性更具區(qū)分度, 另一方面, 也可以通過對每個節(jié)點(diǎn)的自身及其多階鄰居的綜合考察來考慮該節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度.這樣, 對于向量中的每個元素, 用一個數(shù)字來表示目標(biāo)節(jié)點(diǎn)有多少個多階鄰居節(jié)點(diǎn)具有某一殼層的殼值.對于節(jié)點(diǎn)vi, 向量xi中元素xi1保存的是目標(biāo)節(jié)點(diǎn)vi多階鄰居中殼數(shù)為1的節(jié)點(diǎn)總數(shù),xi2保存的是目標(biāo)節(jié)點(diǎn)vi多階鄰居中殼數(shù)為2的節(jié)點(diǎn)總數(shù), 以此類推,xin表示節(jié)點(diǎn)vi目標(biāo)節(jié)點(diǎn)自身的殼數(shù).因此, 目標(biāo)節(jié)點(diǎn)vi的多階鄰居通過向量中的不同元素將其考慮成具有幾個不同殼值等級, 這樣可以直觀地了解節(jié)點(diǎn)vi.

以圖1中的節(jié)點(diǎn)8和節(jié)點(diǎn)9為例來解釋向量的含義, 節(jié)點(diǎn) 8 的展開向量為x8= (1,3,1)T, 表示節(jié)點(diǎn)8的多階鄰居中殼值為1的節(jié)點(diǎn)個數(shù)有一個,是節(jié)點(diǎn)4, 殼值為2的節(jié)點(diǎn)數(shù)有3個, 分別是節(jié)點(diǎn)9、節(jié)點(diǎn) 10和節(jié)點(diǎn) 11, 節(jié)點(diǎn) 8自身的殼數(shù)是3; 節(jié)點(diǎn)9的展開向量為x9= (1,1,0)T, 該向量表示節(jié)點(diǎn)9的多階鄰居中殼值為1的節(jié)點(diǎn)存在一個, 是節(jié)點(diǎn)4, 節(jié)點(diǎn)9自身的殼數(shù)為2, 不存在殼數(shù)為3的多階鄰居.

多階鄰居的殼數(shù)向量能夠清楚地表明該節(jié)點(diǎn)在整個網(wǎng)絡(luò)中的潛在影響力, 不僅表明了節(jié)點(diǎn)的層次性, 還可以表明該節(jié)點(diǎn)在多階鄰居中的影響力.在K-shell方法中節(jié)點(diǎn)殼值相同時, 節(jié)點(diǎn)的影響力往往是不同的, 但是本文的方法可以度量出上述節(jié)點(diǎn)的重要性.

2.2 多階鄰居殼數(shù)向量的比較方法

給定任意的兩個向量xq∈X與xp∈X, 記ε=xq?xp=(ε1,ε2,···,εm)T.使

一個給定的二元關(guān)系如下:如果e*< 0, 那么xqxp, 對應(yīng)地,xq的迭代殼數(shù)的向量中心性小于xp.同理, 如果e*> 0, 那么xq?xp, 多階鄰居殼數(shù)向量xq大于xp.同理, 如果e*= 0, 那么xq=xp,也就是說多階鄰居殼數(shù)向量xq等于xp.

根據(jù)上述基于多階鄰居殼數(shù)向量的比較的定義, 向量比較算法流程圖如圖3所示.

本文下面將進(jìn)一步給出說明, 來證明本章的方法可以將目標(biāo)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行有效的排序,即, 向量集合S對于給定的二元關(guān)系是嚴(yán)格的全序集[26].

定理:二元關(guān)系使集合S是嚴(yán)格全序集, 等價(jià)于, 二元關(guān)系滿足如下條件:

1) ?x,y∈S,xy,yx,x=y三個式子中, 僅有一個成立(三分性);

2) ?x,y∈S, 如果xy, 那么yx不成立(不對稱性);

3) ?x,y,z∈S, 如果xy并且yz, 那么xz成立 (傳遞性).

證明如下:

首先, 對任意的x,y∈S, 使得x=x–y.那么一定有x*< 0,x*> 0 或x*= 0 三者當(dāng)中一個關(guān)系成立.因此, 基于二元關(guān)系的定義, 二元關(guān)系是三分的.

其次, 如果xy, 那么x*< 0.所以,x*>0 一定不成立, 也就等價(jià)于yx不成立.

最后, 對于任意給定的x,y,z∈S, 使得a=x–y,b=y–z, 那么x=a+b, 于是x?z=(x?y)?(y?z)=α+β=ξ.基于二元關(guān)系, 如果xy, 那么af< 0 或者af= 0 或者am< 0 中的某一個成立.類似地,yz意味著bf< 0 或者bf= 0或者bm< 0 中的某一個成立.因此,ξ?={ξf|ξf=0}∪{ξm|ξf=0}<0并且xz.綜上所述, 二元關(guān)系具有傳遞性.

通過上面的證明, 可以看出多階鄰居向量和二元關(guān)系的定義保證向量集合S是嚴(yán)格全序的.因此, 本文給出的定義也就能夠完成對所有節(jié)點(diǎn)重要性的排序.

2.3 相關(guān)常用中心性方法

2.3.1 度中心性 (Degree Centrality)

度中心性是指一個節(jié)點(diǎn)的度越大就意味著這個節(jié)點(diǎn)越重要.一個包含N個節(jié)點(diǎn)的網(wǎng)絡(luò)圖中, 節(jié)點(diǎn)度的中心性值定義為

其中ki表示節(jié)點(diǎn)i的度值,N– 1是指節(jié)點(diǎn)最大可能的度值為N– 1.

2.3.2 介數(shù)中心性 (Betweenness Centrality)

介數(shù)中心性是指經(jīng)過某個節(jié)點(diǎn)的最短路徑的數(shù)目來刻畫節(jié)點(diǎn)重要性的指標(biāo).將介數(shù)定義為

gst是從節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑數(shù)目,nsti是從節(jié)點(diǎn)s到節(jié)點(diǎn)t的gst條最短路徑中經(jīng)過節(jié)點(diǎn)i的最短路徑條數(shù).

2.3.3 特征向量中心性 (Eigenvector Centrality)

一個節(jié)點(diǎn)的重要性既取決于其鄰居節(jié)點(diǎn)的數(shù)量(即該節(jié)點(diǎn)的度), 也取決于其鄰居節(jié)點(diǎn)的重要性, 記xx為節(jié)點(diǎn)i的重要性度量值, 則:

圖3 向量比較大小算法流程圖Fig.3.Flow chart of vector comparison size algorithm.

其中c為一個比例常數(shù), 記x=[x1,x2,x3,···,xn]T,經(jīng)過多次迭代到達(dá)穩(wěn)態(tài)時, 可以寫成如下的矩陣形式:

2.4 基于多階鄰居殼數(shù)的向量中心性方法時間復(fù)雜度分析

假設(shè)圖G中節(jié)點(diǎn)個數(shù)為N, 邊的數(shù)量為M, 度中心性的計(jì)算復(fù)雜度在稠密矩陣中為O(N2), 在稀疏矩陣中為O(M); 早期的介數(shù)中心性的時間復(fù)雜度為O(N3)[27], Brandes[28]改進(jìn)的介數(shù)中心性時間復(fù)雜度為 O(NM); EC算法的時間復(fù)雜度為O(N2); K-shell的時間復(fù)雜度是O(N).

本文提出的MKV方法要對網(wǎng)絡(luò)中的每個節(jié)點(diǎn)的信息進(jìn)行記錄, 而對其中一個節(jié)點(diǎn)的鄰居進(jìn)行遍歷的時候, 效率最差的情況就是B樹的情形, 這種情形下時間復(fù)雜度是O(logN), 網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)是N, 所以MKV的時間復(fù)雜度是O(NlogN).

當(dāng)變量N增大時, 時間復(fù)雜度的排(序)是O((1)<)O(logN)

3 實(shí)驗(yàn)數(shù)據(jù)與分析

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

為了證明本文設(shè)計(jì)的多階鄰居殼數(shù)的向量中心性方法的有效性和適用性, 本文選用了七個經(jīng)典的復(fù)雜網(wǎng)絡(luò)模型:由小說《悲慘世界》中人物關(guān)系構(gòu)成的悲慘世界復(fù)雜網(wǎng)絡(luò)(簡記為LesMiserables)[29],美國西部電力網(wǎng)拓?fù)浣Y(jié)構(gòu)構(gòu)成的電力網(wǎng)(簡記為PowerGrid)[30], Rovira I Virgili大學(xué) (塔拉戈納)成員之間電子郵件交換組成的網(wǎng)絡(luò)(簡記為Email)[31], 2006年以前在網(wǎng)絡(luò)科學(xué)領(lǐng)域所有科學(xué)家的論文合作網(wǎng)絡(luò)數(shù)據(jù)集 (Coauthorships in network science, 簡記為 Coauthor)[32], 生活在新西蘭兩個街區(qū)的海豚之間的網(wǎng)絡(luò)(Dolphin social network, 簡記為 Dolphin)[33], 大腸桿菌代謝網(wǎng)絡(luò)(簡記為C.Elegans)[34]以及著名的空手道俱樂部數(shù)據(jù) (Zachary's karate club, 簡記為 Club)[35].上述這七個復(fù)雜網(wǎng)絡(luò)來源于大量的復(fù)雜網(wǎng)絡(luò)研究文獻(xiàn), 網(wǎng)絡(luò)的具體信息如表1所列.

3.2 中心性的區(qū)分度實(shí)驗(yàn)

對于任意一種給定的中心性方法, 求得的節(jié)點(diǎn)中心性在數(shù)值上會存在一致的, 這就代表中心性的值是重復(fù)的.在理論上, 具有相同中心性數(shù)值的節(jié)點(diǎn)的重要程度是沒有辦法區(qū)分的.而在一個有N個節(jié)點(diǎn)的網(wǎng)絡(luò)中, 中心性的重復(fù)度的定義為RR=r/N, 其中r表示該中心性方法中重復(fù)的中心性值的個數(shù), 而中心性的區(qū)分度則可以定義為DR=(N?r)/N[26].對本文用到的七個網(wǎng)絡(luò)的中心性區(qū)分度分析計(jì)算得到結(jié)果如表2所列.

根據(jù)中心性區(qū)分度的定義, 可以得出一個結(jié)論:中心性指標(biāo)的區(qū)分度DR值越大, 那么這就意味著網(wǎng)絡(luò)中節(jié)點(diǎn)重要程度的區(qū)分度就越高.通過表1得出, MKV方法的DR值要遠(yuǎn)遠(yuǎn)高于K-shell和度值中心性Degree, 雖然本文方法的中心性指標(biāo)的區(qū)分度DR比BC和EC小, 但是與BC的DR值已經(jīng)很是接近.由此可以得出, MKV方法明顯地提高了節(jié)點(diǎn)重要性的區(qū)分度.

表1 本文中用到的幾個網(wǎng)絡(luò)基本信息Table 1.Several basic network information used in this paper.

表2 中心性的區(qū)分度在不同網(wǎng)絡(luò)中的取值情況(越大越好)Table 2.Value of Centrality Distinction in Different Networks(the larger, the better).

3.3 基于多階鄰居殼數(shù)的向量中心性的復(fù)雜網(wǎng)絡(luò)的靜態(tài)攻擊

本文通過蓄意對網(wǎng)絡(luò)進(jìn)行靜態(tài)攻擊并觀察網(wǎng)絡(luò)的形態(tài), 以此來驗(yàn)證評估節(jié)點(diǎn)的重要性.具體過程如下:

1)計(jì)算每種中心性的度量值, 按照評估節(jié)點(diǎn)重要性算法的度量大小選取網(wǎng)絡(luò)中重要性最高的n個節(jié)點(diǎn);

2)蓄意地逐個移除網(wǎng)絡(luò)中選中的重要節(jié)點(diǎn)及其連邊;

3)計(jì)算并估計(jì)上述的攻擊過程對網(wǎng)絡(luò)造成的影響;

4)將刪除的節(jié)點(diǎn)數(shù)量從0.1%增加到30%, 重復(fù)上述過程, 觀察網(wǎng)絡(luò)的狀態(tài), 并做出相關(guān)記錄和分析.

在對復(fù)雜網(wǎng)絡(luò)進(jìn)行靜態(tài)攻擊的仿真實(shí)驗(yàn)中, 網(wǎng)絡(luò)受到攻擊后會破碎成零散的連接部件, 這些連接部件的數(shù)量表明了網(wǎng)絡(luò)的破碎程度.而網(wǎng)絡(luò)中的最大連通子團(tuán)可以表示剩余網(wǎng)絡(luò)的網(wǎng)絡(luò)連通性.所以在評判網(wǎng)絡(luò)的連通性時既要考慮子團(tuán)的數(shù)量, 也需要考慮最大連通子團(tuán)的節(jié)點(diǎn)數(shù)量.美國電力網(wǎng)power在蓄意攻擊后的最大連通子團(tuán)以及子團(tuán)數(shù)量的變化情況如圖4和圖5所示.

圖4 美國電力網(wǎng)power在靜態(tài)攻擊實(shí)驗(yàn)中最大連通子團(tuán)變化情況Fig.4.Largest connected component during static attack experiment on power.

圖5 美國電力網(wǎng)power在蓄意攻擊實(shí)驗(yàn)中子團(tuán)數(shù)量變化情況Fig.5.Total component number during static attack experiment on power.

最大連通子團(tuán)的節(jié)點(diǎn)數(shù)量越少表明網(wǎng)絡(luò)的連通性越差, 在網(wǎng)絡(luò)中移除的節(jié)點(diǎn)越重要.在圖4中,在刪除節(jié)點(diǎn)數(shù)量到2%的時候MKV方法中最大連通子團(tuán)的節(jié)點(diǎn)數(shù)量變化趨勢接近于除了Degree外的幾種方法, 而刪除節(jié)點(diǎn)大于2%時本文方法的最大子團(tuán)數(shù)量迅速減小, 相較于EC和K-shell兩種方法是有一定優(yōu)勢的, 當(dāng)移除節(jié)點(diǎn)達(dá)到15%后,MKV方法的結(jié)果要優(yōu)于其他方法.同樣的在圖5中, 子團(tuán)數(shù)量在刪除節(jié)點(diǎn)小于7%時, MKV方法和K-shell方法結(jié)果很相近, 而刪除節(jié)點(diǎn)高于13%時, MKV方法效果明顯優(yōu)于EC, BC和K-shell方法, 與 Degree 方法的結(jié)果趨于一致.Degree 方法在移除節(jié)點(diǎn)初期, 最大連通子團(tuán)節(jié)點(diǎn)數(shù)量變化明顯的原因是, 按Degree方法選擇的重要節(jié)點(diǎn)移除時, 節(jié)點(diǎn)的鄰居數(shù)量相對其他方法更多, 移除重要節(jié)點(diǎn)及其連邊后最大連通子團(tuán)的節(jié)點(diǎn)數(shù)量會銳減,同時子團(tuán)的數(shù)量會迅速上升.在power網(wǎng)絡(luò)的實(shí)驗(yàn)中, 攻擊開始初期, MKV方法的效果不及EC,BC和Degree, 但是后期的效果是具有優(yōu)勢的, 可見, 對網(wǎng)絡(luò)的蓄意攻擊, MKV方法盡可能考慮的是長期收益, 而非短期收益.

為了量化度量攻擊實(shí)驗(yàn)與節(jié)點(diǎn)重要性之關(guān)系,本文對上述七個網(wǎng)絡(luò)中選取移除節(jié)點(diǎn)的不同時間段的最大連通子團(tuán)節(jié)點(diǎn)數(shù)量和子團(tuán)數(shù)量進(jìn)行了統(tǒng)計(jì).選取 K-shell方法為基準(zhǔn)方法, 根據(jù)公式rl=a/b求出七個網(wǎng)絡(luò)在這些時間段的最大連通子團(tuán)數(shù)量的平均值和最大值, 此處的b表示K-shell最大連通子團(tuán)節(jié)點(diǎn)的數(shù)量,a分別代表其他四種中心性方法對網(wǎng)絡(luò)蓄意攻擊同時刻的最大連通子團(tuán)節(jié)點(diǎn)的數(shù)量, 則rl表示其他方法攻擊網(wǎng)絡(luò)核心結(jié)構(gòu)時最大連通子團(tuán)比K-shell方法提升了多少.同理, 子團(tuán)數(shù)量根據(jù)公式 r b=c/d求出其他方法在子團(tuán)數(shù)量上比K-shell方法優(yōu)化多少, 再統(tǒng)計(jì)其平均值和最小值, 此處的d代表K-shell中心性方法對網(wǎng)絡(luò)蓄意攻擊同時刻的連通子團(tuán)的數(shù)量,c表示其他方法得到的連通子團(tuán)的數(shù)量, 則 rb表示其他方法的子團(tuán)數(shù)量對比K-shell方法的提升.統(tǒng)計(jì)結(jié)果如圖6和圖7所示.

在圖6中, 以K-shell方法得到的結(jié)果為基準(zhǔn),其他方法分別與K-shell方法比較, 圖6中的值越小越好, 在不同的網(wǎng)絡(luò)中MKV方法要優(yōu)于K-shell方法, 與其他方法相比效果不明顯, 但是與度值相比, MKV方法提高了節(jié)點(diǎn)重要性的區(qū)分度, 與BC, EC方法相比, 在時間復(fù)雜度上得到了有效的提升.power網(wǎng)絡(luò)不是一個社交網(wǎng)絡(luò), 其平均路徑長度較大且聚類系數(shù)較低, 在這個網(wǎng)絡(luò)中最大連通子團(tuán)的效果相對是有提升的.因此對power這種類型的網(wǎng)絡(luò)進(jìn)行蓄意攻擊時, MKV方法更具優(yōu)勢.

圖6 七個網(wǎng)絡(luò)受到蓄意攻擊中最大連通子團(tuán)的統(tǒng)計(jì)情況(越小越好) (a) 最大連通子團(tuán)平均值情況; (b) 最大連通子團(tuán)最值情況Fig.6.Largest connected component during static attack experiments on the seven networks(the smaller, the better).

圖7 七個網(wǎng)絡(luò)靜態(tài)攻擊重要節(jié)點(diǎn)的子團(tuán)數(shù)量的統(tǒng)計(jì)情況(越大越好) (a) 子團(tuán)數(shù)量平均值情況; (b) 子團(tuán)數(shù)量最值情況Fig.7.The number of components during static attack experiments on the seven networks (the larger, the better).

在圖7中, 值越大表明網(wǎng)絡(luò)受到蓄意攻擊時得到的子團(tuán)數(shù)量越多, 網(wǎng)絡(luò)越破碎, 該度量節(jié)點(diǎn)重要性的方法就越具備優(yōu)勢.從圖7中看到五種評估節(jié)點(diǎn)重要性的方法得到的子團(tuán)數(shù)量的最終結(jié)果,MKV方法得到的子團(tuán)數(shù)量的結(jié)果要完全優(yōu)于K-shell方法.MKV方法的效果雖不及其他幾種方法, 但是在時間復(fù)雜度上要優(yōu)于BC和EC, 在節(jié)點(diǎn)重要性的區(qū)分度上要優(yōu)于度值中心性.在power網(wǎng)絡(luò)和dolphin網(wǎng)絡(luò)中, 子團(tuán)數(shù)量的效果占很大優(yōu)勢, 原因是這兩個網(wǎng)絡(luò)的聚集系數(shù)較低且平均路徑長度較長, 在這類網(wǎng)絡(luò)中, MKV方法得到的結(jié)果占優(yōu)勢.綜合上述圖片的內(nèi)容, 在對不同網(wǎng)絡(luò)進(jìn)行蓄意攻擊時, MKV方法明顯優(yōu)于K-shell方法.對于低聚類系數(shù)跟高平均路徑長度的網(wǎng)絡(luò), MKV方法是占優(yōu)勢的, 且效果相對明顯.MKV方法雖不是平均降低網(wǎng)絡(luò)連通性的最佳選擇, 但是MKV方法計(jì)算復(fù)雜度相對較低且傾向于優(yōu)先破壞網(wǎng)絡(luò)中的傳播核心結(jié)構(gòu).

3.4 基于多階鄰居殼數(shù)的向量中心性的復(fù)雜網(wǎng)絡(luò)傳播實(shí)驗(yàn)

本文采用SI(susceptible-infected)模型[36]來仿真網(wǎng)絡(luò)中重要節(jié)點(diǎn)的傳播行為, SI模型將傳染范圍內(nèi)的人群劃分為兩類:1) S 類:易感人群, 這類人是指還未染病但是與感染病患者接觸后以一定的概率a受到感染; 2) I類:染病人群, 這類人是指已經(jīng)患病的人群.SI傳染過程如圖8所示.

圖8 SI傳播模型圖Fig.8.SI propagation model diagram.

計(jì)算每種中心性的度量值, 將得出的度量值按數(shù)值降序排列, 選取網(wǎng)絡(luò)中每種中心性度量值最大的節(jié)點(diǎn)設(shè)置為感染節(jié)點(diǎn)I, 該節(jié)點(diǎn)以感染比率a去感染易感節(jié)點(diǎn), 將該傳染過程迭代M次, 統(tǒng)計(jì)感染節(jié)點(diǎn)的數(shù)量.并用所求得的感染節(jié)點(diǎn)數(shù)量來度量所選初始節(jié)點(diǎn)在網(wǎng)絡(luò)中的傳播能力.

以美國電力網(wǎng)power為例, 選取復(fù)雜網(wǎng)絡(luò)中按評估節(jié)點(diǎn)重要方法度量值最高的節(jié)點(diǎn)設(shè)置為感染節(jié)點(diǎn)I, 感染節(jié)點(diǎn)以a= 0.001的概率去感染易感節(jié)點(diǎn)S, 將這個過程迭代1000次, 統(tǒng)計(jì)出迭代過程結(jié)束后的感染節(jié)點(diǎn)數(shù)量, 選取部分迭代次數(shù)的感染節(jié)點(diǎn)的數(shù)量繪制統(tǒng)計(jì)圖.美國電力網(wǎng)power的不同迭代次數(shù)感染節(jié)點(diǎn)統(tǒng)計(jì)圖和大腸桿菌代謝網(wǎng)絡(luò)C.Elegans不同迭代次數(shù)感染節(jié)點(diǎn)統(tǒng)計(jì)圖如圖9和圖10所示.

在SI模型的實(shí)驗(yàn)中, 傳播感染的節(jié)點(diǎn)數(shù)量越多, 證明該節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度越高.如圖9中結(jié)果顯示的那樣, 多階鄰居殼數(shù)的向量中心性MKV在美國電力power網(wǎng)絡(luò)中傳播的效果是第二優(yōu)的, 通過分析得到EC算法的時間復(fù)雜度為O(N2), 而MKV方法是時間復(fù)雜度為O(NlogN),在相同的條件下, MKV的傳播效果雖然比EC的傳播效果差, 但是MKV方法要比EC的計(jì)算代價(jià)低.而在圖10大腸桿菌代謝網(wǎng)絡(luò) C.Elegans的SI傳播實(shí)驗(yàn)中, 迭代殼數(shù)的向量中心性MKV方法要優(yōu)于其他四種方法.因?yàn)楸疚牡哪康氖球?yàn)證哪個中心性參數(shù)在度量節(jié)點(diǎn)重要程度上有最好的結(jié)果, 所以本文試圖在這幾種中心性傳播過程中能感染最多的節(jié)點(diǎn).為了量化這一目標(biāo), 本文從上述七個網(wǎng)絡(luò)SI傳播實(shí)驗(yàn)中選取不同迭代次數(shù)的感染節(jié)點(diǎn)數(shù)對其統(tǒng)計(jì).rsi=p/q,q表示 K-shell方法感染節(jié)點(diǎn)數(shù)量,p表示其余中心性方法感染節(jié)點(diǎn)數(shù)量,rsi表示其他方法感染的節(jié)點(diǎn)數(shù)量要比K-shell方法感染節(jié)點(diǎn)的數(shù)量高多少, 分別求出這些時間段的平均值和最大值.統(tǒng)計(jì)結(jié)果如圖11所示.

圖9 美國電力網(wǎng)power在 SI傳播模型下感染節(jié)點(diǎn)的變化情況Fig.9.Change of infected nodes in Power of American Electric Power network under SI propagation model.

圖10 大腸桿菌代謝網(wǎng)絡(luò) C.Elegans 在 SI傳播模型下感染節(jié)點(diǎn)的變化情況Fig.10.Changes of infection nodes in C.Elegans network under SI propagation model.

圖11 七個網(wǎng)絡(luò)傳播感染節(jié)點(diǎn)的統(tǒng)計(jì)情況(越大越好) (a) SI傳播節(jié)點(diǎn)數(shù)量比較平均值; (b) SI傳播節(jié)點(diǎn)數(shù)量比較最值Fig.11.The statistical result of infected nodes of seven network (the larger, the better).

對網(wǎng)絡(luò)中進(jìn)行SI傳播實(shí)驗(yàn)時, 平均值和最大值的數(shù)值越大表明傳播感染節(jié)點(diǎn)的效果越明顯.在圖11中, 值越大表明感染的節(jié)點(diǎn)數(shù)量越多, 度量節(jié)點(diǎn)重要性的方法就越好.在上述七個網(wǎng)絡(luò)中,MKV方法得到的感染節(jié)點(diǎn)的數(shù)量與K-shell方法相比領(lǐng)先的比率是明顯的.在C.Elegans這個網(wǎng)絡(luò)中, MKV方法的傳播效果要完全優(yōu)于其他方法,在power網(wǎng)絡(luò)中MKV方法的傳播效果僅略低于EC方法傳播的效果, 除此之外, 感染節(jié)點(diǎn)的數(shù)量要遠(yuǎn)高于其他方法的平均值和最大值, 在Coauthors網(wǎng)絡(luò)和LesMiserables中MKV方法所占優(yōu)勢不太明顯, 原因是這兩個網(wǎng)絡(luò)的平均度值相對較大且網(wǎng)絡(luò)節(jié)點(diǎn)連接密集, 對該類型網(wǎng)絡(luò)進(jìn)行感染傳播時,MKV方法的優(yōu)勢不太明顯.因此在傳播感染的實(shí)驗(yàn)中, MKV在傳播過程中在大多數(shù)網(wǎng)絡(luò)中優(yōu)于K-shell方法, 在半數(shù)網(wǎng)絡(luò)中傳播的效果要優(yōu)于BC和Degree.MKV方法與度值相比, 提高了節(jié)點(diǎn)重要性的區(qū)分度, 而與 BC, EC 方法相比, 降低了時間復(fù)雜度, 所以MKV方法能夠快速有效地發(fā)現(xiàn)具有強(qiáng)傳播力的節(jié)點(diǎn), 是網(wǎng)絡(luò)傳播信息的最佳選擇.對于少數(shù)平均度值高、網(wǎng)絡(luò)連接密集的網(wǎng)絡(luò)MKV方法的傳播優(yōu)勢不太明顯; 但是能夠在大多數(shù)網(wǎng)絡(luò)中發(fā)現(xiàn)具有強(qiáng)傳播能力的節(jié)點(diǎn), MKV方法是信息傳播的最佳選擇.

4 結(jié) 論

本文提出了多階鄰居殼數(shù)的中心性方法,MKV方法將節(jié)點(diǎn)自身及多階鄰居節(jié)點(diǎn)的重要性考慮在內(nèi), 并通過對七個不同類型真實(shí)網(wǎng)絡(luò)進(jìn)行SI傳播和蓄意攻擊網(wǎng)絡(luò)兩種實(shí)驗(yàn), 與其他四種常用中心性方法進(jìn)行了比較.

結(jié)果表明:本文設(shè)計(jì)的MKV方法基于K殼中心性, 還保留了K殼中心性對節(jié)點(diǎn)在網(wǎng)絡(luò)中層次的信息, 同時展示出節(jié)點(diǎn)低階殼數(shù)鄰居的分布情況.此外, MKV方法具有高區(qū)別度、計(jì)算復(fù)雜度僅略高于度值, 但比度值提供了更多網(wǎng)絡(luò)結(jié)構(gòu)的信息; 在傳播效率上, 僅次于特性向量中心性, 計(jì)算卻更快捷; 在攻擊實(shí)驗(yàn)過程中絕大多數(shù)情況下優(yōu)于K殼中心性, 證明MKV方法在度量節(jié)點(diǎn)重要性程度上具有一定特點(diǎn)與部分優(yōu)勢.