有偏隨機游走改進吸收中心性識別關鍵節點

寧 陽，寧 晴，武志峰

（1天津電子信息職業技術學院 計算機與軟件技術系，天津 300350；2北京聯合大學 信息服務重點實驗室，北京 100101；3天津職業技術師范大學 信息技術工程學院，天津 300222）

0 引 言

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

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

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

1 相關概念

1.1 網絡表示

1.2 隨機游走

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

1.3 關鍵節點識別算法

根據網絡是否具有方向性，將關鍵節點識別算法應用的網絡類型劃分為無向與有向兩種。在無向網絡中，衡量節點的重要性，主要基于鄰居節點的信息和路徑；有向網絡中主要通過迭代尋優的方法，改進PageRank算法，利用節點的點權信息擴展到加權網絡，以及將多屬性進行融合，結合局部信息和全局信息進行關鍵節點識別。

1.3.1 無向網絡關鍵節點識別

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

式中，為節點總個數，（）為v的度中心性值。

介數中心性（Betweenness Centrality）方法，對節點的全局信息進行考慮。認為信息傳播時，經過的是最短路徑。刻畫節點的重要性時，采用每個節點的最短路徑數目。但該節點不一定是網絡中度最大或者是網絡的拓撲中心。公式（2）為v的介數中心性：

式中，n（）為經過v的v和v之間的最短路徑數；n為v和v之間的最短路徑總數；（）為v的介數中心性值。

接近中心性（Closeness Centrality）是衡量節點重要性指標時的最短路徑。借助網絡對其它節點施加影響的能力來反映節點，反映網絡的全局結構，該方法只能應用于連通網絡中。v的接近中心性如公式（3）：

式中：（）為節點的接近中心性值。

1.3.2 有向網絡關鍵節點識別

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

式中：P為節點的值，1是跳轉概率，也稱阻尼系數，通常085。

LeaderRank在解決出度為0的懸掛節點問題時，添加了一個虛擬背景節點，使網絡中所有節點與其兩兩雙向連接，當迭代達到穩定，將虛擬背景節點的權值平均分配給每一個節點。該指標值與節點重要性成正比。如公式（5）：

其中，t表示穩態時刻。

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

DPRank方法考慮兩步轉移節點信息，節點更傾向于出度大的節點轉移。DP方法構建的轉移概率矩陣如公式（7）：

1.4 評價指標

1.4.1 Kendall tau距離

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

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

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

例：｛1，2，3，4｝，｛1，3，2，4｝，其中表示標準序列。

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

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

1.4.2 SIR傳播模型

本文使用SIR傳播模型，模擬信息在網絡中的傳播過程，用于表示節點的傳播能力。在典型的傳染病模型中，可將個節點的狀態分為如下3類：

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

（2）（感染狀態）：說明該節點已經感染某種病毒，已成為傳染源，感染其直接易感鄰居節點的概率為；

（3）（移除狀態）：感染狀態節點以概率將鄰居易感節點轉變為感染狀態后，以概率變為移除狀態，不再具有感染能力和易感特性。

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

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

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

2.1 算法原理

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

本文提出對算法的改進工作，是在無向網絡中根據鄰居節點的度信息重新設置邊權。鄰居節點的度越大，信息越傾向于向該方向進行轉移，為此提出了_算法；在有向網絡中，基于鄰居節點的出度和入度信息，分別提出了_、_算法。

無向網絡重新構建轉移概率矩陣，采用文獻［8］提出的設置吸收節點的方法，衡量節點重要性，定義為_：

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

在有向網絡中，本文定義的_D中心性指標中節點間的轉移概率矩陣如式（11）：

考慮網絡節點的方向性，該指標中存在設置的吸收節點。由于吸收節點和出度鄰居節點間存在直接連邊，為避免轉移概率為0的情況，采用每個節點的出度均加1，同時避免了分母為0的問題。

在有向網絡中，公式（12）為本文定義的_D中心性指標中節點間的轉移概率矩陣。在吸收節點的鄰居節點均為邊界節點時，v向每個鄰居節點隨機游走的概率均為1／k，該指標等同于等概率的隨機游走。

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

2.2 案例分析

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

圖1 案例網絡Fig.1 Case network

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

3 實驗分析

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

表3中，表示節點數；表示邊數；表示節點平均度；max表示節點最大度；表示網絡節點間最短路徑平均數；表示聚類系數，用來評估節點聚集成團的集聚程度；表示同配系數，用來反映鄰接節點間的度相關性；表示異質系數，衡量網絡中節點度分布的異質性。

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

實驗內容如下：

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

（2）采用數學計算，度量Kendall tau距離計算相關系數。以本文提出的改進算法為標準，對該算法與其它方法之間的相似性量化分析，相似性越大說明算法越有效。

（3）基于SIR多源傳播感染模型，在不同感染概率下，對各算法識別出的TopK節點在穩定狀態下平均感染的節點數進行比較。

表3 數據集參數Tab.3 Parameters of datasets

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

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

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

由表4中數據可見，ZAS、PageRank、LeaderRank均為等概率的向鄰居節點進行轉移，而GAS_Din、Pro_PageRank更傾向于向入度大的節點進行轉移，GAS_Dout、DPRank更傾向于向出度大的節點進行轉移，故算法之間表現出更強的相關性。Top10節點在不同感染概率下達到穩定狀態下的感染節點率如圖7所示，各算法識別結果的總體趨勢相同，一定程度說明了ZAS、GAS_Din、GAS_Dout算法的有效性，GAS_Dout的識別結果也明顯優于GAS_Din、ZAS算法，GAS_Dout的準確性更高。

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

圖2 不同網絡中GAS_D算法與其它中心性算法的相關性及Kendall tau相關系數Fig.2 Correlation between GAS_D algorithm and other centrality algorithms and Kendall tau correlation coefficient in different networks

圖3 無向網絡中各中心性算法識別出的Top10節點在不同感染概率下平穩狀態值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算法與其它中心性算法的相關性及Kendall tau相關系數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算法與其它中心性算法的相關性及Kendall tau相關系數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算法與其它中心性算法的相關性及Kendall tau相關系數Fig.6 Correlation between ZAS、GAS_Dout、GAS_Din algorithm and other centrality algorithms and Kendall tau correlation coefficient in Celegansneural

圖7 有向網絡中各中心性算法識別出的Top10節點在不同感染概率下平穩狀態值Fig.7 The stationary state values of top 10 nodes identified by centrality algorithms under different infection probabilities in directed networks

4 結束語

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