面向有向網絡關鍵節點識別算法研究

寧 陽，武志峰，寧 晴

（1.天津職業技術師范大學信息技術工程學院，天津 300222；2.北京聯合大學信息服務工程重點實驗室，北京 100101）

關鍵節點識別算法的研究在醫學、社會學、網絡安全、電力交通、政治與經濟學等領域有重要意義，是復雜網絡中重要的研究課題之一，是近年來國內外學者研究的重點問題。如在社會網絡中通過挖掘關鍵節點控制流言的傳播，疾病傳播過程中挖掘關鍵節點控制疾病的蔓延，電力交通網絡中識別關鍵樞紐進行重點維護，科學引文網絡中通過挖掘關鍵節點找到學科帶頭人，互聯網絡中根據關鍵節點進行頁面排序等，這些都可以降低經濟成本，保證正常運行[1]。在考慮有向網絡中的節點重要性時可以簡單地將有向網絡視為無向網絡，利用無向網絡中的節點重要性指標進行識別，但是這種方法忽略了節點之間的方向性[2]。考慮節點的方向性，Page等[3]提出的算法是有向網絡中節點重要性排序的經典算法之一，網頁鏈接向節點的出度節點進行轉移，使整個網絡的概率轉移達到平穩狀態，但是存在節點出度為0的懸掛節點和參數不確定問題；Kleinberg[4]提出的HITS算法考慮用節點的權威值（authority）和樞紐值（hub）的指標衡量節點重要性，但是沒有在實際的搜索引擎中廣泛應用；LYU等[5]提出的LeaderRank算法通過添加虛擬背景節點與網絡中所有節點雙向連接，解決PageRank算法的懸掛節點和消除參數影響的問題，但仍存在計算復雜度高的問題；Wang等[6]提出的 Pro-PageRank 和 Liu 等[7]提出的DPRank方法考慮了入度（出度）節點的鄰居節點信息，前者傾向于向入度節點更大的節點方向轉移，后者考慮傾向于向出度大的節點轉移，改進了PageRank算法，但是仍存在懸掛節點需要以等概率向任意節點跳轉的參數問題；宋琛等[8]提出的疊加隨機游走計算相似和衡量節點重要性的方法能夠有效地在無向網絡中進行關鍵節點識別，但該方法沒有考慮節點間概率轉移的傾向問題，也沒有解決如何在有向網絡中進行關鍵節點識別的問題。本文基于Jaccard拓展指標[9]改進疊加隨機游走方法，提出解決有向網絡中傳統關鍵節點識別方法的參數問題，以期更有效地在有向網絡中進行關鍵節點的識別。

1 相關概念

1.1 網絡表示

將一個具體網絡抽象為一個由點集V和邊集E組成的圖G=（V，E）。頂點數記為N=|V|，邊數記為M=|E|。有向無權圖G的鄰接矩陣A=（aij）N×N是一個N階方陣，第i行第j列上的元素aij定義如下：

有向網絡中節點i的度包括出度和入度，節點i的出度kiout（kiin）表示節點i指向其他節點（其他節點指向節點 i）的邊的數目[2]，即

1.2 相關算法

PageRank是一種對網頁按重要性進行排序的方法，如果一個頁面被很多高質量頁面指向，那么該網頁的質量也很高，即一個節點被很多概率比較大的節點指向，那么通過某個節點到達這個節點的概率也越高。為了解決懸掛節點問題，PageRank算法中每一個節點都會以一定的概率跳轉到網絡中的任一節點，經過不斷迭代，每個節點的PageRank值將趨于穩定。

式中：Pi（tn）為節點i第tn步的PageRank值；N為節點個數；1-c為跳轉概率，也稱阻尼系數，通常c=0.85。

文獻[5]通過添加一個虛擬的背景節點g，使其與網絡中所有節點兩兩雙向連接，解決出度為0的懸掛節點問題，當迭代達到穩定，將虛擬背景節點的權值平均分配給每一個節點，以此來衡量節點重要性，該指標值越大，節點越重要。

式中：LeaderRanki（tn）為節點i第tn步的LeaderRank值；tc為穩態時刻；LeaderRanki為節點 i最終LeaderRank值。

文獻[6]提出一種改進的Pro-PageRank方法，節點在轉移過程中更傾向沿著權重大的邊游走，邊的權重通過出度節點的入度鄰居信息衡量，即節點更傾向于沿著入度大的節點進行轉移。

式中：p（j，i）為節點j向節點i轉移的概率；Γout（j）為節點j的出度鄰居節點集合，即節點j指向的節點集合；Γin（i）為節點i的入度鄰居節點集合，即指向節點i的節點的集合；Pro-PageRanki（tn）為節點i第tn步的Pro-PageRank值。

文獻[7]考慮兩步轉移節點信息，節點更傾向于度（出度）大的節點轉移，提出適用于有無向網絡（有向網絡）的DPRank關鍵點識別方法，無向網絡中通過轉移概率矩陣的轉置計算最大特征值1對應的特征向量衡量節點重要性，有向網絡通過迭代計算可通過達到平穩分布時節點的DPRank值衡量節點重要性。值得注意的是有向網絡中仍存在出度節點的出度和為0的懸掛節點，即兩步轉移沒有可達節點的情況，此時以1/n的概率跳轉到任一節點。DPRank方法構建的轉移概率矩陣為

式中：kj為無向網絡中節點的度；Γ（i）為節點i的鄰居節點集合；Pij為轉移概率矩陣第i行第j列的值。

2 擴展Jaccard指標關鍵節點識別算法

2.1 擴展Jaccard指標構建轉移概率矩陣

隨機游走指基于過去的表現，無法預測將來的發展步驟和方向，下一步的選擇是隨機的。一般來講，節點通過存在邊到達相鄰節點的概率是相同的，到達非鄰居節點的概率是0，即等概率隨機選擇到達存在邊的節點。但實際中，從一個節點到其他鄰居節點的概率并不均勻隨機，而是有偏的，所以本文采用擴展的Jaccard指標衡量有向網絡中節點之間的相似性，考慮局部范圍內的節點信息。對于2節點之間是否存在直接連邊進行分別處理，從而進行確定轉移概率矩陣。

Jaccard指數

式中：sij為節點 vi、vj的相似性。

Jaccard指數擴展到有向網絡得到擴展指標，采用分母加1處理分母為0的情況。

有向網絡中2節點直接相連，若計算出Sij為0，則采用基于相似和的疊加隨機游走的方法節點出度分之1彌補擴展Jaccard指標計算不足的問題；無論節點之間是否直接相連，節點傾向于向相似度小的節點方向轉移，以尋找足夠少、差異較大、能夠覆蓋整個網絡的節點，但在2節點之間無直接連邊，計算出Sij為0的情況下，節點之間的轉移概率為0。

式中：Sij為擴展后用于衡量有向網絡節點相似性的指標。

通過概率標準化處理，得到轉移概率矩陣。上述相似性指標標準化處理，使轉移概率矩陣中各行元素之和均為1。

式中：pij為概率矩陣中的元素為概率標準化后對應位置的值。

2.2 基于相似和的疊加隨機游走

Liu等[10]考慮有限次的隨機游走，提出一種基于網絡局部隨機游走的相似性指標（LRW），在LRW基礎上，將t步及其以前的結果加和得到SRW的值，即

設各個節點的初始資源分布為qx，基于t步隨機游走的相似性為

利用一種與度分布一致性的初始資源qx=kx/M，M作為網絡的總邊數，對每一對節點對都相同，計算過程忽略不計。πyx（t）為walker從節點x經過t步游走到節點y的轉移概率矩陣，一般的k步轉移概率矩陣正好是一步轉移概率矩陣的k次方，可以證明k步轉移概率矩陣中各行元素之和都是1。

相似度矩陣中的值代表對應節點之間的相似度，每一行代表當前節點與其他所有節點的相似度，采用文獻[8]提出的相似和概念衡量節點重要性。累加各行相似度，得到基于相似和的疊加隨機游走相似性指標，并將其標準化處理，將其用作網絡中關鍵節點識別。

算法步驟：

①將有向網絡表示為鄰接矩陣的形式；

②根據擴展的Jaccard指數計算轉移概率矩陣；

③使用疊加隨機游走相似和方法衡量節點重要性值；

④利用節點重要性最大值進行標準化處理。

3 實驗分析

3.1 評價指標

3.1.1 SIR傳播模型

本文使用SIR傳播模型[2，11]得到的排序作為標準排序結果，在典型的傳染病模型中，N個節點的狀態可分為如下3類。

S：易染狀態，初始條件下所有節點均為易染狀態，該節點以β的概率被鄰居節點感染。

I：感染狀態，感染某種病毒作為傳染源的節點，該個體以β概率感染其鄰居節點。

R：移除狀態，也稱免疫狀態或恢復狀態，感染狀態節點以β概率感染鄰居易感節點后，以γ概率變為移除狀態R，不再具有感染能力和易感特性。

采用單源感染模型，初始時刻，假設網絡中只有一個節點處于感染狀態，其余個體均處于易感狀態，一個單位時間內，所有處于感染狀態的節點以β=的概率感染其周圍鄰居節點，之后以γ=1的概率變為移除狀態，統計達到穩定狀態時，即不存在易感節點，統計處于移除狀態節點的個數，用于衡量初始感染狀態節點的傳播能力。為減少β、γ參數帶來的隨機性，每個節點計算100次，利用平均值進行計算。對網絡中所有節點均執行相同操作，根據節點的傳播能力得到網絡中節點重要度排序。其中，＜k＞為平均度，＜k2＞為平均度方。

3.1.2 Kendall tau距離

Kendall tau距離[12-13]計算2個排序列表之間成對分歧數量，即2個列表σ和τ，K（σ，τ）表示2個列表之間的差異性

K∈[0，1]，K 值越大，相似性越小。Kendall距離歸一化處理得，將其用于比較一個序列與另一個類似標準答案的排序序列的相似性，得出排序序列有效性，K′值越大，2個列表之間相似性越大。σ列表與τ列表計算Kendall tau距離相似值的過程如表1所示。

表1 σ列表與τ列表計算Kendall tau距離相似值的過程

表中分別列出列表的所有二元組組合，當σ（i）＜σ（j）且 τ（i）＞ τ（j）或者 σ（i）＞ σ（j）且 τ（i）＜ τ（j）時，K=1，否則 K=0。

例：σ ={1，2，3，4}，τ={1，3，2，4}

由表 1可知，K 的值為 1，K′=1-2*1/4*3=0.833。

3.2 實驗結果與分析

根據上述分析，為了驗證本文提出方法的有效性及準確性，設計2組對比實驗，在2個網絡數據集進行仿真實驗，并與 PageRank（PR）、Pro-PageRank（Pro-PR）、LeaderRank（LR）、DPRank（DPR）算法指標進行對比分析，驗證算法的有效性；使用SIR傳播模型計算標準排序結果，計算各中心性算法與SIR的Kendall tau相關系數，驗證算法的準確性。

Freemans_EIES_3[14]網絡是從事社會網絡分析與研究之間關系的網絡，包含32個節點，442條有向邊，節點平均度 27.625，SIR傳播模型感染概率 β為0.029。使用Ucinet6數據可視化，Freemans數據集可視化如圖1所示。

圖1 Freemans數據集可視化

使用 PageRank、Pro-PageRank、LeaderRank、DPRank算法指標以及本文提出的JC方法在Freemans數據集進行仿真實驗，Freemans_EIES_3網絡各中心性算法值如表2所示。

表2 Freemans_EIES_3網絡各中心性算法值

由表2可知，識別出的Top 5節點有4個與其他方法一致，各算法識別出的Top 5節點中心性值加粗顯示，其中節點24在JC方法中處于Top 5，節點8在其他方法中處于Top 5，SIR傳播模型在該數據集仿真實驗表明，節點24的擴散能力大于節點8，說明本文提出的JC算法較其他算法更有效。

以算法排序等級為標準，各中心性算法之間的相關性如圖2所示。由圖2可知，本文算法中節點24、節點5的重要性與其他算法存在較大差異，節點24和節點5在SIR傳播模型中，均處在Top 5的位置，說明2個節點處于重要節點位置，本文算法優于其他算法。各中心性算法與SIR模型Kendall tau相似性比較如表3所示。從表3可知，比較了各中心性算法與SIR模型Kendall tau相關性，本文提出的方法比其他方法更接近，證明了提出方法的準確性。

圖2 各中心性算法之間的相關性

表3 各中心性算法與SIR模型Kendall tau相似性比較

Celegansneural[15]為一個有向含權網絡，節點為線蟲的神經元，邊為神經元突觸或間隙連接。網絡中包含297個節點和2 359條有向連接，節點平均度15.886，SIR傳播模型感染概率β為0.036。

使用 PageRank、Pro-PageRank、LeaderRank、DPRank算法指標以及本文提出的JC方法在Celegansneural數據集進行仿真實驗，計算網絡中各中心性算法識別出的Top 20節點，網絡各中心性算法Top 20節點ID如表4所示。

表4 網絡各中心性算法Top20節點ID

由表4可知，本文識別出的Top 3節點中，除DPRank方法外，節點44在PageRank、Pro-PageRank、LeaderRank方法中均處于Top 1；基于SIR傳播模型識別出的Top 3節點，其中JC算法Top 3中識別出2個，PageRank、LeaderRank 算法識別出 0 個，Pro-PageRank算法識別出1個，DPRank算法識別出2個；Top 5 節點中，JC 與 PageRank、Pro-PageRank、DPRank算法共同識別出40%，與LeaderRank算法共同識別出80%個節點，證明了本文提出的算法的有效性。通過表3比較各中心性算法與SIR模型Kendall tau相關性，證明本文算法準確性比PageRank、LeaderRank、Pro-PageRank有較大提升，但是略次于DPRank算法。通過在2個數據集進行仿真實驗，本文算法在實驗效果上與DPRank算法的準確性相似，明顯高于其他算法。但在實驗過程中，若采用傳統迭代計算PageRank及在此基礎上改進的其他算法的平穩分布，進而計算節點重要性值的方法，對于數據集Celegansneural節點個數297時間消耗大，本文算法計算效率優于其他算法。采用計算轉移概率矩陣轉置的最大特征值對應的特征向量方法[16]計算PageRank、Pro-PageRank、LeaderRank、DPRank，算法效率均得到明顯提升。

4 結語

本文采用Jaccard指數拓展到有向網絡結合疊加隨機游走進行關鍵節點識別，該方法中的Jaccard指數可以是任意的相似度指數的有向版本，將節點相似度和隨機游走結合進行關鍵節點識別，解決了疊加隨機游走計算相似和衡量節點重要性方法中有向網絡進行擴展的問題。實驗結果表明，本文提出的算法可有效地識別出網絡中的關鍵節點且識別精度高。考慮節點間隨機游走的傾向性，優于無偏的在節點之間進行隨機游走，解決了PageRank算法中存在參數的問題，識別精度明顯優于PageRank算法。