面向有向網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別算法研究

寧 陽(yáng)，武志峰，寧 晴

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

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

1 相關(guān)概念

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

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

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

1.2 相關(guān)算法

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

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

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

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

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

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

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

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

2 擴(kuò)展Jaccard指標(biāo)關(guān)鍵節(jié)點(diǎn)識(shí)別算法

2.1 擴(kuò)展Jaccard指標(biāo)構(gòu)建轉(zhuǎn)移概率矩陣

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

Jaccard指數(shù)

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

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

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

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

通過(guò)概率標(biāo)準(zhǔn)化處理，得到轉(zhuǎn)移概率矩陣。上述相似性指標(biāo)標(biāo)準(zhǔn)化處理，使轉(zhuǎn)移概率矩陣中各行元素之和均為1。

式中：pij為概率矩陣中的元素為概率標(biāo)準(zhǔn)化后對(duì)應(yīng)位置的值。

2.2 基于相似和的疊加隨機(jī)游走

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

設(shè)各個(gè)節(jié)點(diǎn)的初始資源分布為qx，基于t步隨機(jī)游走的相似性為

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

相似度矩陣中的值代表對(duì)應(yīng)節(jié)點(diǎn)之間的相似度，每一行代表當(dāng)前節(jié)點(diǎn)與其他所有節(jié)點(diǎn)的相似度，采用文獻(xiàn)[8]提出的相似和概念衡量節(jié)點(diǎn)重要性。累加各行相似度，得到基于相似和的疊加隨機(jī)游走相似性指標(biāo)，并將其標(biāo)準(zhǔn)化處理，將其用作網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別。

算法步驟：

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

②根據(jù)擴(kuò)展的Jaccard指數(shù)計(jì)算轉(zhuǎn)移概率矩陣；

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

④利用節(jié)點(diǎn)重要性最大值進(jìn)行標(biāo)準(zhǔn)化處理。

3 實(shí)驗(yàn)分析

3.1 評(píng)價(jià)指標(biāo)

3.1.1 SIR傳播模型

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

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

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

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

采用單源感染模型，初始時(shí)刻，假設(shè)網(wǎng)絡(luò)中只有一個(gè)節(jié)點(diǎn)處于感染狀態(tài)，其余個(gè)體均處于易感狀態(tài)，一個(gè)單位時(shí)間內(nèi)，所有處于感染狀態(tài)的節(jié)點(diǎn)以β=的概率感染其周?chē)従庸?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)的個(gè)數(shù)，用于衡量初始感染狀態(tài)節(jié)點(diǎn)的傳播能力。為減少β、γ參數(shù)帶來(lái)的隨機(jī)性，每個(gè)節(jié)點(diǎn)計(jì)算100次，利用平均值進(jìn)行計(jì)算。對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)均執(zhí)行相同操作，根據(jù)節(jié)點(diǎn)的傳播能力得到網(wǎng)絡(luò)中節(jié)點(diǎn)重要度排序。其中，＜k＞為平均度，＜k2＞為平均度方。

3.1.2 Kendall tau距離

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

K∈[0，1]，K 值越大，相似性越小。Kendall距離歸一化處理得，將其用于比較一個(gè)序列與另一個(gè)類(lèi)似標(biāo)準(zhǔn)答案的排序序列的相似性，得出排序序列有效性，K′值越大，2個(gè)列表之間相似性越大。σ列表與τ列表計(jì)算Kendall tau距離相似值的過(guò)程如表1所示。

表1 σ列表與τ列表計(jì)算Kendall tau距離相似值的過(guò)程

表中分別列出列表的所有二元組組合，當(dāng)σ（i）＜σ（j）且 τ（i）＞ τ（j）或者 σ（i）＞ σ（j）且 τ（i）＜ τ（j）時(shí)，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 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

圖2 各中心性算法之間的相關(guān)性

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

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

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

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

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

4 結(jié)語(yǔ)

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