寧 陽，武志峰，寧 晴

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

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

1 相關概念

1.1 網(wǎng)絡表示

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

有向網(wǎng)絡中節(jié)點i的度包括出度和入度，節(jié)點i的出度kiout（kiin）表示節(jié)點i指向其他節(jié)點（其他節(jié)點指向節(jié)點 i）的邊的數(shù)目[2]，即

1.2 相關算法

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

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

文獻[5]通過添加一個虛擬的背景節(jié)點g，使其與網(wǎng)絡中所有節(jié)點兩兩雙向連接，解決出度為0的懸掛節(jié)點問題，當?shù)_到穩(wěn)定，將虛擬背景節(jié)點的權值平均分配給每一個節(jié)點，以此來衡量節(jié)點重要性，該指標值越大，節(jié)點越重要。

式中：LeaderRanki（tn）為節(jié)點i第tn步的LeaderRank值；tc為穩(wěn)態(tài)時刻；LeaderRanki為節(jié)點 i最終LeaderRank值。

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

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

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

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

2 擴展Jaccard指標關鍵節(jié)點識別算法

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

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

Jaccard指數(shù)

式中：sij為節(jié)點 vi、vj的相似性。

Jaccard指數(shù)擴展到有向網(wǎng)絡得到擴展指標，采用分母加1處理分母為0的情況。

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

式中：Sij為擴展后用于衡量有向網(wǎng)絡節(jié)點相似性的指標。

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

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

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

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

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

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

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

算法步驟：

①將有向網(wǎng)絡表示為鄰接矩陣的形式；

②根據(jù)擴展的Jaccard指數(shù)計算轉移概率矩陣；

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

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

3 實驗分析

3.1 評價指標

3.1.1 SIR傳播模型

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

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

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

R：移除狀態(tài)，也稱免疫狀態(tài)或恢復狀態(tài)，感染狀態(tài)節(jié)點以β概率感染鄰居易感節(jié)點后，以γ概率變?yōu)橐瞥隣顟B(tài)R，不再具有感染能力和易感特性。

采用單源感染模型，初始時刻，假設網(wǎng)絡中只有一個節(jié)點處于感染狀態(tài)，其余個體均處于易感狀態(tài)，一個單位時間內(nèi)，所有處于感染狀態(tài)的節(jié)點以β=的概率感染其周圍鄰居節(jié)點，之后以γ=1的概率變?yōu)橐瞥隣顟B(tài)，統(tǒng)計達到穩(wěn)定狀態(tài)時，即不存在易感節(jié)點，統(tǒng)計處于移除狀態(tài)節(jié)點的個數(shù)，用于衡量初始感染狀態(tài)節(jié)點的傳播能力。為減少β、γ參數(shù)帶來的隨機性，每個節(jié)點計算100次，利用平均值進行計算。對網(wǎng)絡中所有節(jié)點均執(zhí)行相同操作，根據(jù)節(jié)點的傳播能力得到網(wǎng)絡中節(jié)點重要度排序。其中，＜k＞為平均度，＜k2＞為平均度方。

3.1.2 Kendall tau距離

Kendall tau距離[12-13]計算2個排序列表之間成對分歧數(shù)量，即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 實驗結果與分析

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

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

圖1 Freemans數(shù)據(jù)集可視化

使用 PageRank、Pro-PageRank、LeaderRank、DPRank算法指標以及本文提出的JC方法在Freemans數(shù)據(jù)集進行仿真實驗，F(xiàn)reemans_EIES_3網(wǎng)絡各中心性算法值如表2所示。

表2 Freemans_EIES_3網(wǎng)絡各中心性算法值

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

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

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

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

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

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

表4 網(wǎng)絡各中心性算法Top20節(jié)點ID

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

4 結語

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