寧 陽(yáng)，武志峰，張 策

(天津職業(yè)技術(shù)師范大學(xué) 信息技術(shù)工程學(xué)院，天津 300222)

0 引 言

網(wǎng)絡(luò)科學(xué)研究的是看起來互不相同的復(fù)雜網(wǎng)絡(luò)之間共性和處理的普適方法。網(wǎng)絡(luò)科學(xué)中研究的問題來源于各種實(shí)際網(wǎng)絡(luò)，網(wǎng)絡(luò)中的關(guān)鍵點(diǎn)識(shí)別是網(wǎng)絡(luò)科學(xué)的重要研究?jī)?nèi)容之一。根據(jù)傳播動(dòng)力學(xué)的研究形成的理論和方法更好地認(rèn)識(shí)不同網(wǎng)絡(luò)上的傳播行為之間的聯(lián)系與區(qū)別。關(guān)鍵點(diǎn)識(shí)別的研究在不同的領(lǐng)域具有重要意義，例如在社會(huì)網(wǎng)絡(luò)中找到最有影響力的人可以控制流言的傳播，疾病傳播過程中找到易感人群，對(duì)疾病進(jìn)行有效的預(yù)防和控制，城市交通系統(tǒng)、電力系統(tǒng)中找到關(guān)鍵樞紐進(jìn)行重點(diǎn)維護(hù)，降低經(jīng)濟(jì)損失風(fēng)險(xiǎn)等。有效地評(píng)價(jià)和衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，借助圖論的概念和術(shù)語(yǔ)，將具體實(shí)際問題抽象為圖，得到網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，將多學(xué)科融合在一起作為研究方向，具有廣泛的應(yīng)用價(jià)值。

首先介紹提出不等概率疊加隨機(jī)游走的相關(guān)工作，然后介紹不等概率疊加隨機(jī)游走方法，構(gòu)建不等概率轉(zhuǎn)移矩陣，進(jìn)行疊加。隨機(jī)游走，通過相似和衡量節(jié)點(diǎn)重要性。通過對(duì)3個(gè)數(shù)據(jù)集的仿真實(shí)驗(yàn)，與度中心性、介數(shù)中心性、接近中心性和等概率疊加隨機(jī)游走進(jìn)行比較，并與SIR標(biāo)準(zhǔn)傳播模型[1-2]進(jìn)行Kendall tau距離[3-4]相關(guān)性分析，驗(yàn)證該方法的有效性。

1 相關(guān)工作

復(fù)雜網(wǎng)絡(luò)中關(guān)鍵點(diǎn)識(shí)別的排序方法很多，文獻(xiàn)[5]綜述了關(guān)鍵點(diǎn)識(shí)別問題和方法，并對(duì)其進(jìn)行分類，描述了最重要的進(jìn)展和最新技術(shù)。近年來，學(xué)者通常在衡量節(jié)點(diǎn)的常用指標(biāo)上進(jìn)行改進(jìn)。無向網(wǎng)絡(luò)中幾個(gè)常用衡量節(jié)點(diǎn)重要性的指標(biāo)包括度值、介數(shù)、接近數(shù)、k-殼值和特征向量[6-10]。有向網(wǎng)絡(luò)中經(jīng)典的兩個(gè)算法是Kleinberg提出的HITS算法[11]及Page和Brin提出的PageRank算法[12]。度中心性通過衡量一個(gè)節(jié)點(diǎn)的度，度越大節(jié)點(diǎn)越重要，即與節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置有關(guān)；介數(shù)中心性是經(jīng)過某一節(jié)點(diǎn)整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的最短路徑的數(shù)量反映節(jié)點(diǎn)重要性指標(biāo)；接近中心性通過計(jì)算當(dāng)前節(jié)點(diǎn)到網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)的距離在某種程度上反映節(jié)點(diǎn)重要性；k-殼值通過不斷地在原始網(wǎng)絡(luò)中去除度值為1，2，3…的節(jié)點(diǎn)及其連邊，從而進(jìn)行節(jié)點(diǎn)重要性識(shí)別的一種推廣的度值指標(biāo)；特征向量中心性既考慮了鄰居節(jié)點(diǎn)的數(shù)量又考慮了鄰居節(jié)點(diǎn)的重要性[1]。HITS算法通過刻畫節(jié)點(diǎn)的權(quán)威性和樞紐性指標(biāo)，衡量節(jié)點(diǎn)重要性。PageRank算法通過指向當(dāng)前節(jié)點(diǎn)的數(shù)量和質(zhì)量衡量節(jié)點(diǎn)重要性。文獻(xiàn)[13]提出通過節(jié)點(diǎn)間的相互作用力構(gòu)建隨機(jī)游走模型中的概率轉(zhuǎn)移矩陣，從物理學(xué)的角度考慮網(wǎng)絡(luò)中邊的實(shí)際意義。文獻(xiàn)[14]考慮節(jié)點(diǎn)度及鄰居節(jié)點(diǎn)拓?fù)渲睾隙?，獲取節(jié)點(diǎn)兩步內(nèi)的鄰居節(jié)點(diǎn)信息，通過計(jì)算節(jié)點(diǎn)之間相似度衡量節(jié)點(diǎn)重要性。文獻(xiàn)[15]提出半局部中心性方法，解決大規(guī)模網(wǎng)絡(luò)中時(shí)間消耗大的問題，僅考慮了節(jié)點(diǎn)兩步轉(zhuǎn)移到達(dá)節(jié)點(diǎn)的數(shù)量及節(jié)點(diǎn)度。文獻(xiàn)[16]考慮節(jié)點(diǎn)二階鄰居節(jié)點(diǎn)，節(jié)點(diǎn)更有遠(yuǎn)見的轉(zhuǎn)移到度(出度)大的節(jié)點(diǎn)，改進(jìn)PageRank指標(biāo)計(jì)算轉(zhuǎn)移概率矩陣的平穩(wěn)分布衡量節(jié)點(diǎn)重要性。文獻(xiàn)[17]結(jié)合節(jié)點(diǎn)中心性和邊的中心性指標(biāo)在無向網(wǎng)絡(luò)中重新定義轉(zhuǎn)移概率矩陣衡量節(jié)點(diǎn)重要性。文獻(xiàn)[18]提出了一種疊加游走相似和表征節(jié)點(diǎn)重要性的方法，考慮節(jié)點(diǎn)度、鄰接節(jié)點(diǎn)的屬性以及節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置，基于等概率的隨機(jī)游走，但未考慮實(shí)際網(wǎng)絡(luò)中游走的傾向性。

針對(duì)上述問題，以及受現(xiàn)有研究的啟發(fā)，考慮節(jié)點(diǎn)之間的相似性[19]，進(jìn)行有偏的隨機(jī)游走，考慮兩步到達(dá)節(jié)點(diǎn)的概率，提出一種基于不等概率疊加隨機(jī)游走的重要節(jié)點(diǎn)識(shí)別算法。該方法將Node2 vec[20]中提到的隨機(jī)游走方法2nd order隨機(jī)游走與有疊加效應(yīng)的局部隨機(jī)游走指標(biāo)[18-19]相結(jié)合，考慮節(jié)點(diǎn)之間的相似性，同時(shí)考慮不等概率隨機(jī)游走。2nd order隨機(jī)游走下一步的選擇不再是等概率隨機(jī)的，而是以不等概率進(jìn)行隨機(jī)游走。這里引入不等概率的隨機(jī)游走，考慮有限次的游走步數(shù)、節(jié)點(diǎn)度的信息、節(jié)點(diǎn)之間的相似性作為不等概率隨機(jī)游走的依據(jù)，進(jìn)行無向網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別。

2 不等概率疊加隨機(jī)方法

文中提出的基于不等概率疊加隨機(jī)游走關(guān)鍵點(diǎn)識(shí)別方法主要包括3個(gè)階段，其中2.1節(jié)描述不等概率隨機(jī)游走轉(zhuǎn)移矩陣的構(gòu)建，根據(jù)Jaccard指標(biāo)[19,21]計(jì)算每個(gè)節(jié)點(diǎn)和網(wǎng)絡(luò)中其他節(jié)點(diǎn)的相似性，考慮任意兩個(gè)節(jié)點(diǎn)間有直接連邊，但是無共同鄰居的情況，采用文獻(xiàn)[18]疊加隨機(jī)游走通過相似和衡量節(jié)點(diǎn)重要度提到的節(jié)點(diǎn)度分之鄰接矩陣值來計(jì)算。通過歸一化處理，以此來構(gòu)建概率轉(zhuǎn)移矩陣。2.2節(jié)描述疊加效應(yīng)的局部隨機(jī)游走，根據(jù)有疊加效應(yīng)的局部隨機(jī)游走指標(biāo)[19]，在局部隨機(jī)游走指標(biāo)(local random walk，LRW)[22]的基礎(chǔ)上，將t步及其以前的結(jié)果加總得到疊加效應(yīng)的局部隨機(jī)游走相似性。這種方法可以增大鄰近目標(biāo)節(jié)點(diǎn)的點(diǎn)與目標(biāo)節(jié)點(diǎn)相連的機(jī)會(huì)。2.3節(jié)基于相似和的疊加隨機(jī)游走[18]，根據(jù)疊加效應(yīng)的局部隨機(jī)游走指標(biāo)，累加各行相似度，從而根據(jù)對(duì)應(yīng)節(jié)點(diǎn)的累加相似和進(jìn)行重要節(jié)點(diǎn)識(shí)別。

2.1 構(gòu)建不等概率隨機(jī)游走轉(zhuǎn)移矩陣

隨機(jī)游走(random walk)指基于過去的表現(xiàn)，無法預(yù)測(cè)將來的發(fā)展步驟和方向，下一步的選擇是隨機(jī)的，一般來講，節(jié)點(diǎn)通過存在邊到達(dá)相鄰節(jié)點(diǎn)的概率是相同的，到達(dá)非鄰居節(jié)點(diǎn)的概率是0，即等概率的隨機(jī)選擇到達(dá)存在邊的節(jié)點(diǎn)。

但實(shí)際中，從一個(gè)節(jié)點(diǎn)到其他鄰居節(jié)點(diǎn)的概率不是均勻隨機(jī)的，而是有偏的，所以文中提出基于不等概率進(jìn)行隨機(jī)游走，采用Jaccard指標(biāo)衡量網(wǎng)絡(luò)中節(jié)點(diǎn)之間的相似性，這里不僅考慮了存在邊的鄰居節(jié)點(diǎn)，同時(shí)也考慮了部分非鄰居節(jié)點(diǎn)，即兩步轉(zhuǎn)移能夠到達(dá)的節(jié)點(diǎn)。同時(shí)對(duì)于節(jié)點(diǎn)間存在直接連邊，但是兩個(gè)節(jié)點(diǎn)沒有共同鄰居，造成的Jaccard指標(biāo)衡量相似性不足的問題，文中基于文獻(xiàn)[18]考慮節(jié)點(diǎn)度的信息，作為相鄰節(jié)點(diǎn)間轉(zhuǎn)移概率。

將一個(gè)具體網(wǎng)絡(luò)抽象為一個(gè)由點(diǎn)集V和邊集E組成的圖G=(V,E)。頂點(diǎn)數(shù)記為N=|V|，邊數(shù)記為M=|E|。兩種常見的表示圖的基本結(jié)構(gòu)是鄰接矩陣(adjacency matrix)和鄰接表(adjacency list)。文中將原始數(shù)據(jù)轉(zhuǎn)化為鄰接矩陣，圖G的鄰接矩陣A=(aij)N×N是一個(gè)N階方陣，第i行第j列上的元素aij定義[1]如下：

無權(quán)無向圖：

(1)

設(shè)置初始狀態(tài)，將一個(gè)walker放置在無向無權(quán)圖G任意節(jié)點(diǎn)i，構(gòu)造隨機(jī)游走模型，walker每一步根據(jù)節(jié)點(diǎn)之間相似性，以不等概率p到達(dá)鄰居節(jié)點(diǎn)，同時(shí)，walker以p到達(dá)兩步轉(zhuǎn)移節(jié)點(diǎn)。游走的每一步方向都與已經(jīng)發(fā)生的事件無關(guān)，walker經(jīng)過的路線是一條馬爾可夫鏈。

算法主要步驟如下：

(1)使用鄰接矩陣表示圖的基本結(jié)構(gòu)，得到每個(gè)節(jié)點(diǎn)的度信息;

(2)使用Jaccard指標(biāo)計(jì)算節(jié)點(diǎn)相似性，兩節(jié)點(diǎn)直接相連，沒有共同鄰居利用節(jié)點(diǎn)度信息進(jìn)行計(jì)算；Jaccard指標(biāo)是在共同鄰居的基礎(chǔ)上考慮兩端節(jié)點(diǎn)度的影響，提出的衡量節(jié)點(diǎn)相似性指標(biāo)。

(2)

對(duì)于節(jié)點(diǎn)vx，鄰居集合為Γ(x)，sxy為節(jié)點(diǎn)vx，vy的相似性。

(3)

(4)

2.2 基于疊加效應(yīng)的局部隨機(jī)游走

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

(5)

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

(6)

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

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

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

公式如下所示：

(7)

算法流程如圖1所示。

圖1 算法流程

3 實(shí)驗(yàn)結(jié)果與分析

3.1 SIR傳播模型

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

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)镽移除狀態(tài)，不再具有感染能力和易感特性。

3.2 Kendall tau距離

Kendall tau距離[3]計(jì)算兩個(gè)排序列表之間成對(duì)分歧數(shù)量，即兩個(gè)完成列表σ和τ，K(σ,τ)表示兩個(gè)列表之間的差異性:

K(σ,τ)=

|{(i,j):iτ(j)}|

(8)

例：σ={1,2,3,4}，τ={1,3,2,4}，σ列表與τ列表二元組集合如圖2所示。

二元組σ(1,2)(1,3)(1,4)(2,3)(2,4)(3,4)τ(1,3)(1,2)(1,4)(3,2)(3,4)(2,4)K000100K=1,K'=1-2*1/4*3=0.833

3.3 仿真實(shí)驗(yàn)

根據(jù)上述分析，為了驗(yàn)證文中提出的基于不等概率疊加隨機(jī)游走關(guān)鍵點(diǎn)識(shí)別方法的有效性，對(duì)9/11恐怖襲擊網(wǎng)絡(luò)[24]、科研合作網(wǎng)[25]、USAir97數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，使用Python語(yǔ)言對(duì)算法進(jìn)行實(shí)現(xiàn)，并與度中心性、介數(shù)中心性、接近中心性、等概率疊加隨機(jī)游走方法進(jìn)行比較；對(duì)3個(gè)數(shù)據(jù)集基于SIR模型計(jì)算標(biāo)準(zhǔn)排序結(jié)果，計(jì)算各中心性算法與SIR的Kendall tau距離的差異；分析算法的時(shí)間復(fù)雜度。表1給出了這3個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)統(tǒng)計(jì)特征,其中n表示節(jié)點(diǎn)數(shù)，m表示邊數(shù)，表示節(jié)點(diǎn)平均度，kmax表示節(jié)點(diǎn)最大度，表示網(wǎng)絡(luò)節(jié)點(diǎn)間最短路徑平均數(shù)，C表示聚類系數(shù)，用來評(píng)估節(jié)點(diǎn)聚集成團(tuán)的集聚程度；R表示同配系數(shù)，用來反映鄰接節(jié)點(diǎn)間的度相關(guān)性；H表示異質(zhì)系數(shù)，衡量網(wǎng)絡(luò)中節(jié)點(diǎn)度分布的異質(zhì)性[1,26]?？梢钥闯?個(gè)網(wǎng)絡(luò)具有明顯的小世界性，即高聚類系數(shù)和短的平均最短路徑長(zhǎng)度，同時(shí)USAir97擁有明顯大度節(jié)點(diǎn)且具有高異質(zhì)性，因此具有無標(biāo)度網(wǎng)絡(luò)的特征。

表1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的統(tǒng)計(jì)特征

9/11恐怖襲擊是伊斯蘭恐怖組織在美國(guó)發(fā)動(dòng)的四次有組織的恐怖襲擊，19名恐怖分子劫持四架客機(jī)，該無向網(wǎng)絡(luò)結(jié)構(gòu)共包含62個(gè)節(jié)點(diǎn)，148條邊，每個(gè)節(jié)點(diǎn)代表一名恐怖分子，包含劫持客機(jī)的19名恐怖分子及其同謀者。節(jié)點(diǎn)之間的邊代表恐怖分子之間的聯(lián)系。網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示，其中4次劫機(jī)行動(dòng)中所在飛機(jī)的恐怖分子編號(hào)為1-19(A11:1-2-3-4-5(飛行員)、UA175:5-6-7-8(飛行員)-9-10、AA77:11-12-13(飛行員)-14-15)、UA93:16-17-18(飛行員)-19[16]，利用文中提出的算法，得到如圖4所示的節(jié)點(diǎn)重要度相似和排名，與介數(shù)中心性、度中心性、接近中心性指標(biāo)、等概率疊加隨機(jī)游走比較，結(jié)果如表2所示。

在四次恐怖劫持中，不等概率疊加隨機(jī)游走識(shí)別同節(jié)點(diǎn)度、接近中心性指標(biāo)、等概率疊加均識(shí)別出3名飛行員(5、8、13)，節(jié)點(diǎn)介數(shù)排序識(shí)別出1名，飛行員需要花費(fèi)更多的資源培養(yǎng)，在劫持客機(jī)中是重要人員。上述算法在識(shí)別出的Top10節(jié)點(diǎn)中，度中心性可以識(shí)別出19名直接參與劫機(jī)的8名成員，其他方法次之；在Top15的節(jié)點(diǎn)中，度中心性、接近中心性和不等概率疊加隨機(jī)游走均識(shí)別出19名直接參與劫機(jī)的10名成員，高于介數(shù)中心性、等概率疊加隨機(jī)游走識(shí)別出的節(jié)點(diǎn)個(gè)數(shù)；Top19節(jié)點(diǎn)中，基于不等概率疊加隨機(jī)游走可以識(shí)別出19名直接參與劫機(jī)的14名成員，其他方法次之。從表4可知，文中提出的方法與標(biāo)準(zhǔn)排序結(jié)果相似性最大，顯著提高了排序精度。

圖4 恐怖襲擊網(wǎng)絡(luò)重要度排名Top19的節(jié)點(diǎn)相似和

表2 節(jié)點(diǎn)重要度比較(1)

續(xù)表2

科研合作網(wǎng)絡(luò)中網(wǎng)絡(luò)的節(jié)點(diǎn)表示曾在網(wǎng)絡(luò)科學(xué)領(lǐng)域發(fā)表過論文的科學(xué)家，連邊表示合作關(guān)系。文中考慮無向無權(quán)網(wǎng)絡(luò)，此數(shù)據(jù)集包含1 589個(gè)節(jié)點(diǎn)，2 742條邊，其中128個(gè)孤立節(jié)點(diǎn)，共包含268個(gè)連通集，文中提取極大連通子圖包含379個(gè)節(jié)點(diǎn)，974條邊。采用基于不等概率疊加隨機(jī)游走關(guān)鍵點(diǎn)識(shí)別算法選取重要性排名前5%的18個(gè)節(jié)點(diǎn)與度中心性、介數(shù)中心性、接近中心性、等概率疊加隨機(jī)游走方法進(jìn)行比較，結(jié)果如表3所示，文中提出的算法能夠通過Top5%的節(jié)點(diǎn)兩步轉(zhuǎn)移覆蓋節(jié)點(diǎn)率85%，低于介數(shù)中心性排序方法，高于節(jié)點(diǎn)度中心性、接近中心性和等概率疊加隨機(jī)游走方法。如表5所示，文中方法排序結(jié)果與標(biāo)準(zhǔn)排序之間相似性次于度中心性，高于等概率疊加隨機(jī)游走排序結(jié)果，能夠有效地識(shí)別出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。

USAir97網(wǎng)絡(luò)節(jié)點(diǎn)表示機(jī)場(chǎng)，邊表示航空路線，該數(shù)據(jù)集包含332個(gè)節(jié)點(diǎn)，2 126條邊，通過中心性算法找到交通通暢性影響較大的機(jī)場(chǎng)，進(jìn)行重點(diǎn)維護(hù)。表3通過比較不同中心性方法得到的Top10節(jié)點(diǎn)，不等概率疊加隨機(jī)游走方法與其他中心性方法得到Top10的差異較小，與度中心性識(shí)別重要節(jié)點(diǎn)相同，介數(shù)中心性差異為4個(gè)，與接近中心性差異為3個(gè)，等概率疊加隨機(jī)游走方法差異為1個(gè)。從表4可知，文中方法與SIR模型之間Kendall tau距離相似性明顯高于其他中心性方法，證明了該方法的有效性，排序精度高于其他中心性方法。

表3 節(jié)點(diǎn)重要度比較(2)

表4 USAir97節(jié)點(diǎn)重要度比較

表5 各中心性算法與SIR模型Kendall tau

對(duì)比分析各算法時(shí)間復(fù)雜度，度中心性算法時(shí)間復(fù)雜度為O(n)，介數(shù)中心性時(shí)間復(fù)雜度為O(n3)，接近中心性、等概率疊加隨機(jī)游走，文中算法時(shí)間復(fù)雜度為O(n2)。文中算法在時(shí)間復(fù)雜度一致的情況下，較等概率疊加隨機(jī)游走方法關(guān)鍵點(diǎn)識(shí)別的準(zhǔn)確性有很大提高。

4 結(jié)束語(yǔ)

針對(duì)復(fù)雜網(wǎng)絡(luò)中關(guān)鍵點(diǎn)識(shí)別問題，提出了一種基于不等概率疊加隨機(jī)游走的評(píng)估方法，引入Jaccard相似性指標(biāo)進(jìn)行不等概率隨機(jī)游走，結(jié)合疊加游走計(jì)算相似和在無向網(wǎng)絡(luò)中進(jìn)行關(guān)鍵點(diǎn)識(shí)別，綜合考慮節(jié)點(diǎn)間的相似性、兩步轉(zhuǎn)移到達(dá)節(jié)點(diǎn)、節(jié)點(diǎn)度信息及網(wǎng)絡(luò)中所處位置等信息。實(shí)驗(yàn)證明，基于不等概率疊加隨機(jī)游走相似和在不增加時(shí)間復(fù)雜度的情況下，可以較高精度有效地識(shí)別關(guān)鍵節(jié)點(diǎn)。綜合實(shí)際網(wǎng)絡(luò)特點(diǎn)，不等概率隨機(jī)游走更好地考慮了隨機(jī)游走特點(diǎn)。在一定程度上說明不等概率隨機(jī)游走在無向網(wǎng)絡(luò)關(guān)鍵點(diǎn)識(shí)別是有效的，下一步是將不等概率隨機(jī)游走與點(diǎn)權(quán)相結(jié)合，并將其擴(kuò)展到有向加權(quán)網(wǎng)絡(luò)，進(jìn)行更深入研究。