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

（1天津電子信息職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)與軟件技術(shù)系，天津 300350；2北京聯(lián)合大學(xué) 信息服務(wù)重點(diǎn)實(shí)驗(yàn)室，北京 100101；3天津職業(yè)技術(shù)師范大學(xué) 信息技術(shù)工程學(xué)院，天津 300222）

0 引 言

在電力交通、社交、生物、政治經(jīng)濟(jì)等領(lǐng)域，復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別具有實(shí)際應(yīng)用意義。如：復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別，可以在電力交通網(wǎng)絡(luò)中挖掘樞紐節(jié)點(diǎn)，進(jìn)行重點(diǎn)保護(hù)，達(dá)到降低經(jīng)濟(jì)風(fēng)險(xiǎn)的目的；在社交網(wǎng)絡(luò)中最有影響力的人，能夠被準(zhǔn)確的挖掘出來(lái)，使廣告效益得到最大化的同時(shí)，可以有助于流言傳播的控制；在蛋白質(zhì)網(wǎng)絡(luò)中可以對(duì)關(guān)鍵蛋白質(zhì)進(jìn)行挖掘，這些蛋白質(zhì)在機(jī)體再生和生存時(shí)是不能或缺的；在生物網(wǎng)絡(luò)中，為醫(yī)藥發(fā)展提供有價(jià)值的理論和方法。

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

綜上所述，本文在文獻(xiàn)［8］的基礎(chǔ)上進(jìn)行擴(kuò)展研究，結(jié)合鄰居節(jié)點(diǎn)的度（出度、入度）信息，在無(wú)向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)中考慮信息傳播的傾向性，利用隨機(jī)游走首次可達(dá)時(shí)間構(gòu)建轉(zhuǎn)移概率矩陣，用以識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。

1 相關(guān)概念

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

1.2 隨機(jī)游走

隨機(jī)游走是一個(gè)很有用的工具，借助這個(gè)工具可以對(duì)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行研究；有時(shí)也將隨機(jī)游走模型稱(chēng)為布朗運(yùn)動(dòng)，其是一種理想的數(shù)學(xué)狀態(tài)。隨機(jī)游走可以理解為無(wú)法基于過(guò)去的行為對(duì)后續(xù)的發(fā)展步驟和方向進(jìn)行預(yù)測(cè)。假設(shè)當(dāng)前節(jié)點(diǎn)有4個(gè)鄰居節(jié)點(diǎn)，該節(jié)點(diǎn)向其周?chē)従庸?jié)點(diǎn)的轉(zhuǎn)移概率均為1／4，這是一種無(wú)限制的等概率隨機(jī)游走。若將節(jié)點(diǎn)之間轉(zhuǎn)移的傾向性考慮進(jìn)來(lái)，就成為了一種無(wú)限制的有偏隨機(jī)游走。

1.3 關(guān)鍵節(jié)點(diǎn)識(shí)別算法

根據(jù)網(wǎng)絡(luò)是否具有方向性，將關(guān)鍵節(jié)點(diǎn)識(shí)別算法應(yīng)用的網(wǎng)絡(luò)類(lèi)型劃分為無(wú)向與有向兩種。在無(wú)向網(wǎng)絡(luò)中，衡量節(jié)點(diǎn)的重要性，主要基于鄰居節(jié)點(diǎn)的信息和路徑；有向網(wǎng)絡(luò)中主要通過(guò)迭代尋優(yōu)的方法，改進(jìn)PageRank算法，利用節(jié)點(diǎn)的點(diǎn)權(quán)信息擴(kuò)展到加權(quán)網(wǎng)絡(luò)，以及將多屬性進(jìn)行融合，結(jié)合局部信息和全局信息進(jìn)行關(guān)鍵節(jié)點(diǎn)識(shí)別。

1.3.1 無(wú)向網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別

度中心性（Degree Centrality）考慮節(jié)點(diǎn)的局部信息，認(rèn)為節(jié)點(diǎn)的重要性取決于中心性，其高低取決于節(jié)點(diǎn)度的值。在無(wú)向圖中，公式（1）為節(jié)點(diǎn)的度中心性：

式中，為節(jié)點(diǎn)總個(gè)數(shù)，（）為v的度中心性值。

介數(shù)中心性（Betweenness Centrality）方法，對(duì)節(jié)點(diǎn)的全局信息進(jìn)行考慮。認(rèn)為信息傳播時(shí)，經(jīng)過(guò)的是最短路徑?？坍?huà)節(jié)點(diǎn)的重要性時(shí)，采用每個(gè)節(jié)點(diǎn)的最短路徑數(shù)目。但該節(jié)點(diǎn)不一定是網(wǎng)絡(luò)中度最大或者是網(wǎng)絡(luò)的拓?fù)渲行?。公式?）為v的介數(shù)中心性：

式中，n（）為經(jīng)過(guò)v的v和v之間的最短路徑數(shù)；n為v和v之間的最短路徑總數(shù)；（）為v的介數(shù)中心性值。

接近中心性（Closeness Centrality）是衡量節(jié)點(diǎn)重要性指標(biāo)時(shí)的最短路徑。借助網(wǎng)絡(luò)對(duì)其它節(jié)點(diǎn)施加影響的能力來(lái)反映節(jié)點(diǎn)，反映網(wǎng)絡(luò)的全局結(jié)構(gòu)，該方法只能應(yīng)用于連通網(wǎng)絡(luò)中。v的接近中心性如公式（3）：

式中：（）為節(jié)點(diǎn)的接近中心性值。

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

PageRank是一種可以按照重要性對(duì)網(wǎng)頁(yè)排序的方法。一個(gè)頁(yè)面是否質(zhì)量高，在于其輸入是否有很多高質(zhì)量的頁(yè)面。也就是說(shuō)如果有很多概率比較大的節(jié)點(diǎn)指向同一個(gè)節(jié)點(diǎn)，則通過(guò)某個(gè)節(jié)點(diǎn)到達(dá)該節(jié)點(diǎn)的概率也會(huì)高。為了使懸掛節(jié)點(diǎn)的問(wèn)題得以解決，PageRank算法中每一個(gè)節(jié)點(diǎn)均以一定的幾率跳轉(zhuǎn)到網(wǎng)絡(luò)中的任一節(jié)點(diǎn)，經(jīng)過(guò)不斷迭代，使每個(gè)節(jié)點(diǎn)的值趨于穩(wěn)定，如公式（4）：

式中：P為節(jié)點(diǎn)的值，1是跳轉(zhuǎn)概率，也稱(chēng)阻尼系數(shù)，通常085。

LeaderRank在解決出度為0的懸掛節(jié)點(diǎn)問(wèn)題時(shí)，添加了一個(gè)虛擬背景節(jié)點(diǎn)，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)與其兩兩雙向連接，當(dāng)?shù)_(dá)到穩(wěn)定，將虛擬背景節(jié)點(diǎn)的權(quán)值平均分配給每一個(gè)節(jié)點(diǎn)。該指標(biāo)值與節(jié)點(diǎn)重要性成正比。如公式（5）：

其中，t表示穩(wěn)態(tài)時(shí)刻。

Pro-PageRank方法是在節(jié)點(diǎn)轉(zhuǎn)移過(guò)程中，更傾向沿著權(quán)重大的邊游走。邊的權(quán)重通過(guò)出度節(jié)點(diǎn)的入度鄰居信息衡量。即節(jié)點(diǎn)轉(zhuǎn)移時(shí)更傾向于沿著入度大的節(jié)點(diǎn)進(jìn)行，如公式（6）：

DPRank方法考慮兩步轉(zhuǎn)移節(jié)點(diǎn)信息，節(jié)點(diǎn)更傾向于出度大的節(jié)點(diǎn)轉(zhuǎn)移。DP方法構(gòu)建的轉(zhuǎn)移概率矩陣如公式（7）：

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

1.4.1 Kendall tau距離

Kendall tau距離用來(lái)計(jì)算兩個(gè)排序列表之間成對(duì)分歧數(shù)量，即兩個(gè)完整列表和，（，）表示兩個(gè)列表之間的差異性。

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

將其用于比較一個(gè)序列與另一個(gè)類(lèi)似標(biāo)準(zhǔn)答案的排序序列的相似性，得出排序序列有效性，K值與兩個(gè)列表之間相似性成正比。列表與列表計(jì)算Kendall tau距離相似值的二元組集合，表1中分別列出列表的所有二元組組合。當(dāng)（）（）且（）（）或者（）（）且（）（）時(shí)1，否則0。

例：｛1，2，3，4｝，｛1，3，2，4｝，其中表示標(biāo)準(zhǔn)序列。

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

由上表可知值，進(jìn)而得到兩個(gè)列表之間的相似性：K＝12?14?30833

1.4.2 SIR傳播模型

本文使用SIR傳播模型，模擬信息在網(wǎng)絡(luò)中的傳播過(guò)程，用于表示節(jié)點(diǎn)的傳播能力。在典型的傳染病模型中，可將個(gè)節(jié)點(diǎn)的狀態(tài)分為如下3類(lèi)：

（1）（易染狀態(tài)）：在初始條件下將所有節(jié)點(diǎn)均定義為該狀態(tài)，該節(jié)點(diǎn)被鄰居節(jié)點(diǎn)感染的概率為；

（2）（感染狀態(tài)）：說(shuō)明該節(jié)點(diǎn)已經(jīng)感染某種病毒，已成為傳染源，感染其直接易感鄰居節(jié)點(diǎn)的概率為；

（3）（移除狀態(tài)）：感染狀態(tài)節(jié)點(diǎn)以概率將鄰居易感節(jié)點(diǎn)轉(zhuǎn)變?yōu)楦腥緺顟B(tài)后，以概率變?yōu)橐瞥隣顟B(tài)，不再具有感染能力和易感特性。

本文采用SIR為多源感染模型，初始時(shí)刻假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)為個(gè)，其余均為個(gè)體。一個(gè)單位時(shí)間內(nèi)，所有處于節(jié)點(diǎn)以概率將其周?chē)従庸?jié)點(diǎn)感染之后，以值為1的概率轉(zhuǎn)變?yōu)?，在不存在易感?jié)點(diǎn)時(shí)達(dá)到穩(wěn)定狀態(tài)。此時(shí)對(duì)處于的節(jié)點(diǎn)個(gè)數(shù)進(jìn)行統(tǒng)計(jì)，用于衡量初始感染狀態(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í)行以上操作，節(jié)點(diǎn)傳播能力的大小即為網(wǎng)絡(luò)中節(jié)點(diǎn)的重要度。

2 有偏隨機(jī)游走改進(jìn)吸收中心性算法

基于網(wǎng)絡(luò)中的隨機(jī)游走原理，利用到達(dá)吸收節(jié)點(diǎn)時(shí)間提出的吸收中心性方法，由于其在研究隨機(jī)游走機(jī)制時(shí)，僅考慮理想狀態(tài)下的等概率隨機(jī)游走，并沒(méi)有考慮網(wǎng)絡(luò)中信息流傳播的復(fù)雜性問(wèn)題。針對(duì)于此，本文將信息流在隨機(jī)游走時(shí)向節(jié)點(diǎn)轉(zhuǎn)移的概率納入研究。在無(wú)向網(wǎng)絡(luò)中，節(jié)點(diǎn)信息傾向于度大的節(jié)點(diǎn)轉(zhuǎn)移；在有向網(wǎng)絡(luò)中，節(jié)點(diǎn)的轉(zhuǎn)移分別傾向于沿著出度、入度大的節(jié)點(diǎn)，將節(jié)點(diǎn)的重要性進(jìn)行分析對(duì)比。

2.1 算法原理

吸收中心性方法（AS）是一種隨機(jī)游走機(jī)制，這種機(jī)制是基于網(wǎng)絡(luò)中等概率的，是利用網(wǎng)絡(luò)中節(jié)點(diǎn)的吸收過(guò)程提出的一種識(shí)別重要節(jié)點(diǎn)的方法。吸收節(jié)點(diǎn)是在網(wǎng)絡(luò)中任意選擇一個(gè)節(jié)點(diǎn)，對(duì)網(wǎng)絡(luò)中其他節(jié)點(diǎn)等概率的隨機(jī)游走到節(jié)點(diǎn)的首次到達(dá)時(shí)間進(jìn)行計(jì)算。該方法采用信息流的效率評(píng)估標(biāo)準(zhǔn)是首次到達(dá)時(shí)間，該節(jié)點(diǎn)的重要性衡量指標(biāo)，是網(wǎng)絡(luò)中其它節(jié)點(diǎn)到吸收節(jié)點(diǎn)的平均首次到達(dá)時(shí)間。平均吸收時(shí)間越短，其它節(jié)點(diǎn)到該節(jié)點(diǎn)的距離就越小，節(jié)點(diǎn)越重要。算法公式（9）：

本文提出對(duì)算法的改進(jìn)工作，是在無(wú)向網(wǎng)絡(luò)中根據(jù)鄰居節(jié)點(diǎn)的度信息重新設(shè)置邊權(quán)。鄰居節(jié)點(diǎn)的度越大，信息越傾向于向該方向進(jìn)行轉(zhuǎn)移，為此提出了_算法；在有向網(wǎng)絡(luò)中，基于鄰居節(jié)點(diǎn)的出度和入度信息，分別提出了_、_算法。

無(wú)向網(wǎng)絡(luò)重新構(gòu)建轉(zhuǎn)移概率矩陣，采用文獻(xiàn)［8］提出的設(shè)置吸收節(jié)點(diǎn)的方法，衡量節(jié)點(diǎn)重要性，定義為_(kāi)：

式中：()為的鄰居節(jié)點(diǎn)集合；P為轉(zhuǎn)移概率矩陣的值；W為節(jié)點(diǎn)、之間邊的權(quán)值。

在有向網(wǎng)絡(luò)中，本文定義的_D中心性指標(biāo)中節(jié)點(diǎn)間的轉(zhuǎn)移概率矩陣如式（11）：

考慮網(wǎng)絡(luò)節(jié)點(diǎn)的方向性，該指標(biāo)中存在設(shè)置的吸收節(jié)點(diǎn)。由于吸收節(jié)點(diǎn)和出度鄰居節(jié)點(diǎn)間存在直接連邊，為避免轉(zhuǎn)移概率為0的情況，采用每個(gè)節(jié)點(diǎn)的出度均加1，同時(shí)避免了分母為0的問(wèn)題。

在有向網(wǎng)絡(luò)中，公式（12）為本文定義的_D中心性指標(biāo)中節(jié)點(diǎn)間的轉(zhuǎn)移概率矩陣。在吸收節(jié)點(diǎn)的鄰居節(jié)點(diǎn)均為邊界節(jié)點(diǎn)時(shí)，v向每個(gè)鄰居節(jié)點(diǎn)隨機(jī)游走的概率均為1／k，該指標(biāo)等同于等概率的隨機(jī)游走。

為了方便計(jì)算分析，按照最大值，將各節(jié)點(diǎn)的中心性值歸一化處理，如式（13）：

2.2 案例分析

本節(jié)通過(guò)計(jì)算實(shí)例，對(duì)算法的計(jì)算過(guò)程進(jìn)行解釋?zhuān)鐖D1所示。其中包含9個(gè)節(jié)點(diǎn)12條邊的無(wú)向網(wǎng)絡(luò)，假設(shè)吸收節(jié)點(diǎn)為節(jié)點(diǎn)1，將其代入式（9）、式（10），計(jì)算所有節(jié)點(diǎn)有偏隨機(jī)游走到吸收節(jié)點(diǎn)1的首達(dá)時(shí)間。各中心性方法的中心性值見(jiàn)表2。

圖1 案例網(wǎng)絡(luò)Fig.1 Case network

表2 各中心性方法所有節(jié)點(diǎn)的中心性值Tab.2 Centrality values of all nodes in each centrality method

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

根據(jù)上述分析，為驗(yàn)證本文提出基于有偏隨機(jī)游走改進(jìn)的吸收中心性算法（GAS_D、GAS_Dout、GAS_Din），識(shí)別關(guān)鍵點(diǎn)的有效性，對(duì)無(wú)向網(wǎng)絡(luò)（karate、USAir、911terriset、Email）、有向網(wǎng)絡(luò)（Freemans、Organisational、Celegansneural）進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)集的網(wǎng)絡(luò)參數(shù)見(jiàn)表3。

表3中，表示節(jié)點(diǎn)數(shù)；表示邊數(shù)；表示節(jié)點(diǎn)平均度；max表示節(jié)點(diǎn)最大度；表示網(wǎng)絡(luò)節(jié)點(diǎn)間最短路徑平均數(shù)；表示聚類(lèi)系數(shù)，用來(lái)評(píng)估節(jié)點(diǎn)聚集成團(tuán)的集聚程度；表示同配系數(shù)，用來(lái)反映鄰接節(jié)點(diǎn)間的度相關(guān)性；表示異質(zhì)系數(shù)，衡量網(wǎng)絡(luò)中節(jié)點(diǎn)度分布的異質(zhì)性。

實(shí)驗(yàn)環(huán)境為：Intel（R）Core（TM）i3-2367M CPU＠1.40 GHz、4 GB內(nèi)存、Windows7、python3.2.732位，使用Python語(yǔ)言實(shí)現(xiàn)算法。共設(shè)計(jì)3組對(duì)比實(shí)驗(yàn)，對(duì)算法的有效性和準(zhǔn)確性進(jìn)行驗(yàn)證。

實(shí)驗(yàn)內(nèi)容如下：

（1）對(duì)比分析本文提出的改進(jìn)算法與其它中心性算法中心性值的相關(guān)性。單調(diào)性表現(xiàn)越明顯，算法之間的相關(guān)性越好。

（2）采用數(shù)學(xué)計(jì)算，度量Kendall tau距離計(jì)算相關(guān)系數(shù)。以本文提出的改進(jìn)算法為標(biāo)準(zhǔn)，對(duì)該算法與其它方法之間的相似性量化分析，相似性越大說(shuō)明算法越有效。

（3）基于SIR多源傳播感染模型，在不同感染概率下，對(duì)各算法識(shí)別出的TopK節(jié)點(diǎn)在穩(wěn)定狀態(tài)下平均感染的節(jié)點(diǎn)數(shù)進(jìn)行比較。

表3 數(shù)據(jù)集參數(shù)Tab.3 Parameters of datasets

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

在4個(gè)數(shù)據(jù)集中均可以明顯看出，當(dāng)感染概率足夠大的情況下，各方法識(shí)別出的Top結(jié)果在穩(wěn)定狀態(tài)下均可以覆蓋整個(gè)網(wǎng)絡(luò)；各中心性算法識(shí)別出的Top10節(jié)點(diǎn)不同的感染概率∈（0，1］下，達(dá)到穩(wěn)定狀態(tài)的結(jié)果趨勢(shì)一致，沒(méi)有表現(xiàn)出明顯差異，說(shuō)明了算法的有效性；在感染概率0.5左右，911terriset、Netscience數(shù)據(jù)集中，改進(jìn)的GAS_D算法均優(yōu)于改進(jìn)之前的AS算法，感染節(jié)點(diǎn)數(shù)更多，說(shuō)明本文算法的有效性，并且優(yōu)于改進(jìn)之前的算法。

文獻(xiàn)［8］提出的吸收中心性方法并沒(méi)在有向網(wǎng)絡(luò)中進(jìn)行拓展研究，本文將其拓展方法記為ZAS，并與提出的有偏隨機(jī)游走改進(jìn)之后的GAS_Dout、GAS_Din算法，在3個(gè)真實(shí)的網(wǎng)絡(luò)進(jìn)行對(duì)比研究，各算法之間的相關(guān)性及Kendall tau相似性系數(shù)如圖4～圖6所示。在Freeman、Organisational、Celegansneural數(shù)據(jù)集中，ZAS算法識(shí)別結(jié)果更接近于PageRank、LeaderRank；GAS_Din算法識(shí)別結(jié)果更接近于Pro_PageRank算法；GAS_Dout算法識(shí)別結(jié)果更接近于DPRank。在3個(gè)數(shù)據(jù)集下，ZAS、GAS_Din、GAS_Dout分 別 與 PageRank、LeaderRank、Pro_PageRank、DPRank的相似性見(jiàn)表4。

由表4中數(shù)據(jù)可見(jiàn)，ZAS、PageRank、LeaderRank均為等概率的向鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移，而GAS_Din、Pro_PageRank更傾向于向入度大的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移，GAS_Dout、DPRank更傾向于向出度大的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移，故算法之間表現(xiàn)出更強(qiáng)的相關(guān)性。Top10節(jié)點(diǎn)在不同感染概率下達(dá)到穩(wěn)定狀態(tài)下的感染節(jié)點(diǎn)率如圖7所示，各算法識(shí)別結(jié)果的總體趨勢(shì)相同，一定程度說(shuō)明了ZAS、GAS_Din、GAS_Dout算法的有效性，GAS_Dout的識(shí)別結(jié)果也明顯優(yōu)于GAS_Din、ZAS算法，GAS_Dout的準(zhǔn)確性更高。

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

圖2 不同網(wǎng)絡(luò)中GAS_D算法與其它中心性算法的相關(guān)性及Kendall tau相關(guān)系數(shù)Fig.2 Correlation between GAS_D algorithm and other centrality algorithms and Kendall tau correlation coefficient in different networks

圖3 無(wú)向網(wǎng)絡(luò)中各中心性算法識(shí)別出的Top10節(jié)點(diǎn)在不同感染概率下平穩(wěn)狀態(tài)值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算法與其它中心性算法的相關(guān)性及Kendall tau相關(guān)系數(shù)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算法與其它中心性算法的相關(guān)性及Kendall tau相關(guān)系數(shù)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算法與其它中心性算法的相關(guān)性及Kendall tau相關(guān)系數(shù)Fig.6 Correlation between ZAS、GAS_Dout、GAS_Din algorithm and other centrality algorithms and Kendall tau correlation coefficient in Celegansneural

圖7 有向網(wǎng)絡(luò)中各中心性算法識(shí)別出的Top10節(jié)點(diǎn)在不同感染概率下平穩(wěn)狀態(tài)值Fig.7 The stationary state values of top 10 nodes identified by centrality algorithms under different infection probabilities in directed networks

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

本文基于無(wú)向網(wǎng)絡(luò)中等概率的吸收中心性方法，基于節(jié)點(diǎn)的度信息，提出適用于無(wú)向網(wǎng)絡(luò)的GAS_D算法進(jìn)行不等概率有偏的關(guān)鍵節(jié)點(diǎn)識(shí)別，并與節(jié)點(diǎn)的出度信息結(jié)合，將AS算法拓展到有向網(wǎng)絡(luò)，結(jié)合鄰居節(jié)點(diǎn)的出度和入度信息，提出GAS_Dout、GAS_Din算法。通過(guò)真實(shí)的無(wú)向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)設(shè)計(jì)仿真實(shí)驗(yàn)證明：在無(wú)向網(wǎng)絡(luò)中，本文提出的考慮現(xiàn)實(shí)網(wǎng)絡(luò)中信息轉(zhuǎn)移傾向性的改進(jìn)算法優(yōu)于改進(jìn)之前的算法；在有向網(wǎng)絡(luò)中，考慮鄰居節(jié)點(diǎn)的出度節(jié)點(diǎn)信息對(duì)信息的擴(kuò)散更有利，本文算法在有向網(wǎng)絡(luò)中的擴(kuò)展，也解決了PageRank及其改進(jìn)算法的參數(shù)問(wèn)題。后續(xù)工作將邊值的權(quán)重考慮在內(nèi)進(jìn)行進(jìn)一步的拓展研究。