有偏隨機游走改進吸收中心性識別關(guān)鍵節(jié)點

寧 陽，寧 晴，武志峰

（1天津電子信息職業(yè)技術(shù)學(xué)院 計算機與軟件技術(shù)系，天津 300350；2北京聯(lián)合大學(xué) 信息服務(wù)重點實驗室，北京 100101；3天津職業(yè)技術(shù)師范大學(xué) 信息技術(shù)工程學(xué)院，天津 300222）

0 引 言

在電力交通、社交、生物、政治經(jīng)濟等領(lǐng)域，復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點識別具有實際應(yīng)用意義。如：復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點識別，可以在電力交通網(wǎng)絡(luò)中挖掘樞紐節(jié)點，進行重點保護，達到降低經(jīng)濟風(fēng)險的目的；在社交網(wǎng)絡(luò)中最有影響力的人，能夠被準(zhǔn)確的挖掘出來，使廣告效益得到最大化的同時，可以有助于流言傳播的控制；在蛋白質(zhì)網(wǎng)絡(luò)中可以對關(guān)鍵蛋白質(zhì)進行挖掘，這些蛋白質(zhì)在機體再生和生存時是不能或缺的；在生物網(wǎng)絡(luò)中，為醫(yī)藥發(fā)展提供有價值的理論和方法。

復(fù)雜網(wǎng)絡(luò)重要節(jié)點識別這一問題，從網(wǎng)絡(luò)局部、全局信息方面考慮，可以將其劃分為基于鄰居節(jié)點的結(jié)構(gòu)化指標(biāo)、基于路徑的結(jié)構(gòu)化指標(biāo)、基于節(jié)點移除及收縮的中心性指標(biāo)、基于迭代尋優(yōu)的中心性指標(biāo)進行節(jié)點重要性研究。在無向網(wǎng)絡(luò)，度中心性方法、介數(shù)中心性方法、接近中心性方法等，都是比較經(jīng)典的關(guān)鍵點識別方法。度中心性方法存在節(jié)點的度值與重要性不一定成正比問題，而介數(shù)中心性方法和接近中心性方法具有較高的時間復(fù)雜度，研究人員通常與典型算法進行比較，改進算法的有效性。在有向網(wǎng)絡(luò)，使用迭代尋優(yōu)的中心性指標(biāo)PageRank算法，以及在此基礎(chǔ)上改進的關(guān)鍵點識別方法（如；引入背景節(jié)點的LeaderRank算法、傾向于入度（出度）節(jié)點大的鄰居節(jié)點轉(zhuǎn)移的Pro_PageRank、DPRank算法等等），均存在參數(shù)問題。加權(quán)網(wǎng)絡(luò)中，利用節(jié)點的邊權(quán)信息，重新定義邊權(quán)的節(jié)點移除及收縮方法進行關(guān)鍵節(jié)點識別，其算法時間復(fù)雜度隨著網(wǎng)絡(luò)規(guī)模的增加而增加。融合其他理論，基于證據(jù)理論和TOPSIS、灰色關(guān)聯(lián)度分析、層次分析法、相對熵等方法進行多屬性決策，對各指標(biāo)的權(quán)重重新分配，來綜合判別關(guān)鍵節(jié)點；也可與社區(qū)劃分、圖著色理論、投票算法、聚類算法等相結(jié)合，用于識別一組關(guān)鍵節(jié)點。此外，文獻［20］中提出了一種將游走相似和表征節(jié)點重要性進行疊加的方法，對節(jié)點度、鄰接節(jié)點的屬性以及節(jié)點在網(wǎng)絡(luò)中的位置加以融合，基于的隨機游走是等概率的，但未對實際網(wǎng)絡(luò)中游走的傾向性進行考慮；文獻［8］利用理想狀態(tài)下等概率的隨機游走計算首次到達時間，提出吸收中心性算法，其中未將隨機游走向節(jié)點轉(zhuǎn)移的概率納入研究機制。

綜上所述，本文在文獻［8］的基礎(chǔ)上進行擴展研究，結(jié)合鄰居節(jié)點的度（出度、入度）信息，在無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)中考慮信息傳播的傾向性，利用隨機游走首次可達時間構(gòu)建轉(zhuǎn)移概率矩陣，用以識別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點。

1 相關(guān)概念

1.1 網(wǎng)絡(luò)表示

1.2 隨機游走

隨機游走是一個很有用的工具，借助這個工具可以對復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)進行研究；有時也將隨機游走模型稱為布朗運動，其是一種理想的數(shù)學(xué)狀態(tài)。隨機游走可以理解為無法基于過去的行為對后續(xù)的發(fā)展步驟和方向進行預(yù)測。假設(shè)當(dāng)前節(jié)點有4個鄰居節(jié)點，該節(jié)點向其周圍鄰居節(jié)點的轉(zhuǎn)移概率均為1／4，這是一種無限制的等概率隨機游走。若將節(jié)點之間轉(zhuǎn)移的傾向性考慮進來，就成為了一種無限制的有偏隨機游走。

1.3 關(guān)鍵節(jié)點識別算法

根據(jù)網(wǎng)絡(luò)是否具有方向性，將關(guān)鍵節(jié)點識別算法應(yīng)用的網(wǎng)絡(luò)類型劃分為無向與有向兩種。在無向網(wǎng)絡(luò)中，衡量節(jié)點的重要性，主要基于鄰居節(jié)點的信息和路徑；有向網(wǎng)絡(luò)中主要通過迭代尋優(yōu)的方法，改進PageRank算法，利用節(jié)點的點權(quán)信息擴展到加權(quán)網(wǎng)絡(luò)，以及將多屬性進行融合，結(jié)合局部信息和全局信息進行關(guān)鍵節(jié)點識別。

1.3.1 無向網(wǎng)絡(luò)關(guān)鍵節(jié)點識別

度中心性（Degree Centrality）考慮節(jié)點的局部信息，認為節(jié)點的重要性取決于中心性，其高低取決于節(jié)點度的值。在無向圖中，公式（1）為節(jié)點的度中心性：

式中，為節(jié)點總個數(shù)，（）為v的度中心性值。

介數(shù)中心性（Betweenness Centrality）方法，對節(jié)點的全局信息進行考慮。認為信息傳播時，經(jīng)過的是最短路徑?？坍嫻?jié)點的重要性時，采用每個節(jié)點的最短路徑數(shù)目。但該節(jié)點不一定是網(wǎng)絡(luò)中度最大或者是網(wǎng)絡(luò)的拓撲中心。公式（2）為v的介數(shù)中心性：

式中，n（）為經(jīng)過v的v和v之間的最短路徑數(shù)；n為v和v之間的最短路徑總數(shù)；（）為v的介數(shù)中心性值。

接近中心性（Closeness Centrality）是衡量節(jié)點重要性指標(biāo)時的最短路徑。借助網(wǎng)絡(luò)對其它節(jié)點施加影響的能力來反映節(jié)點，反映網(wǎng)絡(luò)的全局結(jié)構(gòu)，該方法只能應(yīng)用于連通網(wǎng)絡(luò)中。v的接近中心性如公式（3）：

式中：（）為節(jié)點的接近中心性值。

1.3.2 有向網(wǎng)絡(luò)關(guān)鍵節(jié)點識別

PageRank是一種可以按照重要性對網(wǎng)頁排序的方法。一個頁面是否質(zhì)量高，在于其輸入是否有很多高質(zhì)量的頁面。也就是說如果有很多概率比較大的節(jié)點指向同一個節(jié)點，則通過某個節(jié)點到達該節(jié)點的概率也會高。為了使懸掛節(jié)點的問題得以解決，PageRank算法中每一個節(jié)點均以一定的幾率跳轉(zhuǎn)到網(wǎng)絡(luò)中的任一節(jié)點，經(jīng)過不斷迭代，使每個節(jié)點的值趨于穩(wěn)定，如公式（4）：

式中：P為節(jié)點的值，1是跳轉(zhuǎn)概率，也稱阻尼系數(shù)，通常085。

LeaderRank在解決出度為0的懸掛節(jié)點問題時，添加了一個虛擬背景節(jié)點，使網(wǎng)絡(luò)中所有節(jié)點與其兩兩雙向連接，當(dāng)?shù)_到穩(wěn)定，將虛擬背景節(jié)點的權(quán)值平均分配給每一個節(jié)點。該指標(biāo)值與節(jié)點重要性成正比。如公式（5）：

其中，t表示穩(wěn)態(tài)時刻。

Pro-PageRank方法是在節(jié)點轉(zhuǎn)移過程中，更傾向沿著權(quán)重大的邊游走。邊的權(quán)重通過出度節(jié)點的入度鄰居信息衡量。即節(jié)點轉(zhuǎn)移時更傾向于沿著入度大的節(jié)點進行，如公式（6）：

DPRank方法考慮兩步轉(zhuǎn)移節(jié)點信息，節(jié)點更傾向于出度大的節(jié)點轉(zhuǎn)移。DP方法構(gòu)建的轉(zhuǎn)移概率矩陣如公式（7）：

1.4 評價指標(biāo)

1.4.1 Kendall tau距離

Kendall tau距離用來計算兩個排序列表之間成對分歧數(shù)量，即兩個完整列表和，（，）表示兩個列表之間的差異性。

∈［0，1］，值越大，則相似性越小。Kendall距離歸一化處理得到：

將其用于比較一個序列與另一個類似標(biāo)準(zhǔn)答案的排序序列的相似性，得出排序序列有效性，K值與兩個列表之間相似性成正比。列表與列表計算Kendall tau距離相似值的二元組集合，表1中分別列出列表的所有二元組組合。當(dāng)（）（）且（）（）或者（）（）且（）（）時1，否則0。

例：｛1，2，3，4｝，｛1，3，2，4｝，其中表示標(biāo)準(zhǔn)序列。

表1 σ列表與τ列表二元組集合Tab.1 Two tuple sets ofσlist andτlist

由上表可知值，進而得到兩個列表之間的相似性：K＝12?14?30833

1.4.2 SIR傳播模型

本文使用SIR傳播模型，模擬信息在網(wǎng)絡(luò)中的傳播過程，用于表示節(jié)點的傳播能力。在典型的傳染病模型中，可將個節(jié)點的狀態(tài)分為如下3類：

（1）（易染狀態(tài)）：在初始條件下將所有節(jié)點均定義為該狀態(tài)，該節(jié)點被鄰居節(jié)點感染的概率為；

（2）（感染狀態(tài)）：說明該節(jié)點已經(jīng)感染某種病毒，已成為傳染源，感染其直接易感鄰居節(jié)點的概率為；

（3）（移除狀態(tài)）：感染狀態(tài)節(jié)點以概率將鄰居易感節(jié)點轉(zhuǎn)變?yōu)楦腥緺顟B(tài)后，以概率變?yōu)橐瞥隣顟B(tài)，不再具有感染能力和易感特性。

本文采用SIR為多源感染模型，初始時刻假設(shè)網(wǎng)絡(luò)中的節(jié)點為個，其余均為個體。一個單位時間內(nèi)，所有處于節(jié)點以概率將其周圍鄰居節(jié)點感染之后，以值為1的概率轉(zhuǎn)變?yōu)?，在不存在易感?jié)點時達到穩(wěn)定狀態(tài)。此時對處于的節(jié)點個數(shù)進行統(tǒng)計，用于衡量初始感染狀態(tài)節(jié)點的傳播能力，記為。為減少、參數(shù)帶來的隨機性，每個節(jié)點計算100次，利用平均值進行計算。對網(wǎng)絡(luò)中的所有節(jié)點均執(zhí)行以上操作，節(jié)點傳播能力的大小即為網(wǎng)絡(luò)中節(jié)點的重要度。

2 有偏隨機游走改進吸收中心性算法

基于網(wǎng)絡(luò)中的隨機游走原理，利用到達吸收節(jié)點時間提出的吸收中心性方法，由于其在研究隨機游走機制時，僅考慮理想狀態(tài)下的等概率隨機游走，并沒有考慮網(wǎng)絡(luò)中信息流傳播的復(fù)雜性問題。針對于此，本文將信息流在隨機游走時向節(jié)點轉(zhuǎn)移的概率納入研究。在無向網(wǎng)絡(luò)中，節(jié)點信息傾向于度大的節(jié)點轉(zhuǎn)移；在有向網(wǎng)絡(luò)中，節(jié)點的轉(zhuǎn)移分別傾向于沿著出度、入度大的節(jié)點，將節(jié)點的重要性進行分析對比。

2.1 算法原理

吸收中心性方法（AS）是一種隨機游走機制，這種機制是基于網(wǎng)絡(luò)中等概率的，是利用網(wǎng)絡(luò)中節(jié)點的吸收過程提出的一種識別重要節(jié)點的方法。吸收節(jié)點是在網(wǎng)絡(luò)中任意選擇一個節(jié)點，對網(wǎng)絡(luò)中其他節(jié)點等概率的隨機游走到節(jié)點的首次到達時間進行計算。該方法采用信息流的效率評估標(biāo)準(zhǔn)是首次到達時間，該節(jié)點的重要性衡量指標(biāo)，是網(wǎng)絡(luò)中其它節(jié)點到吸收節(jié)點的平均首次到達時間。平均吸收時間越短，其它節(jié)點到該節(jié)點的距離就越小，節(jié)點越重要。算法公式（9）：

本文提出對算法的改進工作，是在無向網(wǎng)絡(luò)中根據(jù)鄰居節(jié)點的度信息重新設(shè)置邊權(quán)。鄰居節(jié)點的度越大，信息越傾向于向該方向進行轉(zhuǎn)移，為此提出了_算法；在有向網(wǎng)絡(luò)中，基于鄰居節(jié)點的出度和入度信息，分別提出了_、_算法。

無向網(wǎng)絡(luò)重新構(gòu)建轉(zhuǎn)移概率矩陣，采用文獻［8］提出的設(shè)置吸收節(jié)點的方法，衡量節(jié)點重要性，定義為_：

式中：()為的鄰居節(jié)點集合；P為轉(zhuǎn)移概率矩陣的值；W為節(jié)點、之間邊的權(quán)值。

在有向網(wǎng)絡(luò)中，本文定義的_D中心性指標(biāo)中節(jié)點間的轉(zhuǎn)移概率矩陣如式（11）：

考慮網(wǎng)絡(luò)節(jié)點的方向性，該指標(biāo)中存在設(shè)置的吸收節(jié)點。由于吸收節(jié)點和出度鄰居節(jié)點間存在直接連邊，為避免轉(zhuǎn)移概率為0的情況，采用每個節(jié)點的出度均加1，同時避免了分母為0的問題。

在有向網(wǎng)絡(luò)中，公式（12）為本文定義的_D中心性指標(biāo)中節(jié)點間的轉(zhuǎn)移概率矩陣。在吸收節(jié)點的鄰居節(jié)點均為邊界節(jié)點時，v向每個鄰居節(jié)點隨機游走的概率均為1／k，該指標(biāo)等同于等概率的隨機游走。

為了方便計算分析，按照最大值，將各節(jié)點的中心性值歸一化處理，如式（13）：

2.2 案例分析

本節(jié)通過計算實例，對算法的計算過程進行解釋，如圖1所示。其中包含9個節(jié)點12條邊的無向網(wǎng)絡(luò)，假設(shè)吸收節(jié)點為節(jié)點1，將其代入式（9）、式（10），計算所有節(jié)點有偏隨機游走到吸收節(jié)點1的首達時間。各中心性方法的中心性值見表2。

圖1 案例網(wǎng)絡(luò)Fig.1 Case network

表2 各中心性方法所有節(jié)點的中心性值Tab.2 Centrality values of all nodes in each centrality method

3 實驗分析

根據(jù)上述分析，為驗證本文提出基于有偏隨機游走改進的吸收中心性算法（GAS_D、GAS_Dout、GAS_Din），識別關(guān)鍵點的有效性，對無向網(wǎng)絡(luò)（karate、USAir、911terriset、Email）、有向網(wǎng)絡(luò)（Freemans、Organisational、Celegansneural）進行仿真實驗，實驗數(shù)據(jù)集的網(wǎng)絡(luò)參數(shù)見表3。

表3中，表示節(jié)點數(shù)；表示邊數(shù)；表示節(jié)點平均度；max表示節(jié)點最大度；表示網(wǎng)絡(luò)節(jié)點間最短路徑平均數(shù)；表示聚類系數(shù)，用來評估節(jié)點聚集成團的集聚程度；表示同配系數(shù)，用來反映鄰接節(jié)點間的度相關(guān)性；表示異質(zhì)系數(shù)，衡量網(wǎng)絡(luò)中節(jié)點度分布的異質(zhì)性。

實驗環(huán)境為：Intel（R）Core（TM）i3-2367M CPU＠1.40 GHz、4 GB內(nèi)存、Windows7、python3.2.732位，使用Python語言實現(xiàn)算法。共設(shè)計3組對比實驗，對算法的有效性和準(zhǔn)確性進行驗證。

實驗內(nèi)容如下：

（1）對比分析本文提出的改進算法與其它中心性算法中心性值的相關(guān)性。單調(diào)性表現(xiàn)越明顯，算法之間的相關(guān)性越好。

（2）采用數(shù)學(xué)計算，度量Kendall tau距離計算相關(guān)系數(shù)。以本文提出的改進算法為標(biāo)準(zhǔn)，對該算法與其它方法之間的相似性量化分析，相似性越大說明算法越有效。

（3）基于SIR多源傳播感染模型，在不同感染概率下，對各算法識別出的TopK節(jié)點在穩(wěn)定狀態(tài)下平均感染的節(jié)點數(shù)進行比較。

表3 數(shù)據(jù)集參數(shù)Tab.3 Parameters of datasets

GAS_D算法在5個無向網(wǎng)絡(luò)中，各算法的中心性值與其它中心性算法之間的相似性分析圖，以及Kendall tau的相似性系數(shù)如圖2所示。與其它3種中心性算法相比，本文提出的改進算法GAS_D與改進前的AS算法相關(guān)性最強，單調(diào)性表現(xiàn)最明顯，kendall tau的相似性值最大，與DC、CC算法的相關(guān)性次之。通過對單調(diào)性表現(xiàn)進行觀察，GAS_D與CC具有更明顯的相關(guān)性，與BC算法的相關(guān)性最不明顯。GAS_D與DC、CC算法共同考慮了節(jié)點的度信息、節(jié)點間的最短路徑，表現(xiàn)出了明顯的相關(guān)性。在5個不同的數(shù)據(jù)集下，本文提出算法與改進前AS、DC、BC、CC算法的平均相似性見表4。karate數(shù)據(jù)集包含32個節(jié)點，且各算法識別出的Top10節(jié)點差別不大，故而基于SIR傳播模型，進一步討論其他4個數(shù)據(jù)集各算法識別出的Top10節(jié)點在不同感染概率下達到穩(wěn)定狀態(tài)的感染節(jié)點數(shù)占節(jié)點總數(shù)的百分比（式（14）），以此衡量Top10節(jié)點的感染能力（如圖3所示）。

在4個數(shù)據(jù)集中均可以明顯看出，當(dāng)感染概率足夠大的情況下，各方法識別出的Top結(jié)果在穩(wěn)定狀態(tài)下均可以覆蓋整個網(wǎng)絡(luò)；各中心性算法識別出的Top10節(jié)點不同的感染概率∈（0，1］下，達到穩(wěn)定狀態(tài)的結(jié)果趨勢一致，沒有表現(xiàn)出明顯差異，說明了算法的有效性；在感染概率0.5左右，911terriset、Netscience數(shù)據(jù)集中，改進的GAS_D算法均優(yōu)于改進之前的AS算法，感染節(jié)點數(shù)更多，說明本文算法的有效性，并且優(yōu)于改進之前的算法。

文獻［8］提出的吸收中心性方法并沒在有向網(wǎng)絡(luò)中進行拓展研究，本文將其拓展方法記為ZAS，并與提出的有偏隨機游走改進之后的GAS_Dout、GAS_Din算法，在3個真實的網(wǎng)絡(luò)進行對比研究，各算法之間的相關(guān)性及Kendall tau相似性系數(shù)如圖4～圖6所示。在Freeman、Organisational、Celegansneural數(shù)據(jù)集中，ZAS算法識別結(jié)果更接近于PageRank、LeaderRank；GAS_Din算法識別結(jié)果更接近于Pro_PageRank算法；GAS_Dout算法識別結(jié)果更接近于DPRank。在3個數(shù)據(jù)集下，ZAS、GAS_Din、GAS_Dout分 別 與 PageRank、LeaderRank、Pro_PageRank、DPRank的相似性見表4。

由表4中數(shù)據(jù)可見，ZAS、PageRank、LeaderRank均為等概率的向鄰居節(jié)點進行轉(zhuǎn)移，而GAS_Din、Pro_PageRank更傾向于向入度大的節(jié)點進行轉(zhuǎn)移，GAS_Dout、DPRank更傾向于向出度大的節(jié)點進行轉(zhuǎn)移，故算法之間表現(xiàn)出更強的相關(guān)性。Top10節(jié)點在不同感染概率下達到穩(wěn)定狀態(tài)下的感染節(jié)點率如圖7所示，各算法識別結(jié)果的總體趨勢相同，一定程度說明了ZAS、GAS_Din、GAS_Dout算法的有效性，GAS_Dout的識別結(jié)果也明顯優(yōu)于GAS_Din、ZAS算法，GAS_Dout的準(zhǔn)確性更高。

表4 本文提出算法與其他算法識別結(jié)果的相似性對比Tab.4 The similarity comparison between the recognition results of the proposed algorithm and other algorithms

圖2 不同網(wǎng)絡(luò)中GAS_D算法與其它中心性算法的相關(guān)性及Kendall tau相關(guān)系數(shù)Fig.2 Correlation between GAS_D algorithm and other centrality algorithms and Kendall tau correlation coefficient in different networks

圖3 無向網(wǎng)絡(luò)中各中心性算法識別出的Top10節(jié)點在不同感染概率下平穩(wěn)狀態(tài)值Fig.3 The stationary state values of top 10 nodes identified by centrality algorithms under different infection probabilities in undirected networks

圖4 Freemans中ZAS、GAS_Dout、GAS_Din算法與其它中心性算法的相關(guān)性及Kendall tau相關(guān)系數(shù)Fig.4 Correlation between ZAS、GAS_Dout、GAS_Din algorithm and other centrality algorithms and Kendall tau correlation coefficient in Freemans

圖5 Organisational中ZAS、GAS_Dout、GAS_Din算法與其它中心性算法的相關(guān)性及Kendall tau相關(guān)系數(shù)Fig.5 Correlation between ZAS、GAS_Dout、GAS_Din algorithm and other centrality algorithms and Kendall tau correlation coefficient Organisational

圖6 Celegansneural中ZAS、GAS_Dout、GAS_Din算法與其它中心性算法的相關(guān)性及Kendall tau相關(guān)系數(shù)Fig.6 Correlation between ZAS、GAS_Dout、GAS_Din algorithm and other centrality algorithms and Kendall tau correlation coefficient in Celegansneural

圖7 有向網(wǎng)絡(luò)中各中心性算法識別出的Top10節(jié)點在不同感染概率下平穩(wěn)狀態(tài)值Fig.7 The stationary state values of top 10 nodes identified by centrality algorithms under different infection probabilities in directed networks

4 結(jié)束語

本文基于無向網(wǎng)絡(luò)中等概率的吸收中心性方法，基于節(jié)點的度信息，提出適用于無向網(wǎng)絡(luò)的GAS_D算法進行不等概率有偏的關(guān)鍵節(jié)點識別，并與節(jié)點的出度信息結(jié)合，將AS算法拓展到有向網(wǎng)絡(luò)，結(jié)合鄰居節(jié)點的出度和入度信息，提出GAS_Dout、GAS_Din算法。通過真實的無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)設(shè)計仿真實驗證明：在無向網(wǎng)絡(luò)中，本文提出的考慮現(xiàn)實網(wǎng)絡(luò)中信息轉(zhuǎn)移傾向性的改進算法優(yōu)于改進之前的算法；在有向網(wǎng)絡(luò)中，考慮鄰居節(jié)點的出度節(jié)點信息對信息的擴散更有利，本文算法在有向網(wǎng)絡(luò)中的擴展，也解決了PageRank及其改進算法的參數(shù)問題。后續(xù)工作將邊值的權(quán)重考慮在內(nèi)進行進一步的拓展研究。