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

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

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

1 相關(guān)算法

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

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

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

接近中心性（CC）是基于最短路徑衡量節(jié)點(diǎn)重要性的指標(biāo)，反映節(jié)點(diǎn)通過網(wǎng)絡(luò)對其他節(jié)點(diǎn)施加影響的能力，反映網(wǎng)絡(luò)的全局結(jié)構(gòu)，只能應(yīng)用于連通的網(wǎng)絡(luò)中。如公式(3)所示：成的網(wǎng)絡(luò)不連通。在新形成的網(wǎng)絡(luò)中計(jì)算網(wǎng)絡(luò)平均最短路徑長度，通過計(jì)算網(wǎng)絡(luò)前后平均最短路徑長度變化率作為節(jié)點(diǎn)j對網(wǎng)絡(luò)的影響力。網(wǎng)絡(luò)平均最短路徑長度變化越大，節(jié)點(diǎn)j對網(wǎng)絡(luò)的影響力越大。例如節(jié)點(diǎn)8的連邊吸收到節(jié)點(diǎn)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)解、司法行政機(jī)關(guān)的人民調(diào)解，加強(qiáng)銜接聯(lián)動(dòng)，擰成一股繩，讓當(dāng)事人既有面子又有里子。

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

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

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

圖G的平均最短路徑：

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

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

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

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

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

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

3 衡量指標(biāo)

3.1 傳播模型

使用SIR傳播模型計(jì)算標(biāo)準(zhǔn)排序結(jié)果，在典型的傳染病模型中，N個(gè)節(jié)點(diǎn)的狀態(tài)可分為3類：

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

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

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

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

3.2 Kendall tau距離

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

5 結(jié)語

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