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

關鍵字:復雜網(wǎng)絡 關鍵節(jié)點 吸收節(jié)點 最短路徑

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

1 相關算法

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

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

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

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

圖1 案例網(wǎng)絡

網(wǎng)絡平均最短路徑：

網(wǎng)絡平均最短路徑變化率：

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

2.2 定義衡量節(jié)點重要性指標

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

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

圖G的平均最短路徑：

將節(jié)點8吸收到節(jié)點1的網(wǎng)絡平均最短路徑變化率：

轉(zhuǎn)移概率矩陣如下所示：

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

2 吸收節(jié)點衡量節(jié)點重要性方法

2.1 構建轉(zhuǎn)移概率矩陣

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

3 衡量指標

3.1 傳播模型

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

S：易染狀態(tài)，初始條件下所有節(jié)點的狀態(tài)，該節(jié)點以β的概率被鄰居節(jié)點感染；

I：感染狀態(tài)，感染某種病毒作為傳染源的節(jié)點，以β概率感染其鄰居節(jié)點；

R：移除狀態(tài)，感染狀態(tài)節(jié)點以β概率感染鄰居易感節(jié)點后，以γ概率變?yōu)镽。

采用單源感染模型，初始時刻，假設網(wǎng)絡中只有一個節(jié)點處于感染狀態(tài)，其余個體均處于易感狀態(tài)，一個單位時間內(nèi)，所有處于感染狀態(tài)的節(jié)點以β=0.25的概率感染其鄰居節(jié)點，以γ=1的概率變?yōu)橐瞥隣顟B(tài)，統(tǒng)計達到穩(wěn)定狀態(tài)時，即不存在易感節(jié)點，統(tǒng)計處于移除狀態(tài)節(jié)點和感染節(jié)點的個數(shù)衡量節(jié)點的傳播能力，記為F(tc)，tc為達到穩(wěn)定狀態(tài)的時間。為減少β、γ參數(shù)帶來的隨機性，獨立運行100次。

3.2 Kendall tau距離

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

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

4 實驗結果與分析

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

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

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

圖2 相關性分析圖

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

圖3 TOP10節(jié)點在不同時刻感染節(jié)點數(shù)

5 結語

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