基于多重影響力矩陣的有向加權(quán)網(wǎng)絡(luò)節(jié)點重要性評估方法?

王雨 郭進利

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

基于多重影響力矩陣的有向加權(quán)網(wǎng)絡(luò)節(jié)點重要性評估方法?

王雨 郭進利?

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

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

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

有向加權(quán)網(wǎng)絡(luò),節(jié)點重要性,多重影響力矩陣,最短路徑條數(shù)

1 引 言

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

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

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

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

2 理論基礎(chǔ)

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

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

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

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

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

定義2節(jié)點效率[20].節(jié)點vi的效率是指從該節(jié)點到網(wǎng)絡(luò)中其他節(jié)點之間距離倒數(shù)之和的平均值表示為

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

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

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

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

3.1 基于效率的影響力矩陣

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

3.2 基于最短路徑條數(shù)的影響力矩陣

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

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

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

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

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

圖1 一個簡單的拓撲結(jié)構(gòu)Fig.1.A simple topological structure.

圖1是含有5個節(jié)點的簡單拓撲結(jié)構(gòu),圖2(a)和圖2(b)分別是從某影響節(jié)點和待評估節(jié)點的角度提取的圖1網(wǎng)絡(luò)的部分拓撲結(jié)構(gòu).以此為例,利用上述3個矩陣,從不同角度比較各重要性影響比例值的大小.由于重要性影響比例是根據(jù)信息傳輸?shù)穆窂絹矸治龅?所以暫不考慮連邊上的權(quán)重值.

圖2 分別從某影響節(jié)點和待評估節(jié)點的角度提取的圖1網(wǎng)絡(luò)的部分拓撲結(jié)構(gòu) (a)節(jié)點v1影響v3,v5的路徑圖;(b)節(jié)點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.

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

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

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

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

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

3.3 構(gòu)建多重影響力矩陣

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

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

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

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

表1中的比較矩陣

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

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

M中的元素mij表示考慮各因素后,節(jié)點vi對vj的綜合影響比例值.由于節(jié)點效率值能體現(xiàn)該節(jié)點對于整個拓撲網(wǎng)絡(luò)信息傳輸?shù)呢暙I,因此,選取節(jié)點效率作為其對整個網(wǎng)絡(luò)節(jié)點重要性影響的初始值.那么每個節(jié)點對網(wǎng)絡(luò)中其余節(jié)點的依賴程度值便可用矩陣P表示:

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

歸一化后,節(jié)點vi的重要度為

3.4 算法流程

本文算法充分考慮了節(jié)點的局部重要性和其受網(wǎng)絡(luò)其他節(jié)點的依賴程度.已知網(wǎng)絡(luò)的鄰接矩陣A和權(quán)重矩陣W,其具體的算法步驟如下:

第一步,計算所有節(jié)點對之間的最短距離Dis=[dij]//有向網(wǎng)絡(luò)的Floyd算法;

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

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

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

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

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

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

4 實證分析

4.1 算法有效性分析

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

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

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

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

表2 圖3所示網(wǎng)絡(luò)的節(jié)點重要性排序結(jié)果Table 2.Importance ranking results of network nodes shown in Fig.3.

表3 刪除相應(yīng)節(jié)點前后圖3網(wǎng)絡(luò)的平均效率值Table 3.The average efficiency of network shown infigure 3 before and after removing node.

圖3 具有對稱結(jié)構(gòu)的有向加權(quán)網(wǎng)絡(luò)拓撲Fig.3.A directed weighted network topology with symmetric structure.

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

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

表4 加權(quán)定向后的ARPA網(wǎng)絡(luò)節(jié)點重要性排序結(jié)果Table 4.Importance ranking results of nodes in directed weighted ARPA network.

圖4 加權(quán)定向后的ARPA網(wǎng)絡(luò)Fig.4.Directed weighted network obtained by the ARPA network.

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

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

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

由圖5可以看出,在移除前5個重要節(jié)點后,文獻[21]和文獻[22]的評價方法均導(dǎo)致了6個子圖,其中最大子圖的節(jié)點數(shù)目均為10.而利用本文算法能夠?qū)е?個子圖,其中最大子圖的節(jié)點數(shù)目為7.此結(jié)果表明,無論是從子圖數(shù)目,還是從最大子圖規(guī)模的衡量上,本文算法的表現(xiàn)都要優(yōu)于其他方法.因此,它在節(jié)點重要性評價上能取得良好的效果.

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

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

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

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

圖6 不同評價方法的連鎖故障結(jié)果 (a)移除節(jié)點對指標G的影響;(b)移除節(jié)點對指標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的變化趨勢可以看出,在整體水平上,隨著移除節(jié)點數(shù)目的增加,本文算法能造成G更大幅度的下降.雖然在刪除第2個節(jié)點時,表現(xiàn)暫時落后,在刪除前4個節(jié)點時,三種算法的表現(xiàn)持平,但是在后續(xù)刪除節(jié)點的過程中,本文算法對應(yīng)的G值都要小于文獻[21,22].特別地,當(dāng)連續(xù)移除前5個節(jié)點后,本文算法對應(yīng)的最大連通子圖的規(guī)模比文獻[21,22]減少30%.此外,由S的變化趨勢容易看出,本文算法對應(yīng)的子圖數(shù)目S上升較快,數(shù)值大小相對其他方法一直領(lǐng)先.由以上實驗結(jié)果可以得出,本文所提出的節(jié)點重要性評價方法相對更加可靠.

5 結(jié) 論

本文通過分析節(jié)點的局部重要性以及網(wǎng)絡(luò)中所有節(jié)點之間的依賴關(guān)系,提出了一種基于多重影響力矩陣的節(jié)點重要性評價方法.將該方法應(yīng)用于幾個典型的有向加權(quán)網(wǎng)絡(luò),得出以下結(jié)論.

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

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

[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物理學(xué)報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上海理工大學(xué)學(xué)報34 235]

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

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

[12]Li J R,Yu L,Zhao J 2014J.UESTC.43 322(in Chinese)[李靜茹,喻莉,趙佳 2014電子科技大學(xué)學(xué)報 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計算機應(yīng)用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物理學(xué)報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西南交通大學(xué)學(xué)報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電子學(xué)報43 1705]

[29]Zhu Y,Meng Z Y,Kan S Y 1999J.Northern Jiaotong Univ.23 119(in Chinese)[朱茵,孟志勇,闞叔愚 1999北方交通大學(xué)學(xué)報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

?國家自然科學(xué)基金(批準號: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