王雨 郭進(jìn)利

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

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

王雨 郭進(jìn)利?

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

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

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

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

1 引 言

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

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

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

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

2 理論基礎(chǔ)

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

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

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

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

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

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

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

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

3 基于多重影響力矩陣的節(jié)點(diǎn)重要性評(píng)價(jià)方法

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

3.1 基于效率的影響力矩陣

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

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

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

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

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

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

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

圖1 一個(gè)簡(jiǎn)單的拓?fù)浣Y(jié)構(gòu)Fig.1.A simple topological structure.

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

圖2 分別從某影響節(jié)點(diǎn)和待評(píng)估節(jié)點(diǎn)的角度提取的圖1網(wǎng)絡(luò)的部分拓?fù)浣Y(jié)構(gòu) (a)節(jié)點(diǎn)v1影響v3,v5的路徑圖;(b)節(jié)點(diǎn)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é)點(diǎn)間距離不相等時(shí)的影響比例比較,而矩陣SIP和TIP分別是從影響節(jié)點(diǎn)和待評(píng)估節(jié)點(diǎn)的角度,用于兩節(jié)點(diǎn)間距離相等時(shí)的影響比例的比較.一般來(lái)講,當(dāng)比較重要性影響比例大小時(shí),首先要考慮的就是節(jié)點(diǎn)間的距離,然后再考慮距離相同時(shí),SIP和TIP中元素的大小.

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

從SIP的角度,比較同行元素.以v1對(duì)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é)點(diǎn)的角度,節(jié)點(diǎn)v1對(duì)v3的影響比例要大于v1對(duì)v5的影響比例.當(dāng)然實(shí)際的影響比例還與v3,v5各自對(duì)應(yīng)的TIP有關(guān).

從TIP的角度,比較同列元素.以v2,v4對(duì)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.因此單從待評(píng)估節(jié)點(diǎn)的角度,節(jié)點(diǎn)v4對(duì)v6的影響比例要大于v2對(duì)v6的影響比例.當(dāng)然實(shí)際的影響比例還與v2,v4各自對(duì)應(yīng)的SIP有關(guān).

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

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

第一步,采用(0,1,2)三標(biāo)度法對(duì)每一個(gè)矩陣進(jìn)行兩兩比較,建立比較矩陣;

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

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

表1中的比較矩陣

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

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

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

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

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

3.4 算法流程

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

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

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

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

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

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

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

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

4 實(shí)證分析

4.1 算法有效性分析

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

計(jì)算得到各節(jié)點(diǎn)的重要性指標(biāo)值和排序結(jié)果,列于表2.

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

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

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

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

圖3 具有對(duì)稱(chēng)結(jié)構(gòu)的有向加權(quán)網(wǎng)絡(luò)拓?fù)銯ig.3.A directed weighted network topology with symmetric structure.

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

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

表4 加權(quán)定向后的ARPA網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序結(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可以看出,本文的評(píng)價(jià)算法可以避免單純地利用交叉強(qiáng)度指標(biāo)的不足,考慮到全局因素的重要性指標(biāo)能更好地區(qū)分節(jié)點(diǎn)之間的差異.比如,節(jié)點(diǎn)以此認(rèn)為它們具有相同的重要性是太過(guò)片面的.考慮到節(jié)點(diǎn)在全網(wǎng)中的相對(duì)重要性pi值(p7=0.1817,p11=0.1984,p20=0.1194),可見(jiàn)v20在整個(gè)網(wǎng)絡(luò)中的相對(duì)重要性明顯小于v7和v11,因此D′i指標(biāo)得到v20的重要性明顯小于v7和v11.

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

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

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

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

4.2 算法在連鎖故障中的進(jìn)一步驗(yàn)證

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

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

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

5 結(jié) 論

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

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

部分入度為0的節(jié)點(diǎn),其評(píng)價(jià)結(jié)果為0.對(duì)此本文是用交叉強(qiáng)度值對(duì)該類(lèi)節(jié)點(diǎn)加以輔助區(qū)分的,如何針對(duì)該類(lèi)節(jié)點(diǎn)設(shè)計(jì)出更準(zhǔn)確的評(píng)價(jià)指標(biāo)將是下一步的研究工作.

[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é)報(bào)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)[劉潤(rùn)然, 賈春曉,章劍林,汪秉宏2012上海理工大學(xué)學(xué)報(bào)34 235]

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

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

[12]Li J R,Yu L,Zhao J 2014J.UESTC.43 322(in Chinese)[李靜茹,喻莉,趙佳 2014電子科技大學(xué)學(xué)報(bào) 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)[王班,馬潤(rùn)年,王剛,陳波2015計(jì)算機(jī)應(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é)報(bào)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é)報(bào)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é)報(bào)43 1705]

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

?國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào):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