基于多重影響力矩陣的有向加權網絡節點重要性評估方法?

王雨 郭進利

(上海理工大學管理學院,上海 200093)

基于多重影響力矩陣的有向加權網絡節點重要性評估方法?

王雨 郭進利?

(上海理工大學管理學院,上海 200093)

(2016年10月15日收到;2016年11月23日收到修改稿)

本文基于有向加權網絡模型,構建了三個影響力矩陣,并利用層次分析法對其賦權求和,形成多重影響力矩陣,從而提出了一種基于該矩陣的節點重要性評價方法.該方法通過新定義的交叉強度指標,來表征節點的局部重要性;利用全網節點對待評估節點的重要性影響總值,來表征節點在全網中的相對重要性.在分析影響節點對待評估節點的影響比例時,既考慮到節點間的距離因素,又引入了最短路徑條數因素;既考慮了該影響節點對網絡中其他節點的影響關系,又考慮了網絡中其他節點對該待評估節點的影響關系,使得評價方法更加全面.將算法運用于ARPA網絡,結果表明,該方法能有效地區分各節點之間的差異.最后,對實驗結果進行連鎖故障的仿真對比實驗,進一步驗證了方法的有效性.

有向加權網絡,節點重要性,多重影響力矩陣,最短路徑條數

1 引 言

復雜網絡具有非同質的拓撲結構,這決定了網絡中的每個節點不可能具有完全相同的重要程度[1].因此,采用定量方法挖掘出網絡中的關鍵節點,并對其性質進行針對性的分析和利用具有十分重要的意義[2],它有助于提高整個網絡的可靠性與抗毀性[3,4].目前,節點重要性評估的研究多集中在無向或無權網絡上[5?12],然而,現實世界中的網絡多數是有向加權網絡,不僅要考慮節點之間相互作用的強弱[12],還要考慮其方向[5].將節點重要性評估的研究拓展到有向加權網絡,對于推動復雜網絡的發展具有更為重要的實用價值.

國內外學者從不同角度提出了多種有價值的評價方法.“中心性”常用來衡量節點的重要性,常見的指標有度、接近中心性、介數、累計提名等.例如Jeong等[13]利用度指標研究了蛋白質網絡.然而,度相同的節點在網絡中的重要度未必相同.另外,度指標僅利用了節點最局部的鄰居信息,并沒有考慮節點在網絡中的位置,其應用非常有限.Freeman[14]于1977年在研究社會網絡時提出介數指標.但該指標需要計算網絡中任意節點對之間的最短路徑,其算法的時間復雜度較高,對于大規模網絡并不適用.近年來,有學者開始基于信息擴散的視角識別網絡中的關鍵節點.例如Kitsak等[15]提出利用k-核(ks)分解法來挖掘中心節點.該方法認為ks指標越大的節點越重要.然而,在BA網絡和樹形網絡中,所有的節點具有相同的ks值,同層的節點無法比較其重要性.另外,該方法也不能直接運用于有向網絡、加權網絡.Lü等[16]提出了LeaderRank算法,該算法沒有參數,相比經典的PageRank算法[17]更加精準.但是,標準的LeaderRank算法中背景節點和所有節點的連接都一樣,不切合實際且不能直接運用到加權網絡.

目前有向加權網絡節點重要度評估的研究還相對較少.Xu等[18]借鑒PageRank算法,提出一個有向加權網絡節點重要性的評價指標——DWCN-NodeRank.但是,該算法不能同時獲得較高的評估精度和較快的收斂速度.Liu等[5]充分利用網絡的拓撲結構特征和鄰居節點的重要性,提出了一種基于交互信息的節點重要性評價方法,該方法將節點所包含的信息量作為其重要性的衡量指標.節點所包含的信息越多,就越重要,這在一定程度上能區分節點間的差異.但該方法僅考慮了網絡的有向性,而沒有對加權網絡進行討論,王班等[19]對其進行改進,使其適用于有向加權網絡.但是,文獻[5,19]均只考慮了鄰居節點之間的交互信息,而忽略了那些非直接相鄰的節點之間也可能沿著某路徑進行信息交互,不夠全面.周漩等[20]結合節點的效率和度值,提出了節點重要度貢獻矩陣的概念,以此表示節點之間的相互依賴關系,進而判斷節點的重要度.但是,該方法將節點的重要度平均貢獻給鄰居節點,且認為這種重要性依賴關系僅僅存在于鄰居節點之間,與現實不符.實際上,當網絡具有較強的連通性,即所有節點之間的關系比較緊密時,非鄰居節點之間的相互依賴關系就不能被忽略.Hu等[21]以及范文禮和劉志剛[22]分別提出了基于重要度貢獻關聯矩陣和網絡傳輸效率矩陣的節點重要性評價方法.這兩種方法不僅認為鄰居節點之間存在相互作用,而且考慮到非鄰居節點也可通過某種途徑向待評估節點貢獻自身的重要度,克服了重要度貢獻只依賴鄰居節點的不足.但是,傳輸效率矩陣在判斷重要性貢獻比例值時,僅考慮了節點間的最短路徑長度這一因素,顯然不夠全面.事實上,兩節點間的相互影響程度還與二者之間的最短路徑條數相關.

基于以上考慮,本文通過新定義的交叉強度指標,來表征有向加權網絡中節點的局部重要性.為研究節點在全網中的相對重要性,本文不僅同時考慮了最短路徑長度和最短路徑條數兩個影響因素,還分別從影響節點和待評估節點兩個角度構建了另外兩個影響力矩陣,以此來表示全網節點之間的重要性影響關系,進而提出了基于多重影響力矩陣的綜合評價算法.本文結構如下:在第二部分,引入交叉強度指標及其他相關指標.在第三部分,構建三種影響力矩陣,并運用層次分析法求得“多重影響力矩陣”,進而提出評價算法.在第四部分,將評價方法運用于幾個具體的有向加權網絡,并進行仿真實驗分析,以此驗證算法的有效性.在最后一部分,給出本文的總結.

2 理論基礎

有向加權復雜網絡模型G=(V,E,W).其中V={v1,v2,···,vn}為節點集合,E={e1,e2,···,em}為邊集合,(vi,vj)∈E,表示從節點vi到vj的一條有向邊.網絡節點數目為n=|V|,邊數為m=|E|.鄰接矩陣記為An×n=(aij),當且僅當存在一條從節點vi指向vj的有向邊時aij=1,否則aij=0.W表示有向邊的權重矩陣,wij表示有向邊(vi,vj)的權值.有向加權網絡的權重矩陣一般不對稱,即wijwji.

在有向加權網絡中,每個節點的強度可以分為入強度和出強度[23].強度指標將入強度和出強度簡單相加,無法有效區分兩者之間的差異.針對這一問題,本文把有向加權網絡中入強度和出強度的概念相結合,提出節點交叉強度的概念.

定義1交叉強度.為了綜合考慮節點的入強度和出強度,本文將節點vi的交叉強度定義如下:

其中,λ是一常數,它滿足表示節點vi的入強度,表示節點vi的出強度.當λ>0.5時,節點的入強度被認為對節點的重要性影響程度更大;當λ<0.5時,節點的出強度被認為對節點的重要性影響程度更大.常數λ的不同取值會得到不同的節點交叉強度值,從而導致節點重要性評價結果產生一定差異.

由于本文所有算法是在相似權[24]原則下進行的,即連邊的權重越大表示兩點間的距離越小,關系越親密,因此認為節點的入強度更能反映節點的重要性.比如其他用戶轉發某用戶的微博數,相比該用戶轉發其他用戶的微博數更能反映該用戶的重要性;其他作者引用某作者的文章數,相比該作者引用的文章數更能反映該作者的重要性,等等.交叉強度對節點強度進行了拓展,是衡量節點重要性的局部指標.常數λ的引入也使該指標同樣可以度量那些出度非常大但入度為0或入度非常大但出度為0的節點重要性,更自然的用于有向加權網絡.

定義2節點效率[20].節點vi的效率是指從該節點到網絡中其他節點之間距離倒數之和的平均值表示為

其中,dij表示從節點vi到節點vj的距離;1/dij表示從節點vi到節點vj的效率,記作eij.節點效率值可表征從該節點到達網絡中其他節點的平均難易程度.效率值越大,說明該節點越可能處于網絡的中心位置,它在信息傳輸和總發揮的作用越大.

定義3網絡平均效率[25].網絡的平均效率是指網絡中所有節點對之間距離倒數之和的平均值,它用來表示網絡信息流通的平均難易程度:

3 基于多重影響力矩陣的節點重要性評價方法

網絡中的節點并不都是孤立存在的,而是受到其他節點的影響和制約.這種影響關系可以用節點重要性影響矩陣來描述.從信息傳輸路徑的角度,網絡中其他節點對某節點重要性的影響比例值會受到最短路徑長度和最短路徑條數兩個因素的影響[14,26].需要注意的是,節點間的依賴關系不僅存在于鄰居節點之間.當網絡連通性較好,即節點之間具有較強的可達性時,非鄰居節點仍可以通過其有效路徑傳遞自身的重要性,從而影響所指向節點的重要性.這里的有效路徑既可以是最短路徑,也可以是非最短路徑.本文假設節點會優先選擇其最短路徑進行信息傳播,這樣花費的成本最低[26].當然,節點通過非最短路徑對其他節點施加的影響也需考慮在內.基于此,本文建立了三個重要性影響矩陣來表示節點間的這種重要性依賴關系.

3.1 基于效率的影響力矩陣

從空間自相關的角度,兩個對象距離越遠,對彼此的依賴程度越弱.利用空間自相關理論[27],可以認為:在其他條件相同時,網絡中任一節點對待評估節點的影響比例與兩節點之間的距離成反比,距離越大,重要性影響比例就越小.節點間的效率值eij是距離dij的倒數,該指標既表征了節點間相互作用的最直接、有效的形式,又體現了影響比重與距離的衰減關系,即當i=j或從vi到vj不存在路徑時,eij=0;當vi直接指向vj時,其傳輸效率值最大,eij=1;當vi存在非直接到達vj的路徑時,eij∈(0,1).因此,可構建如下效率矩陣E,它能從最短路徑長度的角度反映節點間重要性的影響程度.

3.2 基于最短路徑條數的影響力矩陣

節點間的重要性影響程度除了取決于兩節點間的最短路徑長度,還與連接兩節點的路徑數有關.不妨固定待評估節點vj,考察網絡其他節點對vj的影響程度.假設從節點vi到vj的距離dij等于從節點vk到vj的距離dkj,但從vi到vj長度為dij的路徑數遠多于從vk到vj長度為dkj的路徑數,那么在其他條件完全相同的情況下,vi要比vk更能影響vj的重要性.以朋友網絡為例,假設A和B都能最少通過兩層人物關系聯系到C,但A既可以通過路徑A→D→E→C,又可以通過路徑A→F→G→C聯系到C,而B僅能通過路徑B→D→G→C聯系到C.那么在其他條件完全相同的情況下,人物A對C的影響力就要大于B對C的影響力.同樣地,固定影響節點vi,考察其對網絡其他節點的影響程度,結論亦然.

在無向網絡中,鄰接矩陣具有重要性質[28]:鄰接矩陣的k次冪里的元素值(Ak)ij(k∈Z+)等于對應節點對(vi,vj)之間長度為k的任意路徑數.同樣地,這條性質也可推廣到有向網絡.由于所以(A2)ij表示了從節點vi到節點vj所經歷的長度為2的路徑條數.對于任意正整數k(k>2),由于

所以,(Ak)ij表示了從節點vi到節點vj之間長度為k的路徑總數.本文假設節點優先通過最短路徑向網絡中其他節點傳播自身的重要性,因此可利用該條性質計算從節點vi到節點vj之間的最短路徑數,即長度為dij的路徑總數(Adij)ij.當i=j或從vi到vj不存在路徑時,dij→∞,(Adij)ij=0.

需要特別強調的是,某節點vi(影響節點)對節點vj(待評估節點)的影響程度除了取決于兩節點間的距離大小、最短路徑條數,還取決于其他節點對vj的影響以及vi對其他節點的影響.比如,在其他條件不變時,如果網絡中的其他節點均不對vj產生影響,那么vi對vj的影響程度就會相對變大,反之就會變小;另一方面,在其他條件不變時,如果vi僅對vj產生影響,而不存在指向其他節點的連邊那么vi對vj的影響程度也會相對變大,反之就會變小.因此,可以基于最短路徑條數對這兩種情況進行分析,分別構建以源節點,即影響節點為中心的影響力矩陣SIP(source node-centred inlf uence power matrix)和以目標節點,即待評估節點為中心的影響力矩陣TIP(target node-centred influence power matrix):

對于矩陣SIP,元素為A1,2,···,n),其分子表示從節點vi到節點vj的最短路徑數,即長度為dij的路徑數,分母表示從節點vi到網絡中所有節點長度為dij的路徑數總和,二者的比值是從固定影響節點vi的角度,來分析其對vj的影響比例的;對于矩陣TIP,元素為,其分母表示網絡中的所有節點到節點vj長度為dij的路徑數總和,分子與分母的比值是從固定待評估節點vj的角度,來分析vi對其的影響比例的.由矩陣元素的分母表示還可以看出,這兩個矩陣均考慮到了其他節點對在非自身最短路徑上的信息傳播對所研究節點對之間依賴程度的影響.

圖1 一個簡單的拓撲結構Fig.1.A simple topological structure.

圖1是含有5個節點的簡單拓撲結構,圖2(a)和圖2(b)分別是從某影響節點和待評估節點的角度提取的圖1網絡的部分拓撲結構.以此為例,利用上述3個矩陣,從不同角度比較各重要性影響比例值的大小.由于重要性影響比例是根據信息傳輸的路徑來分析的,所以暫不考慮連邊上的權重值.

圖2 分別從某影響節點和待評估節點的角度提取的圖1網絡的部分拓撲結構 (a)節點v1影響v3,v5的路徑圖;(b)節點v2,v4影響v6的路徑圖Fig.2.Part topology extracted from figure 1 from the perspective of acertain sourcenode and target node:(a)The path graph that v1influences v3and v5;(b)the path graph that v2and v4influence v6.

根據(4)—(6)式得:

效率矩陣主要用于兩節點間距離不相等時的影響比例比較,而矩陣SIP和TIP分別是從影響節點和待評估節點的角度,用于兩節點間距離相等時的影響比例的比較.一般來講,當比較重要性影響比例大小時,首先要考慮的就是節點間的距離,然后再考慮距離相同時,SIP和TIP中元素的大小.

從節點間的效率角度,由于d13=2e16,所以節點v1對v3的影響比例要大于v1對v6的影響比例.

從SIP的角度,比較同行元素.以v1對v3,v5的影響為例,圖2(a)給出v1影響v3,v5的路徑圖.雖然e13=e15=0.5,但是由于v1到v3的最短路徑數2大于v1到v5的最短路徑數1,導致SIP13=0.67>SIP15=0.33.因此單從影響節點的角度,節點v1對v3的影響比例要大于v1對v5的影響比例.當然實際的影響比例還與v3,v5各自對應的TIP有關.

從TIP的角度,比較同列元素.以v2,v4對v6的影響為例,圖2(b)給出v2,v4影響v6的路徑圖.雖然e26=e46=0.5,但是由于v4到v6的最短路徑數2大于v2到v6的最短路徑數1,導致TIP46=0.67>TIP26=0.33.因此單從待評估節點的角度,節點v4對v6的影響比例要大于v2對v6的影響比例.當然實際的影響比例還與v2,v4各自對應的SIP有關.

3.3 構建多重影響力矩陣

由以上分析可知,節點之間的影響程度同時受到節點間的距離、最短路徑數以及影響節點對網絡中所有節點的影響比例、網絡中所有節點對待評估節點的影響比例的多重制約.因此,要想全面反映節點間的影響比例大小,就需要對矩陣E、矩陣SIP和TIP進行賦權加總,構建多重影響力矩陣.各矩陣權重的計算使用改進的層次分析法[29]得出,步驟如下:

第一步,采用(0,1,2)三標度法對每一個矩陣進行兩兩比較,建立比較矩陣;

第二步,利用極差法將比較矩陣轉化為判斷矩陣,并進行一致性檢驗,最后得到矩陣權重.具體的計算方法參見文獻[29].表1列出了按照(7)式三標度法構造的比較矩陣B中的元素值.

表1 (0,1,2)三標度法構建各矩陣重要性的比較值Table 1.Importance comparison of matrix with(0,1,2)three-demarcation method.

表1中的比較矩陣

比較矩陣B的構建是基于以下考慮:效率矩陣E通過距離直接體現了節點間的親疏關系,而且在比較節點間的影響比例值大小時,首先要考慮的是兩節點之間的距離,然后再去考慮當距離相同時,最短路徑數對比例值的影響.因此可認為效率矩陣E比其他兩個矩陣更加重要;而矩陣SIP和TIP都是基于最短路徑數來研究節點間的相互影響的,區別僅在于側重點不同,SIP考慮到影響節點對網絡中所有待評估節點的影響,TIP考慮到網絡中所有影響節點對待評估節點的影響,這兩種情況都需要考慮在內,無法比較其好壞,因此認為這兩個矩陣具有同等的重要性.

經一致性檢驗,得到各矩陣的權重值分別為wE=0.82,wSIP=0.09,wTIP=0.09.對各矩陣加權求和,便得多重影響力矩陣M:

M中的元素mij表示考慮各因素后,節點vi對vj的綜合影響比例值.由于節點效率值能體現該節點對于整個拓撲網絡信息傳輸的貢獻,因此,選取節點效率作為其對整個網絡節點重要性影響的初始值.那么每個節點對網絡中其余節點的依賴程度值便可用矩陣P表示:

矩陣P是多重影響力矩陣M的第i行中的數都乘以Ii得來的,其中pij=Iimij表示節點vi對vj的重要性綜合影響值.在考慮全網節點對待評估節點重要性影響值的基礎上,結合待評估節點自身的局部重要性(交叉強度值),可以定義節點vi的重要度Di:

歸一化后,節點vi的重要度為

3.4 算法流程

本文算法充分考慮了節點的局部重要性和其受網絡其他節點的依賴程度.已知網絡的鄰接矩陣A和權重矩陣W,其具體的算法步驟如下:

第一步,計算所有節點對之間的最短距離Dis=[dij]//有向網絡的Floyd算法;

第三步,根據定義2,計算出每個節點的效率值Ii(i=1,···,n)和所有節點對之間的效率值eij(i,j=1,···,n),填入效率矩陣E;

第四步,根據各節點對之間的距離dij,計算所有涉及的矩陣Adij,并按式和將各比例值分別填入矩陣SIP和TIP中;

第五步,按照(8)式,確定多重影響矩陣M;將矩陣M的第i行中的數都乘以Ii,確定矩陣P;

第六步,根據(10)式和(11)式,計算每個節點的重要度

第七步,將所有節點按照重要性值從大到小進行排序.

考慮到有些節點僅存在出邊,而不存在入邊,比如微博網絡中的“僵尸用戶”,引文網絡中的從未被引用的文章等,這時它們的重要度指標都為0.為了增強此類節點的可比性,本文對此類節點的處理如下:當兩個節點的D′i值均為0時,比較二者的交叉強度值,值越大的節點,排序越靠前,節點越重要.

4 實證分析

4.1 算法有效性分析

首先以圖3所示的具有對稱結構的有向加權網絡[19]為例,運用本文所提算法計算每個節點的交叉強度以及最終的重要性指標并與文獻[19]中的交互信息評價方法進行對比分析.注意,文獻[19]是對文獻[5]的改進,使其評價方法能適用于有向加權網絡(不妨令λ=0.8).

計算得到各節點的重要性指標值和排序結果,列于表2.

本文算法可以得出重要性的排序:v4和v7最重要,排在首位;v3和v8同等重要,僅次于v4,v7;v1和v9同等重要,次于v3,v8;v2和v10最不重要,排在末位.合理的解釋為:從圖3可以看出,節點v4和v7處于全局信息控制能力最大的位置,相當于兩個“橋節點”,如果兩個節點被刪除,會直接導致網絡不再連通,因此v4和v7的重要性最大;同樣地,v3和v8的刪除也會導致網絡不連通,但相對于v4和v7,與v3和v8相關聯的節點要少一些,因此重要性次之;v5和v6相互連接,但并沒有起到“橋梁”的作用,因此重要性稍差;節點v1,v9和v2,v10在網絡中的位置相同,都處于網絡的邊緣且都沒有入邊,但相對于v1,v9,節點v2,v10的出強度更小一些,因此排序就更為靠后.另外,從表2還可以看出,本文算法可以得出與文獻[19]完全一致的前4個重要節點,再次說明了本文算法的有效性.

但是,本文算法與文獻[19]在評價節點重要性上還是存在一定差異的,比如文獻[19]認為節點v1,v9和v2,v10的重要性都要優先于v5和v6.為此表3給出了刪除相應節點后網絡的平均效率值的變化.由表3不難看出,刪除節點v5后,網絡的平均效率有所下降,這說明節點v5的刪除在一定程度上減弱了網絡的信息流通;而刪除節點v1后,網絡的平均效率反而上升,這說明節點v1的刪除使得網絡的通訊冗余度減少,反而提高了整個網絡的通信能力.那么可以認為,節點v5和v6的重要性要大于v1,v9和v2,v10.因此,本文方法在評價節點重要性上相對更加準確.

表2 圖3所示網絡的節點重要性排序結果Table 2.Importance ranking results of network nodes shown in Fig.3.

表3 刪除相應節點前后圖3網絡的平均效率值Table 3.The average efficiency of network shown infigure 3 before and after removing node.

圖3 具有對稱結構的有向加權網絡拓撲Fig.3.A directed weighted network topology with symmetric structure.

從對圖3網絡的實驗可以看出,本文算法對簡單的有向加權網絡進行節點重要性評估可以取得良好的結果.為了進一步驗證本文方法的有效性,本文利用了美國的ARPA(advanced research project agency)網絡拓撲進行研究.ARPA拓撲屬于無向無權網絡,為此,本文先對其進行邊賦權[30]得到無向加權網絡,在此基礎上再進行邊定向[19]得到有向加權網絡,如圖4所示.其中邊的定向原則是:首先計算加權網絡中每個節點的強度,然后比較邊(vi,vj)的兩個端點vi與vj的強度大小.當Si

表4給出了本文所提算法以及文獻[19,21,22]所述方法確定的節點重要性排序結果 (不妨令λ=0.8).

表4 加權定向后的ARPA網絡節點重要性排序結果Table 4.Importance ranking results of nodes in directed weighted ARPA network.

圖4 加權定向后的ARPA網絡Fig.4.Directed weighted network obtained by the ARPA network.

首先從表4可以看出,本文的評價算法可以避免單純地利用交叉強度指標的不足,考慮到全局因素的重要性指標能更好地區分節點之間的差異.比如,節點以此認為它們具有相同的重要性是太過片面的.考慮到節點在全網中的相對重要性pi值(p7=0.1817,p11=0.1984,p20=0.1194),可見v20在整個網絡中的相對重要性明顯小于v7和v11,因此D′i指標得到v20的重要性明顯小于v7和v11.

另外,從表4的節點標注還可以看出,本文算法確定的前5個重要節點為v2,v14,v3,v19,v6,同時它們也屬于文獻[19,21,22]確定的前5個重要節點集的并集里,這符合網絡的中心性評估,反映了本文算法的有效性.然而,文獻[19]排在第5位的重要節點v9在本文算法和文獻[22]中卻排在末位,在文獻[21]中也排在倒數第二位.從圖4可以直觀看出,節點v9所處的位置及連邊上的權重值均不占優勢,其重要性相對較小.另外,文獻[19]認為節點v8,v10,v11具有相同的重要性,而本文算法能將v11與v8,v10的重要性區別開來.經計算,刪除節點v8后,網絡的平均效率僅下降了0.5%,而刪除節點v11后,網絡的平均效率下降了4%.可以得出v11的重要性要大于v8,這與本文的評價結果相一致.因此,本文評價方法相對文獻[19]更能細致地區分節點之間的差異.

由于節點的移除會降低網絡的連通性,造成的連通性越差,則對應的評價方法越好.因此,本文基于表4的評價結果,通過連續移除前5個重要節點,來對比本文與另外兩種評價方法的準確性.網絡的連通性可采用移除節點后的子圖數目和最大子圖規模兩個指標來衡量,子圖數目越多,或最大子圖所包含的節點數目越少,則說明網絡連通性越差,對應的評價方法就越準確.實驗結果如圖5所示.

由圖5可以看出,在移除前5個重要節點后,文獻[21]和文獻[22]的評價方法均導致了6個子圖,其中最大子圖的節點數目均為10.而利用本文算法能夠導致7個子圖,其中最大子圖的節點數目為7.此結果表明,無論是從子圖數目,還是從最大子圖規模的衡量上,本文算法的表現都要優于其他方法.因此,它在節點重要性評價上能取得良好的效果.

圖5 (網刊彩色)移除前5個重要節點后ARPA網絡連通性的變化Fig.5.(color online)The connectivity changes by removing the top 5 important nodes on the ARPA.

4.2 算法在連鎖故障中的進一步驗證

為了驗證算法的可靠性,本文對ARPA網絡進行連鎖故障仿真來分析網絡的魯棒性.這里魯棒性可采用兩個指標來衡量.一個是故障后的子圖數目S,另一個是連鎖故障前后,網絡最大連通子圖的規模之比G,其表達式為

其中,nmax表示網絡發生故障后最大連通子圖的節點數目.連鎖故障的過程如下:按照各方法得到的節點重要性先后順序,依次移除網絡中的重要節點.由于節點的移除影響著網絡的魯棒性[21],因此可以根據不同移除方式下的網絡魯棒性分析,來判斷各評價方法的可靠性.G越小,S越大,說明網絡魯棒性越差,對應的評價方法就越可靠.本文及文獻[21,22]對應的連鎖故障仿真結果如圖6所示.

圖6 不同評價方法的連鎖故障結果 (a)移除節點對指標G的影響;(b)移除節點對指標S的影響Fig.6.The results of cascading failures with different evaluation methods:(a)The effect of node removal on G;(b)the effect of node removal on S.

從G的變化趨勢可以看出,在整體水平上,隨著移除節點數目的增加,本文算法能造成G更大幅度的下降.雖然在刪除第2個節點時,表現暫時落后,在刪除前4個節點時,三種算法的表現持平,但是在后續刪除節點的過程中,本文算法對應的G值都要小于文獻[21,22].特別地,當連續移除前5個節點后,本文算法對應的最大連通子圖的規模比文獻[21,22]減少30%.此外,由S的變化趨勢容易看出,本文算法對應的子圖數目S上升較快,數值大小相對其他方法一直領先.由以上實驗結果可以得出,本文所提出的節點重要性評價方法相對更加可靠.

5 結 論

本文通過分析節點的局部重要性以及網絡中所有節點之間的依賴關系,提出了一種基于多重影響力矩陣的節點重要性評價方法.將該方法應用于幾個典型的有向加權網絡,得出以下結論.

相比其他方法,本文方法對ARPA網絡節點重要性的區分更加細致.通過移除個別節點,本文方法得到的重要節點能造成網絡平均效率更大程度的下降;通過連續移除前5個重要節點,計算網絡連通性的變化,發現本文方法能造成更多的子圖數目,以及更小的最大子圖規模,這說明該方法具有一定的可靠性,其得到的重要節點能顯著影響網絡的連通性.進一步地,對網絡進行連鎖故障的仿真實驗,結果表明該方法能造成G更大幅度的下降,對應的S值相對更大且上升更快,這再次驗證了方法的適用性和可靠性.

部分入度為0的節點,其評價結果為0.對此本文是用交叉強度值對該類節點加以輔助區分的,如何針對該類節點設計出更準確的評價指標將是下一步的研究工作.

[1]Barabási A L,Bonabeau E 2003Sci.Am.288 50

[2]Lü L Y,Chen D B,Ren X L,Zhang Q M,Zhang Y C,Zhou T 2016Phys.Rep.650 1

[3]Batool K,Niazi M A 2014PLoS One9 e90283

[4]Zhang Y L,Yang N D,Lall U 2016J.Syst.Sci.Syst.Eng.25 102

[5]Liu Y H,Jin J Z,Zhang Y,Xu C 2014J.Supercomput.67 723

[6]Han Z M,Wu Y,Tan X S,Duan D G,Yang W J 2015Acta Phys.Sin.64 058902(in Chinese)[韓忠明,吳楊,譚旭升,段大高,楊偉杰2015物理學報64 058902]

[7]Li S M,Xu X H 2015Chinese J.Aeronaut.28 780

[8]Fan W L,Hu P,Liu Z G 2016IET Gener.Transm.Distrib.10 2027

[9]Liu R R,Jia C X,Zhang J L,Wang B H 2012J.Univ.Shanghai Sci.Technol.34 235(in Chinese)[劉潤然, 賈春曉,章劍林,汪秉宏2012上海理工大學學報34 235]

[10]Yu H,Liu Z,Li Y J 2013Acta Phys.Sin.62 020204(in Chinese)[于會,劉尊,李勇軍 2013物理學報 62 020204]

[11]Han Z M,Chen Y,Li M Q,Liu W,Yang W J 2016Acta Phys.Sin.65 168901(in Chinese)[韓忠明,陳炎,李夢琪,劉雯,楊偉杰2016物理學報65 168901]

[12]Li J R,Yu L,Zhao J 2014J.UESTC.43 322(in Chinese)[李靜茹,喻莉,趙佳 2014電子科技大學學報 43 322]

[13]Jeong H,Mason S,Barabási A L 2001Nature411 41

[14]Freeman L 1977Sociometry40 35

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

[16]Lü L Y,Zhang Y C,Yeung C H,Zhou T 2011PLoS One6 e21202

[17]Brin S,Page L 1998Comput.Net.ISDN Syst.30 107

[18]Xu J,Li J X,Xu S 2012J.Zhejiang Univ.:Sci.C13 118

[19]Wang B,Ma R N,Wang G,Chen B 2015J.Comput.Appl.35 1820(in Chinese)[王班,馬潤年,王剛,陳波2015計算機應用35 1820]

[20]Zhou X,Zhang F M,Li K W,Hui X B,Wu H S 2012Acta Phys.Sin.61 050201(in Chinese)[周漩,張鳳鳴,李克武,惠曉濱,吳虎勝2012物理學報61 050201]

[21]Hu P,Fan W L,Mei S W 2015Physica A:Stat.Mech.Appl.429 169

[22]Fan W L,Liu Z G 2014J.Southwest Jiaotong Univ.49 337(in Chinese)[范文禮,劉志剛2014西南交通大學學報49 337]

[23]Kudelka M,Zehnalova S,Horak Z,Kromer P,Snasel V 2015Int.J.Appl.Math.Comput.Sci.25 281

[24]Thomas J B,Brier M R,Ortega M,Benzinger T L,Ances B M 2015Neurobiol.Aging36 401

[25]Latora V,Marchiori M 2007New J.Phys.9 188

[26]Shao F,Cheng B 2014Int.J.Comput.Commun.Cont.9 602

[27]Griffith D A,Chun Y 2015Netw.Spat.Econ.15 337

[28]Cai Q S,Liu Y,Niu J W,Sun L M 2015Acta Electron.Sinica.43 1705(in Chinese)[蔡青松,劉燕,牛建偉,孫利民2015電子學報43 1705]

[29]Zhu Y,Meng Z Y,Kan S Y 1999J.Northern Jiaotong Univ.23 119(in Chinese)[朱茵,孟志勇,闞叔愚 1999北方交通大學學報23 119]

[30]Sun S L,Lin J Y,Xie L H,Xiao W D 2007 22nd IEEE International Symposium on Intelligent ControlSingapore,October 1–3,2007 p7

PACS:02.10.Ox,89.75.Hc,89.75.Fb DOI:10.7498/aps.66.050201

Evaluation method of node importance in directed-weighted complex network based on multiple influence matrix?

Wang Yu Guo Jin-Li?
(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

15 October 2016;revised manuscript

23 November 2016)

In complex networks,the node importance evaluation is of great significance for studying the robustness of network.The existing methods of evaluating the node importance mainly focus on undirected and unweighted networks,which fail to reflect the real scenarios comprehensively and objectively.In this paper,according to the directed and weighted complex network model,by analyzing the local importance of the nodes and the dependencies among all the nodes in the whole network,a new method of evaluating the node importance based on a multiple influence matrix is proposed.Firstly,the method defines the concept of cross strength to characterize the local importance of the nodes.The index not only distinguishes between the in-strength and out-strength of the nodes,but also helps to discriminate the differences in importance among each with an in-degree of 0.In addition,to characterize the global importance of the nodes to be evaluated,we use the total important influence value of all the nodes exerted on the nodes,which makes up the deficiencies of the other evaluation methods which just depend on adjacent nodes.Emphatically,in the analysis of the influence ratio of source node on node to be evaluated,we not only take into account the distance factor between nodes,but also introduce the number of the shortest path factors.In order to make the evaluation algorithm more accurate,according to the number of the shortest paths,we present two perspectives to analyze how other factors affect the influence ratio.One is to evaluate how this source node exerts important influence on the other nodes to be evaluated.The other is to analyze how the other source nodes perform important influence on this node to be evaluated.In view of the above factors,three influence matrices are constructed,including the efficiency matrix,and the other two influence matrices from the perspectives of fixing source nodes and target nodes,respectively.Then,we use analytic hierarchy process to weight the three matrices,thereby obtaining the multiple influence matrix,which makes the global importance evaluation more comprehensive.Finally,the method is applied to typical directed weighted networks.It is found that compared with other methods,our method can effectively distinguish between nodes.Furthermore,we carry out simulation experiments of cascading failure on each method.The simulation results further verify the effectiveness of the proposed method.

directed-weighted complex network,node importance,multiple influence matrix,the number of shortest path

PACS:02.10.Ox,89.75.Hc,89.75.Fb

10.7498/aps.66.050201

?國家自然科學基金(批準號:71571119)資助的課題.

?通信作者.E-mail:phd5816@163.com

*Project Supported by the National Natural Science Foundation of China(Grant No.71571119).

?Corresponding author.E-mail:phd5816@163.com