單海燕

（南京信息工程大學(xué)經(jīng)濟(jì)管理學(xué)院，南京 210044）

面向有向賦權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)重要性度量方法研究

單海燕

（南京信息工程大學(xué)經(jīng)濟(jì)管理學(xué)院，南京 210044）

眾多現(xiàn)實(shí)問題可以建模為有向賦權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的度量問題。文章從節(jié)點(diǎn)不同連接方式的角度出發(fā)，區(qū)分網(wǎng)絡(luò)中節(jié)點(diǎn)的直接連接、橋梁連接以及間接連接方式對(duì)有向賦權(quán)網(wǎng)絡(luò)的損失，提出了面向有向賦權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)相對(duì)重要性的度量方法；通過對(duì)比節(jié)點(diǎn)重要性不同度量方法，說明該方法能更細(xì)致地凸顯節(jié)點(diǎn)之間的差異性，并比較客觀地反映節(jié)點(diǎn)的物理屬性以及節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)位置對(duì)有向賦權(quán)網(wǎng)絡(luò)整體的影響作用。

有向賦權(quán)網(wǎng)絡(luò)；相對(duì)重要性；直接損失；間接橋梁損失；間接連接損失

0 引言

通訊網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、供應(yīng)鏈網(wǎng)絡(luò)、知識(shí)網(wǎng)絡(luò)等許多現(xiàn)實(shí)系統(tǒng)中存在多種復(fù)雜關(guān)系，如合作關(guān)系、運(yùn)輸關(guān)系、生產(chǎn)關(guān)系、社會(huì)關(guān)系等[1～3]。網(wǎng)絡(luò)中哪些個(gè)體對(duì)網(wǎng)絡(luò)的連通性及各種關(guān)系的建立會(huì)起到至關(guān)重要的作用？通訊網(wǎng)絡(luò)中如何選擇最有效的節(jié)點(diǎn)作為傳播源點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行信息傳播？城市交通網(wǎng)絡(luò)中哪些路口發(fā)生擁堵會(huì)造成交通系統(tǒng)癱瘓？知識(shí)網(wǎng)絡(luò)中哪些個(gè)體的流失將給組織帶來重大損失？這些問題都可歸結(jié)為個(gè)體/節(jié)點(diǎn)在系統(tǒng)/網(wǎng)絡(luò)中的重要性問題，均是現(xiàn)實(shí)中亟待解決的問題。

本文將針對(duì)有向賦權(quán)網(wǎng)絡(luò)，賦予節(jié)點(diǎn)一定的物理屬性及勢(shì)，從節(jié)點(diǎn)不同連接方式的角度出發(fā)，區(qū)分網(wǎng)絡(luò)中節(jié)點(diǎn)的直接連接、橋梁連接以及間接連接方式對(duì)有向賦權(quán)網(wǎng)絡(luò)的不同損失，提出有向賦權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的測(cè)度方法，并通過實(shí)例說明該方法能更有效地評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。

1 節(jié)點(diǎn)重要性的度量模型

1.1 基本定義

有向賦權(quán)網(wǎng)絡(luò)可以通過圖G=(N,E,W)表示，其中N={1,2,…,n}表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，E={e1,e2,…,em}表示網(wǎng)絡(luò)中所有邊的集合，W={wi1i2,wi1i3,…,win-1in}表示網(wǎng)絡(luò)中所有邊上權(quán)重（關(guān)系強(qiáng)度）的集合。

可采用社會(huì)網(wǎng)絡(luò)中的鄰接矩陣表示有向賦權(quán)網(wǎng)絡(luò)結(jié)構(gòu)，鄰接矩陣中的行和列表示網(wǎng)絡(luò)中的各節(jié)點(diǎn)，并且行和列排列的順序都相同，矩陣中行位置的行動(dòng)者通常是某種特定關(guān)系的發(fā)送者，列位置的行動(dòng)者通常是某種特定關(guān)系的接收者；矩陣中的元素，代表行動(dòng)者之間是否存在某種關(guān)系，這樣的矩陣X記作

1.2 節(jié)點(diǎn)重要性的度量方法

1.2.1 直接損失

在有向賦權(quán)網(wǎng)絡(luò)中刪除某節(jié)點(diǎn)后，將給網(wǎng)絡(luò)中可直接獲得該節(jié)點(diǎn)相關(guān)資源或信息的這些節(jié)點(diǎn)產(chǎn)生最直接影響。假設(shè)節(jié)點(diǎn)j可直接獲得節(jié)點(diǎn)i的相關(guān)資源或信息，即xji=1。如果相對(duì)節(jié)點(diǎn)j，節(jié)點(diǎn)i在某類度量指標(biāo)上的勢(shì)較大且節(jié)點(diǎn)j與節(jié)點(diǎn)i建立的關(guān)系強(qiáng)度較強(qiáng)，那么刪除節(jié)點(diǎn)i后節(jié)點(diǎn)j的損失較多，反之亦然。因?yàn)?，若相?duì)節(jié)點(diǎn)j，節(jié)點(diǎn)i在某類度量指標(biāo)上的勢(shì)較大，說明節(jié)點(diǎn)i有更多的資源或信息值得節(jié)點(diǎn)j去學(xué)習(xí)或獲??；關(guān)系強(qiáng)度越強(qiáng)，說明節(jié)點(diǎn)j越容易獲得或接收到節(jié)點(diǎn)i的相關(guān)資源或信息。因此，刪除節(jié)點(diǎn)i后有向賦權(quán)網(wǎng)絡(luò)的直接損失可定義為定義1刪除節(jié)點(diǎn)i后有向賦權(quán)網(wǎng)絡(luò)的直接損失NLD(i)可表示為

1.2.2 間接橋梁損失

在有向賦權(quán)網(wǎng)絡(luò)中刪除節(jié)點(diǎn)i后，也可能給網(wǎng)絡(luò)中未直接與節(jié)點(diǎn)i建立連接的一些節(jié)點(diǎn)產(chǎn)生影響。例如，在有向賦權(quán)網(wǎng)絡(luò)中，若節(jié)點(diǎn)j經(jīng)過節(jié)點(diǎn)i獲得節(jié)點(diǎn)k的相關(guān)資源或信息，那么，刪除節(jié)點(diǎn)i后，將給節(jié)點(diǎn)j獲得節(jié)點(diǎn)k的相關(guān)資源或信息產(chǎn)生不便，可能需經(jīng)過更長(zhǎng)的路徑，甚至無法到達(dá)節(jié)點(diǎn)k。這里將這類間接損失定義為間接橋梁損失。

假設(shè)d(i,j,k)表示在可經(jīng)過節(jié)點(diǎn)i的情況下，節(jié)點(diǎn)j到節(jié)點(diǎn)k的最短路徑長(zhǎng)度，不妨將這條最短路徑表示為j→h1→…→hdi→k，令Hi(j,k)={h1,…,hdi}；d(-i,j,k)表示在不經(jīng)過節(jié)點(diǎn)i的情況下，節(jié)點(diǎn)j到節(jié)點(diǎn)k的最短路徑長(zhǎng)度，不妨將這條最短路徑表示為j→h-1→…→hd-i→k ， 令 H-i(j,k)={h-1,…,hd-i}， 顯 然iH-i(j,k)。

注意一下幾點(diǎn)：

(1)由于機(jī)會(huì)成本以及時(shí)間成本的存在，一般認(rèn)為有向賦權(quán)網(wǎng)絡(luò)中的節(jié)點(diǎn)選擇最短路徑來獲取網(wǎng)絡(luò)中其他節(jié)點(diǎn)的資源或信息。

（3）如果i?Hi(j,k)，說明節(jié)點(diǎn)j可不經(jīng)過節(jié)點(diǎn)i獲得節(jié)點(diǎn)k的相關(guān)資源或信息，那么Hi(j,k)=H-i(j,k)，并且d(i,j,k)=d(-i,j,k)。

（4）如果Hi(j,k)=，即節(jié)點(diǎn)j無法到達(dá)節(jié)點(diǎn)k，顯然H-i(j,k)=?且d(i,j,k)=d(-i,j,k)=+∞，說明任意節(jié)點(diǎn)在建立節(jié)點(diǎn)j與節(jié)點(diǎn)k連接方面并未起到橋梁作用。因此，可近似將刪除節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j與節(jié)點(diǎn)k的損失看作0。

（5）如果Hi(j,k)≠?但H-i(j,k)=?，說明在刪除節(jié)點(diǎn)i前，節(jié)點(diǎn)j經(jīng)過節(jié)點(diǎn)i可到達(dá)節(jié)點(diǎn)k，但刪除節(jié)點(diǎn)i后，節(jié)點(diǎn)j無法到達(dá)節(jié)點(diǎn)k，即節(jié)點(diǎn)i在建立節(jié)點(diǎn)j與節(jié)點(diǎn)k連接方面起到橋梁作用。若節(jié)點(diǎn)k的勢(shì)不低于節(jié)點(diǎn)j的勢(shì)，那么刪除節(jié)點(diǎn)i將給網(wǎng)絡(luò)中的節(jié)點(diǎn)造成不小的損失。

（6）如果Hi(j,k)≠?且H-i(j,k)≠?，說明刪除節(jié)點(diǎn)i，可能使得網(wǎng)絡(luò)中剩余節(jié)點(diǎn)需經(jīng)過更長(zhǎng)的路徑才能與其他節(jié)點(diǎn)建立連接。

定義2刪除節(jié)點(diǎn)i后，對(duì)有向賦權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)j(j∈N{i,k})與節(jié)點(diǎn)k(k∈Γi)間的間接橋梁損失NLIB(i,j,k)可表示為：

其中，M為一很大的正數(shù)。

因此，刪除節(jié)點(diǎn)i后有向賦權(quán)網(wǎng)絡(luò)的間接橋梁損失NLIB(i)可表示為：

1.2.3 間接連接損失

另一方面，刪除節(jié)點(diǎn)i也會(huì)給網(wǎng)絡(luò)中通過間接連接方式獲得節(jié)點(diǎn)i的資源或信息的那些節(jié)點(diǎn)產(chǎn)生損失。對(duì)鄰接矩陣X進(jìn)行乘法運(yùn)算，可分析出有向賦權(quán)網(wǎng)絡(luò)中間接獲得節(jié)點(diǎn)i的資源或信息的節(jié)點(diǎn)數(shù)并找出相應(yīng)的間接連接路徑。

1.2.4 節(jié)點(diǎn)重要性的測(cè)度

這里我們將節(jié)點(diǎn)重要性的測(cè)度等價(jià)為該節(jié)點(diǎn)被刪除后對(duì)網(wǎng)絡(luò)中剩余節(jié)點(diǎn)的破壞性（損失）。因此，節(jié)點(diǎn)的重要性可定義為：

定義4有向賦權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)i的重要性NI(i)表示為

其中,α、β、γ≥0分別表示在度量節(jié)點(diǎn)重要性時(shí)，刪除節(jié)點(diǎn)i將給網(wǎng)絡(luò)造成的直接損失、間接橋梁損失以及間接連接損失的權(quán)重，且α+β+γ=1。

定義5有向賦權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)i的相對(duì)重要性RNI(i)可定義為：

2 模型分析

為了更好地理解幾種典型的節(jié)點(diǎn)重要性判斷方法的差異性，探討本文所提出的度量方法的有效性和適用性，這里以文獻(xiàn)[4]給出的數(shù)據(jù)為例，對(duì)幾種典型的節(jié)點(diǎn)重要性判斷方法的計(jì)算結(jié)果進(jìn)行比較分析。

圖1 有向賦權(quán)網(wǎng)絡(luò)圖

表1 節(jié)點(diǎn)直接損失、間接橋梁損失以及間接連接損失計(jì)算結(jié)果

從表1可以看出，相同節(jié)點(diǎn)在有向賦權(quán)網(wǎng)絡(luò)的不同網(wǎng)絡(luò)結(jié)構(gòu)下，具有不同的直接損失、間接橋梁損失以及間接連接損失，從而具有不同的網(wǎng)絡(luò)地位。有向賦權(quán)網(wǎng)絡(luò)中的節(jié)點(diǎn)若具有相對(duì)較優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)位置及較高的勢(shì)，那么這類節(jié)點(diǎn)的流失將給網(wǎng)絡(luò)造成較大的損失，如圖1（i）、（iii）中的節(jié)點(diǎn)1與節(jié)點(diǎn)5。反之，若節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)位置較劣或節(jié)點(diǎn)的勢(shì)相對(duì)較低，節(jié)點(diǎn)在有向賦權(quán)網(wǎng)絡(luò)中地位較低，如圖1（ii）中的節(jié)點(diǎn)1，雖然節(jié)點(diǎn)1的勢(shì)相對(duì)較高，但網(wǎng)絡(luò)中其他節(jié)點(diǎn)并未關(guān)注到該節(jié)點(diǎn)。

表2對(duì)本文及文獻(xiàn)[3]、[4]所給的節(jié)點(diǎn)重要性判斷方法的排序結(jié)果進(jìn)行比較。由于文獻(xiàn)[6]、[12]均針對(duì)無向網(wǎng)絡(luò)進(jìn)行研究，因此表2給出的文獻(xiàn)[6]、[12]排序結(jié)果可看作是針對(duì)圖1（i）的分析結(jié)果。對(duì)比這三種度量方法，我們發(fā)現(xiàn)這種對(duì)圖1（i）中節(jié)點(diǎn)1在網(wǎng)絡(luò)中的重要程度的分析結(jié)果是一致的，但在其他節(jié)點(diǎn)重要性的分析上出現(xiàn)了分歧。文獻(xiàn)[3]所給方法分析出節(jié)點(diǎn)6是網(wǎng)絡(luò)中最不重要的節(jié)點(diǎn)，然而本文認(rèn)為是節(jié)點(diǎn)2與節(jié)點(diǎn)3，文獻(xiàn)[4]認(rèn)為是節(jié)點(diǎn)2。由于節(jié)點(diǎn)2具有最低的勢(shì)且未起到任何“橋梁”作用，因此刪除圖1（i）中的節(jié)點(diǎn)2，對(duì)網(wǎng)絡(luò)中其他節(jié)點(diǎn)不會(huì)造成損失；若刪除節(jié)點(diǎn)3，雖然節(jié)點(diǎn)3不是網(wǎng)絡(luò)中勢(shì)最低的節(jié)點(diǎn)，勢(shì)比它低的節(jié)點(diǎn)（節(jié)點(diǎn)2與節(jié)點(diǎn)5）是通過間接連接的方式獲得節(jié)點(diǎn)3的相關(guān)信息或知識(shí)，但是節(jié)點(diǎn)2與節(jié)點(diǎn)5可以通過直接連接方式獲得比節(jié)點(diǎn)3還要多的信息或知識(shí)，因此刪除節(jié)點(diǎn)3也不會(huì)對(duì)網(wǎng)絡(luò)中其他節(jié)點(diǎn)造成損失；但是刪除節(jié)點(diǎn)6會(huì)導(dǎo)致節(jié)點(diǎn)5可能無法直接獲得更多的信息或知識(shí)，節(jié)點(diǎn)6不會(huì)是網(wǎng)絡(luò)中地位最低的節(jié)點(diǎn)。

表2 節(jié)點(diǎn)重要性度量方法對(duì)比

通過對(duì)比不同的節(jié)點(diǎn)重要性度量方法，表明本文提出的有向賦權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性的度量方法能更細(xì)致地凸顯節(jié)點(diǎn)之間的差異性，并比較客觀地反映節(jié)點(diǎn)的物理屬性以及節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)位置對(duì)網(wǎng)絡(luò)整體的影響。因此，本文所提出的方法具有廣泛的實(shí)用性以及對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)具有指導(dǎo)價(jià)值。

[1]Song X,Wang X,Li A,et al.Node Importance Evaluation Method for Highway Network of Urban Agglomeration[J].Journal of Transportat?lon Systems Engineering and Informatlon Technology,2011,11(2).

[2]Cowan R,Jonard N.Network Structure and the Diffusion of Knowledge[J].Journal of Economic Dynamics and Control,2004,28(8).

[3]Okumura Y.A network Formation Process Converges to the Complete Collaboration Network[J].Mathematical Social Sciences,2007,53(2).

[4]王建偉,榮莉莉,郭天柱.一種參數(shù)可調(diào)的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法[J].科研管理,2009,30(4).

[5]安世虎,聶培堯,賀國(guó)光.節(jié)點(diǎn)賦權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的綜合測(cè)度法[J].管理科學(xué)學(xué)報(bào),2006,9(6).

[6]單海燕,王文平.面向產(chǎn)量決策的多寡頭網(wǎng)絡(luò)最優(yōu)結(jié)構(gòu)分析[J].管理科學(xué)學(xué)報(bào),2010,13(5).

F27

A

1002-6487（2012）24-0029-03

國(guó)家自然科學(xué)基金資助項(xiàng)目（70973017；71172044）

單海燕（1981-），女，江蘇鹽城人，博士，講師，研究方向：系統(tǒng)建模及網(wǎng)絡(luò)分析。

（責(zé)任編輯/易永生）