單海燕

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

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

單海燕

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

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

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

0 引言

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

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

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

1.1 基本定義

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

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

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

1.2.1 直接損失

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

1.2.2 間接橋梁損失

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

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

注意一下幾點：

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

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

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

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

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

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

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

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

1.2.3 間接連接損失

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

1.2.4 節(jié)點重要性的測度

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

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

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

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

2 模型分析

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

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

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

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

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

表2 節(jié)點重要性度量方法對比

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

[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é)點重要性度量方法[J].科研管理,2009,30(4).

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

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

F27

A

1002-6487（2012）24-0029-03

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

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

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