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

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

關(guān)鍵字:復(fù)雜網(wǎng)絡(luò) 關(guān)鍵節(jié)點 吸收節(jié)點 最短路徑

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

1 相關(guān)算法

將網(wǎng)絡(luò)抽象為圖G=(V,E)，頂點數(shù)記為N=|V|，邊數(shù)記為M=|E|。圖G的鄰接矩陣A=（aij）N×N是一個N階方陣，節(jié)點i和j有邊，aij=1，否則為0。無向網(wǎng)絡(luò)中節(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é)點重要性的指標(biāo)，反映節(jié)點通過網(wǎng)絡(luò)對其他節(jié)點施加影響的能力，反映網(wǎng)絡(luò)的全局結(jié)構(gòu)，只能應(yīng)用于連通的網(wǎng)絡(luò)中。如公式(3)所示：成的網(wǎng)絡(luò)不連通。在新形成的網(wǎng)絡(luò)中計算網(wǎng)絡(luò)平均最短路徑長度，通過計算網(wǎng)絡(luò)前后平均最短路徑長度變化率作為節(jié)點j對網(wǎng)絡(luò)的影響力。網(wǎng)絡(luò)平均最短路徑長度變化越大，節(jié)點j對網(wǎng)絡(luò)的影響力越大。例如節(jié)點8的連邊吸收到節(jié)點1，如圖1案例網(wǎng)絡(luò)(a)-(b)所示。

圖1 案例網(wǎng)絡(luò)

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

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

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

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

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

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

圖G的平均最短路徑：

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

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

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

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

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

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

3 衡量指標(biāo)

3.1 傳播模型

使用SIR傳播模型計算標(biāo)準排序結(jié)果，在典型的傳染病模型中，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)镽。

采用單源感染模型，初始時刻，假設(shè)網(wǎng)絡(luò)中只有一個節(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距離歸一化處理，得將其用于比較一個序列與另一個類似標(biāo)準答案的排序序列的相似性，得出排序序列有效性, 值越大，相似性越大。

4 實驗結(jié)果與分析

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

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

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

圖2 相關(guān)性分析圖

基于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方法識別結(jié)果，和CC識別出的Top10節(jié)點的傳播能力無明顯差異。說明了ASC方法的有效性，且優(yōu)于DC和BC方法。

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

5 結(jié)語

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