基于有效距離的復雜網絡節點影響力度量方法

馬媛媛,韓 華

(武漢理工大學理學院，武漢 430070)

0 引言

現實世界中的許多復雜系統可以抽象為復雜網絡模型。近年來，網絡科學研究受到了物理、數學、化學、醫學、生物學、計算機科學等領域學者的廣泛關注[1-3]，其中度量節點的影響力并挖掘關鍵節點是網絡科學的重要研究之一。一方面，關鍵節點的數量通常較少，但對網絡結構和功能有著很大的影響，例如，在電力網絡中某主要區段的線路故障將導致整個網絡癱瘓；另一方面，識別關鍵節點在檢測金融風險、防止恐怖襲擊、控制流行病傳播等方面有廣泛的應用價值[4-5]。

目前，許多經典的中心性被提出，其中度中心性[6]、介數中心性[7]、接近中心性[8]、特征向量中心性[9]、PageRank[10]和k-shell中心性[11]等在度量節點影響力中得到了廣泛的應用。現有的算法研究可分為三大類：一是基于網絡局部信息，如度中心性，僅利用節點本身的信息，時間復雜度低，適合于大規模網絡，但忽略網絡的大部分信息，精度較低；二則基于網絡全局信息，如介數中心性、接近中心性和特征向量中心性，根據整個網絡的結構特征確定節點的傳播能力，具有較高的準確性，但計算復雜度較高，不適合大規模網絡；此外，近年來出現了一種介于局部中心性與全局中心性之間的折衷方法—半局部中心性算法，具有精度高、時間復雜度低、考慮的信息較全面的特點。例如，胡鋼等[12]通過研究節點與其直接鄰居及間接鄰居之間的關聯關系，提出了基于鄰接信息熵的網絡節點重要性識別算法；Wang等[13]基于網絡中節點與多階鄰居的殼值，利用向量形式表示節點在復雜網絡中的相對重要性,提出了多階鄰居殼數向量中心性算法。

近幾年，學者們認為用單一的中心性算法來描述網絡節點的重要性是片面的，嘗試從不同角度來度量節點的重要性，并將多屬性決策方法(MCDM)[14-15]和機器學習方法[16]應用到節點的影響力度量上。如Bian等[17]將多種不同的中心性作為復雜網絡的多屬性度量指標，利用層次分析法(AHP)對多屬性指標進行聚合，評價節點的影響力；郭強等[18]采用多屬性排序方法(TOPSIS)對時序網絡不同時間片段節點的影響力進行綜合評價；韓忠明等[19]選取了7個經典節點重要性度量指標,并引入List Net排序學習方法構建了一個基于結構洞的節點重要性排序綜合評價方法。

節點的影響力是指節點傳播信息的能力，而信息傳播依附于具體的網絡，故網絡結構必定會對信息的傳播過程產生影響，進而影響節點的重要性，然而上述研究并未充分考慮網絡結構特征對節點重要性的影響。因此，本文基于網絡結構特征引入有效距離函數，同時從節點和鄰居兩個角度度量節點的傳播能力，提出一種新的半局部中心性度量方法，然后根據熵權法計算權重，并用VIKOR方法對節點的重要性進行排序。

1 相關研究

假設無向網絡G=(V,E)包含|V|=N個節點和|E|=M條邊，網絡的鄰接矩陣用A=(aij)N×N表示，當節點vi與節點vj之間存在連接時aij=1，否則aij=0。

1.1 度中心性

度為網絡拓撲結構的基本參數，度中心性(DC)是一種簡單直觀的排序方法，節點的度表示節點vi的鄰居個數，其中τ(i)表示節點vi的鄰居集合。

(1)

1.2 接近中心性

接近中心性(CC)反應節點在網絡中居于中心的程度，式(2)中dij表示節點vi到節點vj的距離。

(2)

1.3 介數中心性

(3)

1.4 k-shell中心性

k-shell分解是一種粗粒度的網絡分解算法，主要根據節點的度數的更新不斷地刪除網絡中的節點，進而得到節點的核值，一般用字母ks表示節點的核值，分解過程如下：

1)首先計算網絡中節點的度數，刪除節點度數k≤1的節點及其相連的邊，更新網絡并重新計算度數，再刪除度k≤1的節點，直到網絡中不存在度數k≤1的節點，記這些刪除的節點ks=1。

2)遞歸地刪除網絡中節點度數k≤2的節點及其相連的邊，之后更新網絡并重新計算度，記ks=2。

3)重復上述過程，直到每個節點都被賦予ks值。

1.5 GIN中心性

GIN中心性[20]是一種同時考慮節點和鄰居信息的節點重要性評估算法，式(4)中ki表示節點vi的度，dij表示節點vi到節點vj的距離。

(4)

2 一種新的節點影響力度量算法

2.1 有效距離

任意相鄰節點之間的距離設置為1，是計算節點間距離最基本的方法，但它與現實網絡中信息流交互的原理相違背。信息通過節點后，根據節點與鄰居的連接情況，將信息流分配到不同的路徑，故任意兩節點間距離不應總相等。2013年,Brockmann和Helbing等[21]基于網絡拓撲的局部信息，提出了兩個連通節點之間的有效距離,將任意兩個節點vi和vj間的有效距離定義為

d(i,j)=1-logPji

(5)

2.2 SN中心性

考慮到節點的重要性不僅與節點本身有關，還與鄰居節點的信息有關，本文從兩個角度考慮節點的重要性，提出了一種基于節點度值和有效距離量化節點影響力的中心性—SN中心性。

從節點的本身考慮，用度屬性來表征節點的重要性，定義為

(6)

從鄰居角度考慮，用鄰居度與相對距離的比值來表征節點的重要性，定義為

(7)

為接近真實傳播情況,式(7)中τ(i)表示節點的兩步內鄰居。避免兩角度結合的主觀性,本文采用VIKOR方法[22]得到距理想解最近的折衷可行解SN,權重依據熵權法確定,具體過程如下:

1)根據網絡中所有節點的SEi和NEi值，建立一個決策矩陣D。

(8)

2)標準化決策矩陣D,并構建標準矩陣R。

(9)

(10)

3)計算第j個屬性的熵。

(11)

4)則第j個準則的權重為

(12)

5)確定出正理想解r+和負理想解r-。

(13)

其中,J和J′是效益標準集(標準越高，節點越重要)和成本標準集(條件越高，節點越不重要)，文中這兩個標準都是效益標準。

6)各節點的群體效用值Si和個體遺憾值Ri按式(14)計算:

(14)

7)計算節點i的VIKOR重要度。

SNi=v(Si-S-)/(S+-S-)+(1-v)(Ri-R-)/(R+-R-)

(15)

S+=maxSi,S-=minSi,R+=maxRi,R-=minRi

(16)

其中,v為決策機制系數，取v=0.5，兼顧群體效用最大化和個體遺憾最小化。SNi是第i個節點重要性的綜合評價值，SNi越小則第i個節點越重要。節點重要性的向量可表示為

Te=[SN1,…,SNi,…,SNn]

(17)

8)根據節點的重要性值將Te升序排列。

(18)

2.3 算例分析

示例網絡中節點在不同排序方法下的排序結果如表1所示，其中最后一列補充了各節點SN算法的值。由表1可知，DC算法給予節點3、節點7相同排名，但刪除節點7后，圖1將不是一個連通圖，故節點7的影響力應強于節點3；KS算法區分節點的能力較差；BC算法給予8個節點相同的排名，表明算法的穩定性較差；CC算法給節點8的排名靠前，而其他算法中節點8則處于較后的排名，是因其側重與其他節點間距離而出現的偏差；GNI、SN算法的排序結果較優，但GNI算法給出節點8的排名低于節點10，從兩節點的連邊情況看，節點8應優于節點10的排名，故SN算法的排序結果更優。

圖1 示例

表1 示例網絡的排序結果

2.4 算法流程

算法在引入有效距離的基礎上，從兩個角度考慮了節點重要性。已知網絡的鄰接矩陣A，具體算法步驟如下:

2)根據式(6)和式(7)分別計算各角度下節點的重要性；

3)構建決策矩陣D并將其標準化得到標準化矩陣R;

4)根據式(11)計算各重要性的信息熵;

5)根據式(12)計算權重;

6)根據式(13)確定正理想解r+和負理想解r-;

7)根據式(14)計算各節點的群體效用值Si和個體遺憾值Ri;

8)根據式(15)計算VIKOR重要度，并得到Te;

9)將Te按升序排列,得到節點排序。

3 評價標準

3.1 SIR模型

為衡量各種指標影響力排序結果的準確性，需已知節點的實際影響力排序。SIR(Susceptible-Infected-Recovered)模型[23]被廣泛用于描述疾病、謠言、信息傳播過程，故采用SIR模型對傳播過程進行模擬，得到節點影響力的標準排名σ。在SIR模型中，節點處于易感狀態S，感染狀態I，恢復狀態R三種狀態之一。個體被感染后以概率λ被治愈，治愈后對該疾病免疫,不再被感染。初始階段，設定網絡中任意一個節點為感染狀態，其他節點為易感狀態。傳播過程中，每個處于感染狀態的節點試圖用感染概率α(α也稱為傳播概率)感染其處于易感狀態的鄰居，然后以概率β進入恢復狀態，且不再被感染。這個過程重復進行，直到網絡中沒有受感染的節點。不失一般性,本文取傳播概率在傳播閾值附近，恢復概率β為1。Φ′為網絡中最后處于恢復狀態的節點總數，等同于初始感染節點的影響力。為了保證計算結果的可靠性，取M次試驗的平均值作為節點的實際影響力Φ(i)。

(19)

3.2 評估指標

3.2.1 區分度

TRF指標[24]的數值反映某種指標下節點得分的內部情況，TRF=0表示所有節點被賦予不同的中心性值,TRF=1表示所有節點被賦予相同的中心性值,故TRF指標值越小，節點獲得相同得分的數量越少，算法效果越好。TRF指標的定義如式(20)所示：

(20)

其中,n為將要排序數據的個數，一般是網絡中節點的個數，ns為數據中獲得相同得分的節點的數目。

3.2.2 相關性

實驗采用Kendall tau相關系數[25]衡量各指標排序結果準確性，其表達式為

(21)

4 實驗數據及分析

4.1 實驗數據

為評估提出算法的效果，實驗選取6個真實網絡數據，包括Karate[26]，Dolphin[27]，Jazz[28]，Football[29]，USAir[30]，Netscience[31]。這些網絡的拓撲結構統計特征如表2所示。其中，N與M分別為網絡節點數與連邊數，C為網絡集聚系數，〈k〉為節點平均度。

表2 6個真實網絡的拓撲參數

4.2 結果及分析

在6個真實網絡數據集上，將提出的SN中心性分別與度中心性、K-Shell中心性、介數中心性、接近中心性、GIN中心性進行對比。

不同指標值的排序即節點傳播能力的排名，當排名結果出現某一排名下頻率較高時，說明該排名下的節點眾多，對應的中心性性能較差；當排名長度相對更接近網絡中節點數時，排名結果分散，中心性性能較好。圖2展示了6個真實網絡中各指標下節點的排名分布情況,顯然,DC和KS在6個網絡中排名分布的高頻數高于其他中心性，且排名長度較短，表明DC和KS區分節點的傳播能力較弱。相比之下，DC、CC比BC、CC排名分布較好。幾乎所有情況下，GIN和SN的排名分布似一條直線，且排名分布長度與網絡中節點個數接近，表明其排名分布效果很好；同時從排名頻率高于直線的部分觀察，SN更優一些。

圖2 6個真實網絡中各指標下節點的排名分布情況

不同指標在不同網絡數據的TRF值見表3，結果表明所提出的SN算法在Karate，Dolphin，Football，Netscience網絡中得到的排序具有最高TRF值，即SN算法對節點排名有較好的差異性。SN算法在Jazz，USAir網絡中單調性值也處于第二位，優于DC，KS，BC，CC的排序結果。

表3 不同指標在不同網絡數據的TRF值

各個指標在不同的傳播率下的排序準確性如圖3所示，當傳播率較小時，度中心性的準確性較高，是因為傳播率較小時，單節點開始的SIR傳播過程易局限于節點的局部鄰域，此時節點的度越大，感染到的節點也越多。當傳播率變大，接近傳播閾值時，SN中心性的準確性逐漸高于前者，說明同時考慮節點與鄰居的度與有效距離更接近于真實結果。

圖3 6個真實網絡中不同指標評估準確性對比

表4 各指標下Karate網絡中排名前五的節點

表5 各指標下Dolphin網絡中排名前五的節點

表6 各指標下Football網絡中排名前五的節點

表7 各指標下Jazz網絡中排名前五的節點

表8 各指標下Usair網絡中排名前五的節點

表4～表9分別比較6個不同網絡中各中心性度量排名前5的節點。KS算法將較多節點分解在同一層，故未在此比較。SN算法融合了DC，BC，CC，GIN四者中出現頻率高的節點，排名的相關性較高。

表9 各指標下Netscience網絡中排名前五的節點

5 結論

準確度量復雜網絡中節點的重要性對于加快積極信息在網絡中的傳播、預防網絡攻擊、抑制傳染病的爆發具有現實意義。本文考慮到任意相鄰節點間距離不等的情況，引入相對距離，提出了考慮節點度與節點間距離的中心性，并用熵權法和VIKOR法對節點重要性進行排序。在6個實際網絡進行了數值仿真，驗證所提方法的可行性和有效性。實驗結果表明，該方法不僅可以得到更準確的排序結果，而且有效減少了相同排序節點的出現頻率。