改進的吸收中心性方法衡量節點重要性

寧陽 天津職業技術師范大學 信息技術工程學院 寧晴 北京聯合大學/北京市信息服務工程重點實驗室

關鍵字:復雜網絡 關鍵節點 吸收節點 最短路徑

近年來，節點重要性識別研究受到越來越廣泛的關注，在醫學、社會學、網絡安全、電力交通、政治與經濟學領域有重要研究意義。例如社會網絡中找到最有影響力的人控制流言的傳播，疾病傳播中找到易感人群，進行預防和控制，城市交通系統、電力系統中找到關鍵樞紐進行重點維護，降低經濟損失風險等。目前關于復雜網絡重要節點識別主要是在常用指標度值、介數、接近數、k-殼值基礎上進行改進和將多個指標融合綜合考慮節點重要性。基于多屬性融合決策關鍵節點的研究包括基于證據理論和TOPSIS多屬性決策，確定各指標的權重識別關鍵節點。基于網絡拓撲結構，Wang等提出節點刪除方法計算網絡效率識別關鍵節點，存在破壞網絡連通性的問題；Lv等提出的改進算法，將不連通節點之間距離通過網絡直徑解決；譚等提出的節點收縮方法將節點與鄰居節點凝聚為一個節點，通過網絡凝聚度衡量節點重要性。本文基于網絡平均最短距離、改進節點移除方法提出改進的吸收中心性方法，解決移除節點造成的網絡不連通問題，更有效的進行關鍵節點識別。

1 相關算法

將網絡抽象為圖G=(V,E)，頂點數記為N=|V|，邊數記為M=|E|。圖G的鄰接矩陣A=（aij）N×N是一個N階方陣，節點i和j有邊，aij=1，否則為0。無向網絡中節點度表示節點i的鄰居節點的個數，表示為度中心性（DC）考慮局部信息，認為節點的度越大，節點越重要。如公式(1)所示：

介數中心性（BC）考慮全局信息，認為信息是通過最短路徑進行傳播，以經過每個節點的最短路徑數目刻畫節點的重要性。如公式(2)所示：

式中：njk(i)為經過節點i的節點j和節點k之間的最短路徑數目，njk為節點j和節點k之間的最短路徑總數目。

接近中心性（CC）是基于最短路徑衡量節點重要性的指標，反映節點通過網絡對其他節點施加影響的能力，反映網絡的全局結構，只能應用于連通的網絡中。如公式(3)所示：成的網絡不連通。在新形成的網絡中計算網絡平均最短路徑長度，通過計算網絡前后平均最短路徑長度變化率作為節點j對網絡的影響力。網絡平均最短路徑長度變化越大，節點j對網絡的影響力越大。例如節點8的連邊吸收到節點1，如圖1案例網絡(a)-(b)所示。

圖1 案例網絡

網絡平均最短路徑：

網絡平均最短路徑變化率：

深化繁簡分流，優化資源配置，著力解決案多人少矛盾；加大調解力度，法院檢察院的司法調解、公安部門的行政調解、司法行政機關的人民調解，加強銜接聯動，擰成一股繩，讓當事人既有面子又有里子。

2.2 定義衡量節點重要性指標

本文考慮節點的鄰居節點，節點i為節點j的一個鄰居節點，通過2.1節計算了將節點j吸收到節點i時節點j對于整個網絡信息傳遞的影響力，考慮節點j的所有鄰居信息，綜合考慮節點j的影響能力。直觀反映在轉移概率矩陣中即為累加轉移概率矩陣中每行的值，節點j的吸收中心定義為ASC(j)：

如圖1所示的案例網絡，根據公式(4-6)計算如下：

圖G的平均最短路徑：

將節點8吸收到節點1的網絡平均最短路徑變化率：

轉移概率矩陣如下所示：

式中：dij為節點i到節點j的最短距離。

2 吸收節點衡量節點重要性方法

2.1 構建轉移概率矩陣

網絡中節點i和節點j之間存在直接連邊，表示兩節點之間有互相轉移的傾向性，無向網絡可以看成是具有雙向信息轉移的有向網絡，當信息從節點i傳遞到j，將以節點j為起點在網絡中傳播。信息的傳播通常是在最短路徑上進行傳播，故本文結合最短路徑衡量節點重要性。當信息從節點i傳遞到j，將節點j吸收到節點i，即將節點j的鄰居節點作為接節點i的鄰居節點。相比移除節點的同時移除節點的所有連邊，該方法移除了節點，沒有移除節點的邊，避免移除節點造

3 衡量指標

3.1 傳播模型

使用SIR傳播模型計算標準排序結果，在典型的傳染病模型中，N個節點的狀態可分為3類：

S：易染狀態，初始條件下所有節點的狀態，該節點以β的概率被鄰居節點感染；

I：感染狀態，感染某種病毒作為傳染源的節點，以β概率感染其鄰居節點；

R：移除狀態，感染狀態節點以β概率感染鄰居易感節點后，以γ概率變為R。

采用單源感染模型，初始時刻，假設網絡中只有一個節點處于感染狀態，其余個體均處于易感狀態，一個單位時間內，所有處于感染狀態的節點以β=0.25的概率感染其鄰居節點，以γ=1的概率變為移除狀態，統計達到穩定狀態時，即不存在易感節點，統計處于移除狀態節點和感染節點的個數衡量節點的傳播能力，記為F(tc)，tc為達到穩定狀態的時間。為減少β、γ參數帶來的隨機性，獨立運行100次。

3.2 Kendall tau距離

Kendall tau距離計算兩個排序列表之間成對分歧數量，K(σ,τ)表示σ、τ的差異性：

K∈[0,1]，K值越大，相似性越小。Kendall距離歸一化處理，得將其用于比較一個序列與另一個類似標準答案的排序序列的相似性，得出排序序列有效性, 值越大，相似性越大。

4 實驗結果與分析

為了驗證本文提出的改進的吸收中心性方法識別關鍵點的有效性，對Physicians網絡進行仿真實驗。Physicians—一個節點代表一個醫生，兩個節點之間存在邊說明兩個醫生對同一個話題感興趣或者二者是朋友的關系。取網絡的極大連通子圖，包含117個節點，465條邊。設計對比實驗，驗證本文提出方法的有效性和準確性。

通過各中心性算法與SIR模型Kendall tau距離相似性比較，ASC排序結果與標準排序之間相似性為0.86，次于DC相似性0.89，高于BC相似性0.84、CC相似性0.85，證明了該方法的有效性，排序精度較高。

基于SIR傳播模型，對于網絡中的每個節點作為初始感染節點，在t=10時刻計算F(t)與各中心性方法值的相關性。在t=10時刻基本達到穩定狀態。理論上中心性值越大的節點傳播感染能力F(t)越大，說明具有很強的相關性。如圖2所示，BC方法與F(t)的相關性最差，ASC和CC方法與F(t)的相關性最好，而DC方法的相關性也很好，但是對于網絡中度數相同的節點不能做區分，相關性略次與ASC和CC方法，在一定程度上證明了本文提出方法的有效性，且優于BC、DC方法。

圖2 相關性分析圖

基于SIR傳播模型，依次分析本文提出方法ASC與其他方法識別出的Top10節點作為SIR傳播模型的初始感染節點，在t∈[0,40]各時刻的平均感染能力。在該過程中，取兩種方法各自Top10節點的差異節點作為初始感染節點進行分析，減小計算量。從圖3(a-c)可以看出在t=10時刻，基本達到穩定狀態。ASC識別出的Top10節點明顯優于BC、DC方法識別結果，和CC識別出的Top10節點的傳播能力無明顯差異。說明了ASC方法的有效性，且優于DC和BC方法。

圖3 TOP10節點在不同時刻感染節點數

5 結語

針對復雜網絡中關鍵節點識別的問題，通過移除節點及其連邊的效率中心性會破壞網絡的拓撲結構使得移除節點后的網絡不連通，在此基礎上提出了改進的吸收節點中心性，吸收節點的連邊，使網絡保持連通性。結合網絡的平均最短距離及鄰居節點信息，將網絡的局部信息和全局信息綜合考慮。通過實驗分析證明，提出的改進吸收中心性方法可以有效的識別網絡中的關鍵節點。下一步與點權相結合，將其向有向加權網絡進行擴展，進行更深入的研究。