面向有向賦權網絡的節點重要性度量方法研究

單海燕

（南京信息工程大學經濟管理學院，南京 210044）

面向有向賦權網絡的節點重要性度量方法研究

單海燕

（南京信息工程大學經濟管理學院，南京 210044）

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

有向賦權網絡；相對重要性；直接損失；間接橋梁損失；間接連接損失

0 引言

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

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

1 節點重要性的度量模型

1.1 基本定義

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

可采用社會網絡中的鄰接矩陣表示有向賦權網絡結構，鄰接矩陣中的行和列表示網絡中的各節點，并且行和列排列的順序都相同，矩陣中行位置的行動者通常是某種特定關系的發送者，列位置的行動者通常是某種特定關系的接收者；矩陣中的元素，代表行動者之間是否存在某種關系，這樣的矩陣X記作

1.2 節點重要性的度量方法

1.2.1 直接損失

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

1.2.2 間接橋梁損失

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

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

注意一下幾點：

(1)由于機會成本以及時間成本的存在，一般認為有向賦權網絡中的節點選擇最短路徑來獲取網絡中其他節點的資源或信息。

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

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

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

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

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

其中，M為一很大的正數。

因此，刪除節點i后有向賦權網絡的間接橋梁損失NLIB(i)可表示為：

1.2.3 間接連接損失

另一方面，刪除節點i也會給網絡中通過間接連接方式獲得節點i的資源或信息的那些節點產生損失。對鄰接矩陣X進行乘法運算，可分析出有向賦權網絡中間接獲得節點i的資源或信息的節點數并找出相應的間接連接路徑。

1.2.4 節點重要性的測度

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

定義4有向賦權網絡中節點i的重要性NI(i)表示為

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

定義5有向賦權網絡中節點i的相對重要性RNI(i)可定義為：

2 模型分析

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

圖1 有向賦權網絡圖

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

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

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

表2 節點重要性度量方法對比

通過對比不同的節點重要性度量方法，表明本文提出的有向賦權網絡節點重要性的度量方法能更細致地凸顯節點之間的差異性，并比較客觀地反映節點的物理屬性以及節點的網絡結構位置對網絡整體的影響。因此，本文所提出的方法具有廣泛的實用性以及對現實網絡具有指導價值。

[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]王建偉,榮莉莉,郭天柱.一種參數可調的網絡節點重要性度量方法[J].科研管理,2009,30(4).

[5]安世虎,聶培堯,賀國光.節點賦權網絡中節點重要性的綜合測度法[J].管理科學學報,2006,9(6).

[6]單海燕,王文平.面向產量決策的多寡頭網絡最優結構分析[J].管理科學學報,2010,13(5).

F27

A

1002-6487（2012）24-0029-03

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

單海燕（1981-），女，江蘇鹽城人，博士，講師，研究方向：系統建模及網絡分析。

（責任編輯/易永生）