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

王凱莉 鄔春學 艾均? 蘇湛

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

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

1 引 言

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

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

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

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

2 基于多階鄰居殼數的向量中心性方法與現有經典方法

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

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

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

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

設計該算法的思路是因為在K-殼分解法中節點的區分度很低, 需要設計一種新的方法提高節點殼數所度量的區分度.本文將節點自身的殼值與其多階鄰居的殼值構造一個向量, 把多階鄰居的殼數放入權值不同向量元素中, 通過一個向量而不是一個簡單的數值來度量節點的重要性程度, 該向量代表這個節點在網絡中能夠波及到的其各階鄰居節點的殼值的大小.

需要指出的是, 算法中多階鄰居的殼值, 指的是多階低殼值鄰居.計算目標節點的多階鄰居過程中, 可能會出現部分殼值高于目標節點殼值的鄰居, 在本文設計的算法中, 這些鄰居并不統計.

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

圖2 MKV 算法實現流程圖Fig.2.MKV algorithm implementation flow chart.

通過流程圖可以看出, 算法通過不斷迭代, 將低殼數節點的信息記錄在對應的高殼數鄰居的向量中, 故此最終形成的向量, 帶有該節點低殼數鄰居的信息, 而階數在同一網絡中固定不變, 在不同網絡中則不盡相同.

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

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

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

2.2 多階鄰居殼數向量的比較方法

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

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

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

本文下面將進一步給出說明, 來證明本章的方法可以將目標網絡中的所有節點進行有效的排序,即, 向量集合S對于給定的二元關系是嚴格的全序集[26].

定理:二元關系使集合S是嚴格全序集, 等價于, 二元關系滿足如下條件:

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 三者當中一個關系成立.因此, 基于二元關系的定義, 二元關系是三分的.

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

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

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

2.3 相關常用中心性方法

2.3.1 度中心性 (Degree Centrality)

度中心性是指一個節點的度越大就意味著這個節點越重要.一個包含N個節點的網絡圖中, 節點度的中心性值定義為

其中ki表示節點i的度值,N– 1是指節點最大可能的度值為N– 1.

2.3.2 介數中心性 (Betweenness Centrality)

介數中心性是指經過某個節點的最短路徑的數目來刻畫節點重要性的指標.將介數定義為

gst是從節點s到節點t的最短路徑數目,nsti是從節點s到節點t的gst條最短路徑中經過節點i的最短路徑條數.

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

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

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

其中c為一個比例常數, 記x=[x1,x2,x3,···,xn]T,經過多次迭代到達穩態時, 可以寫成如下的矩陣形式:

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

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

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

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

3 實驗數據與分析

3.1 實驗數據

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

3.2 中心性的區分度實驗

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

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

表1 本文中用到的幾個網絡基本信息Table 1.Several basic network information used in this paper.

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

3.3 基于多階鄰居殼數的向量中心性的復雜網絡的靜態攻擊

本文通過蓄意對網絡進行靜態攻擊并觀察網絡的形態, 以此來驗證評估節點的重要性.具體過程如下:

1)計算每種中心性的度量值, 按照評估節點重要性算法的度量大小選取網絡中重要性最高的n個節點;

2)蓄意地逐個移除網絡中選中的重要節點及其連邊;

3)計算并估計上述的攻擊過程對網絡造成的影響;

4)將刪除的節點數量從0.1%增加到30%, 重復上述過程, 觀察網絡的狀態, 并做出相關記錄和分析.

在對復雜網絡進行靜態攻擊的仿真實驗中, 網絡受到攻擊后會破碎成零散的連接部件, 這些連接部件的數量表明了網絡的破碎程度.而網絡中的最大連通子團可以表示剩余網絡的網絡連通性.所以在評判網絡的連通性時既要考慮子團的數量, 也需要考慮最大連通子團的節點數量.美國電力網power在蓄意攻擊后的最大連通子團以及子團數量的變化情況如圖4和圖5所示.

圖4 美國電力網power在靜態攻擊實驗中最大連通子團變化情況Fig.4.Largest connected component during static attack experiment on power.

圖5 美國電力網power在蓄意攻擊實驗中子團數量變化情況Fig.5.Total component number during static attack experiment on power.

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

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

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

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

圖7 七個網絡靜態攻擊重要節點的子團數量的統計情況(越大越好) (a) 子團數量平均值情況; (b) 子團數量最值情況Fig.7.The number of components during static attack experiments on the seven networks (the larger, the better).

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

3.4 基于多階鄰居殼數的向量中心性的復雜網絡傳播實驗

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

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

計算每種中心性的度量值, 將得出的度量值按數值降序排列, 選取網絡中每種中心性度量值最大的節點設置為感染節點I, 該節點以感染比率a去感染易感節點, 將該傳染過程迭代M次, 統計感染節點的數量.并用所求得的感染節點數量來度量所選初始節點在網絡中的傳播能力.

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

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

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

圖10 大腸桿菌代謝網絡 C.Elegans 在 SI傳播模型下感染節點的變化情況Fig.10.Changes of infection nodes in C.Elegans network under SI propagation model.

圖11 七個網絡傳播感染節點的統計情況(越大越好) (a) SI傳播節點數量比較平均值; (b) SI傳播節點數量比較最值Fig.11.The statistical result of infected nodes of seven network (the larger, the better).

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

4 結 論

本文提出了多階鄰居殼數的中心性方法,MKV方法將節點自身及多階鄰居節點的重要性考慮在內, 并通過對七個不同類型真實網絡進行SI傳播和蓄意攻擊網絡兩種實驗, 與其他四種常用中心性方法進行了比較.

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