基于網(wǎng)絡拓撲結構的重要節(jié)點發(fā)現(xiàn)算法

鄧曉懿， 楊 陽， 金 淳

(1.華僑大學 工商管理學院，福建 泉州 362021; 2.大連理工大學 系統(tǒng)工程研究所，遼寧 大連 116024)

0 引言

復雜網(wǎng)絡由大量節(jié)點組成，其中重要節(jié)點是少數(shù)能對整個網(wǎng)絡的結構及功能產(chǎn)生深層次影響的特殊節(jié)點。在網(wǎng)絡安全、信息傳播、疾病防控、犯罪預防、交通及電力傳輸?shù)阮I域中，少數(shù)重要節(jié)點的影響可以快速地波及到網(wǎng)絡中大部分節(jié)點狀態(tài)。例如，在internet中，只需攻擊其中5%度大于5的網(wǎng)絡節(jié)點就能阻斷因特網(wǎng)的連通性[1]；美國俄亥俄州克利夫蘭市的電力傳輸故障導致了整個北美電力網(wǎng)絡癱瘓；在全球經(jīng)濟網(wǎng)絡中，控制著40%財富的147家跨國公司數(shù)量不到全球公司總量的1%[2]；在SNS網(wǎng)站(Weibo，Twitter或Facebook)上，少數(shù)具有較強影響力的用戶所發(fā)的信息會很快就會傳遍整個網(wǎng)絡。因此，重要節(jié)點對網(wǎng)絡的結構和功能有著巨大影響, 如何發(fā)現(xiàn)復雜網(wǎng)絡中的重要節(jié)點、并度量其重要性具有重大理論意義和實際應用價值[3,4]。

在復雜網(wǎng)絡中，節(jié)點的重要性依賴于網(wǎng)絡拓撲結構，其常見度量指標有度中心性(Degree Centrality, DC)[5]、介數(shù)中心性(Betweenness Centrality, BC)[6]、接近中心性(Closeness Centrality, CC)[7]、特征向量中心性(Eigenvector Centrality, EC)[8]等。相對其他方法，EC不但蘊含著節(jié)點的特征信息(如重要性、聲望以及地位等)，同時更強調節(jié)點所處的周圍環(huán)境，認為節(jié)點重要性不但取決于其鄰居節(jié)點的數(shù)量，還取決于其鄰居節(jié)點的重要性[9]。換句話說，節(jié)點的EC值即為其所有鄰居的EC值之和，節(jié)點可通過連接其他重要節(jié)點的方式來提升自身重要性，EC值較高的節(jié)點要么和大量一般節(jié)點相連，要么和少量具有較高EC值的節(jié)點相連。因此，EC更適用于描述節(jié)點的長期或者全局影響力，例如在傳染病傳播網(wǎng)絡中，如果節(jié)點EC值越大，那么該節(jié)點很可能距離傳染源很近，或為感染源之一，是需要重點關注或控制的關鍵性節(jié)點。

傳統(tǒng)復雜網(wǎng)絡重要節(jié)點發(fā)現(xiàn)算法可分為局部發(fā)現(xiàn)和全局發(fā)現(xiàn)，局部發(fā)現(xiàn)算法僅考慮節(jié)點自身屬性和其鄰居信息，而全局發(fā)現(xiàn)算法側重衡量節(jié)點在網(wǎng)絡的全局信息。EC算法[8]則是全局發(fā)現(xiàn)算法中的一種代表性算法。由于EC算法思路簡單，復雜度較低，在很多領域中受到極大關注[9]。但是，EC算法將所有節(jié)點歸為一個社區(qū)，并未考慮節(jié)點局部所在社區(qū)的聚集程度，也未利用社區(qū)的結構特征度量節(jié)點的重要性，不能充分滿足重要節(jié)點的發(fā)現(xiàn)要求。針對EC算法的不足，本文提出了可達中心性算法(Accessibility Centrality, AC)。該方法基于網(wǎng)絡拓撲結構來度量節(jié)點之間的影響力，依靠鄰接矩陣傳遞控制路徑長度，強化了節(jié)點的結構性特征；此外，該方法同時考慮了節(jié)點的局部影響力和全局影響力，可彌補EC算法僅基于節(jié)點全局影響力進行計算的不足，可進一步提高重要節(jié)點發(fā)現(xiàn)的效率和準確性。

1 類EC算法分析

EC算法是基于特征向量的節(jié)點發(fā)現(xiàn)中的核心代表算法[10]，是評價復雜網(wǎng)絡節(jié)點影響力的重要算法之一。EC算法、EC改進算法以及變體通常稱為類EC算法，本節(jié)針對類EC算法進行概述分析。

1.1 EC算法概述

EC算法認為網(wǎng)絡中的每個節(jié)點都有一個相對狀態(tài)值，節(jié)點的相對狀態(tài)值受到該節(jié)點的鄰居相對狀態(tài)值的正向反饋，在不斷反饋迭代過程中，節(jié)點相對狀態(tài)值標準化后達到穩(wěn)態(tài)，此時的穩(wěn)態(tài)值就是節(jié)點的EC值。

假設G=(V,E)為一個無向無權網(wǎng)絡，A=(Aij)為其鄰接矩陣，即：

(1)

根據(jù)EC算法定義，設S=[S1,S2,…，SN]T為節(jié)點的相對狀態(tài)，uS=[uS1,uS2,…uSN]T為節(jié)點相對狀態(tài)標準化值，S0=[1,1,…1]T為節(jié)點的初始狀態(tài)值。迭代過程如下：

Step1節(jié)點第一階段狀態(tài)值等于初始階段節(jié)點鄰居狀態(tài)值之和的倍數(shù)，即S1=AS0/λ1；

Step2節(jié)點第二階段狀態(tài)值等于第一階段節(jié)點鄰居狀態(tài)值之和的倍數(shù)，即S2=AS1/λ1；

……

StepN節(jié)點第N階段狀態(tài)值等于第N-1階段節(jié)點鄰居狀態(tài)值之和的倍數(shù)，即SN=ASN-1/λ1。其中，λ1為一個比例常數(shù)，多次迭代直到uSN=uSN-1為止，uSN等于EC向量。從上述過程可看出，EC算法更適合評價節(jié)點長期影響力。

1.2 相關研究概述

在EC算法改進方面，Redner[11]將EC算法應用拓展到加權EC算法，并將加權EC應用到引文網(wǎng)絡的搜索結果排序。Ilya[12]提出主分量中心性算法，利用鄰接矩陣的前p個特征向量來計算節(jié)點的中心性，解決了EC算法認為重要節(jié)點集中于一個社團的缺陷。李靜茹等[13]提出基于鏈接強度矩陣的加權中心性度量法，將PCC應用于加權社交網(wǎng)絡，在傳播效率、魯棒性、容錯性等方面比加權EC算法更優(yōu)。Martin等[14]利用非回溯矩陣解決了EC算法局部轉移問題，并適用于大型復雜多社區(qū)結構網(wǎng)絡。另一面，對于提高EC算法效率，Poulin等[15]提出在EC算法鄰居節(jié)點每次正向反饋時加入節(jié)點自身的狀態(tài)值，提高了收斂速度。Kohlschütter等[16]提出并行算法計算鄰接矩陣的特征向量和特征值，提高了運行速度。

在EC算法變體方面，網(wǎng)頁排序領域的PageRank算法[17]通過模擬用戶上網(wǎng)瀏覽網(wǎng)頁過程，沿著訪問路徑將節(jié)點狀態(tài)值平均分配給其他頁面，使節(jié)點網(wǎng)頁得到一個全局的重要性排序，但當網(wǎng)絡不連通時，節(jié)點排序結果不唯一?；赑ageRank算法，LeaderRank算法[18]在原網(wǎng)絡中加入一個背景節(jié)點(Ground Node)，并將這個節(jié)點和網(wǎng)絡中所有節(jié)點相連，保證了網(wǎng)頁的強連通性，更能識別網(wǎng)絡中有影響力的節(jié)點。Li等[19]則認為入度較大的節(jié)點在遍歷過程中被訪問的概率應該更高，利用背景節(jié)點和其他所有節(jié)點的鏈接賦予不同權重提升了LeaderRank算法效果。上述研究都將節(jié)點視為同質節(jié)點，而Kleinberg[20]則認為節(jié)點重要性不應該依賴于單一指標，應采用權威值和樞紐值兩個不同指標對網(wǎng)絡節(jié)點進行排序，每個指標同樣依賴鄰居指標的貢獻。Benzi等[21]將有向網(wǎng)絡映射成無向二分網(wǎng)絡，運用矩陣函數(shù)計算節(jié)點權威值和樞紐值。

上述研究針對EC算法的不足，做了相應改進或優(yōu)化，在一定程度上提高了EC算法的效率，并擴大了其應用范圍。但是，其中大部分研究都是將鄰居作為傳播路徑，應用鄰居的正向反饋進行節(jié)點影響力評估，過于注重節(jié)點參數(shù)的收斂性，忽略了網(wǎng)絡拓撲結構對節(jié)點影響力的影響，同時也未討論反饋不同階段中節(jié)點影響力變化情況。

2 基于網(wǎng)絡拓撲結構的可達中心性算法

2.1 算法核心思想

在現(xiàn)實社交網(wǎng)絡中，如果節(jié)點A和B是朋友，那么節(jié)點A的另一個朋友節(jié)點C也可能是節(jié)點B的朋友，由此形成一個三角形關系結構。此時，節(jié)點的結構特性可用集聚系數(shù)(Clustering Coefficient)表示，若節(jié)點鄰居之間三角形關系結構的邊越多，節(jié)點的集聚系數(shù)越大。EC算法則可看作信息在網(wǎng)絡中進行無損失傳播的模擬過程，并依靠鄰居節(jié)點重要度測量節(jié)點影響力。事實上，在可達的情況下，節(jié)點可以對其他任意節(jié)點貢獻重要度。此外，節(jié)點所在社區(qū)的結構越密集，節(jié)點信息的傳播路徑越多，其影響力越大；同時，傳播過程中會出現(xiàn)信息丟失，信息丟失程度與路徑長度成正比。

本文提出基于網(wǎng)絡拓撲結構的可達中心性算法(Accessibility Centrality, AC)，從節(jié)點結構特征和網(wǎng)絡的傳播特性兩個方面對EC算法進行改進：首先，根據(jù)網(wǎng)絡的節(jié)點結構特征，利用鄰接矩陣計算網(wǎng)絡中不同路徑長度下的節(jié)點間影響力；然后，根據(jù)節(jié)點間影響力得到不同路徑長度下的節(jié)點影響力；最后，根據(jù)網(wǎng)絡的信息傳播特性得到最終節(jié)點的影響評價指標AC值。AC算法框架如圖1所示。

圖1 AC算法框架

設無向無權網(wǎng)絡G=(V,E)，節(jié)點數(shù)N，鄰接矩陣為A=A(i,j)，G中節(jié)點間存在影響力F(i,j)。若節(jié)點i能影響節(jié)點j，從網(wǎng)絡拓撲結構上就存在著連接節(jié)點i到節(jié)點j的路徑。相同路徑長度下節(jié)點i到達節(jié)點j的路徑數(shù)越多，節(jié)點i對節(jié)點j的影響力越大。為研究不同路徑長度下節(jié)點影響力變化情況，本文在接下來的章節(jié)分別對不同路徑長度下的節(jié)點間影響力和節(jié)點整體影響力進行定義并詳細闡述。

2.2 節(jié)點間影響力

為便于理解節(jié)點間影響力，本節(jié)以一個小型無向網(wǎng)絡G為例進行闡述。圖2所示的網(wǎng)絡可看作由兩個大小相等的社區(qū)所構成的網(wǎng)絡，具有10個節(jié)點和13條邊。

圖2 小型無向網(wǎng)絡G示例

在圖2中，網(wǎng)絡G中節(jié)點i1和i6都與4個節(jié)點相連，由于i6所在社團結構更為緊密，顯然i6對i5的影響力F(6,5)大于i1對i5的影響力F(1,5)。當路徑長度為1時，i1和i6到達i5的路徑分別是1→5和6→5；當路徑為2時，i1和i6無法到達i5；當路徑長度為3時，i1和i6到達i5的路徑數(shù)量仍舊相同；當路徑長度為4時，i1無法到達i5，但i6可以通過6→7→10→6→5和6→9→10→6→5兩條不同路徑到達i5，說明隨著路徑長度增加，i6對i5的影響力優(yōu)勢不斷增加。因此，F(xiàn)(6,5)的大小不僅與i6和i5的直接到達路徑數(shù)量直接相關，而且與不同路徑長度下的間接到達路徑數(shù)量有關。

定義1k步路徑節(jié)點間影響力Fk(i,j)：節(jié)點i對節(jié)點j的k步路徑影響力等于節(jié)點i在長度為k的連接路徑下到達節(jié)點j所遍歷的節(jié)點數(shù)量，如公式(2)表示。

(2)

其中，節(jié)點i對j的1步路徑節(jié)點間影響力F1(i,j)=A(i,j)，對于節(jié)點i對j的k步路徑節(jié)點間影響力Fk(i,j)，l為網(wǎng)絡中任意節(jié)點，當Fk-1(i,l)和A(l,j)都不為0時，表示i可繼續(xù)通過節(jié)點l對j施加影響力，F(xiàn)k(i,j)在Fk-1(i,l)的基礎上增加了一個遍歷節(jié)點l。

圖3 節(jié)點uf k值和EC值變化趨勢

由此可見，F(xiàn)k(i,j)不僅考慮了兩兩節(jié)點間的可達路徑數(shù)量，同時還累計了路徑上的節(jié)點個數(shù)，可使處于社區(qū)結構相對緊密的節(jié)點的影響力更大，而處于社區(qū)結構相對稀疏的節(jié)點的影響力更小，最終可使節(jié)點影響力的收斂速度更快，具體詳見圖3。

2.3 節(jié)點整體影響力

定義2k步路徑節(jié)點整體影響力fk(i):節(jié)點i的k步路徑整體影響力等于該節(jié)點到所有節(jié)點(包含其自身)的k步路徑節(jié)點間影響力Fk(i,j)之和，公式表示如下。

(3)

以圖2中網(wǎng)絡G為例，G中10個節(jié)點在1步～6步路徑長度下節(jié)點影響力如表1所示。由表1可知，節(jié)點2、3、4以及節(jié)點7、9的影響力變化一致，這是由于節(jié)點7、9和節(jié)點2、3、4分別處于對稱位置，使得這些節(jié)點在不同路徑長度下到達其他節(jié)點的遍歷路徑長度相同。

表1 節(jié)點k步路徑節(jié)點影響力

為便于比較不同路徑下節(jié)點整體影響力，本文以網(wǎng)絡G中節(jié)點1、2、5、6、7、8、10為例進行說明。節(jié)點fk(i)值和EC(i)變化趨勢如圖3所示，其中，fk(i)按照公式(4)做標準化處理。

(4)

由圖3可知，節(jié)點7、8的ufk差值顯然大于它們的EC差值，其他節(jié)點之間的ufk差值也比EC差值更為明顯。對于節(jié)點1而言，盡管其鄰居較多，但由于其所在社區(qū)結構相對稀疏，造成其ufk值迅速下降，且其在3步路徑長度下的ufk值小于節(jié)點5的ufk值，波動幅度小于EC算法，說明AC算法的收斂速度比EC算法更快。

2.4 節(jié)點影響力評價指標

在得到節(jié)點整體影響力之后，再對每個節(jié)點的長期影響力進行評估。在計算節(jié)點的長期影響力時，為了考慮節(jié)點的全局影響力，EC算法將節(jié)點影響力的最終穩(wěn)定值作為節(jié)點的長期影響力評價指標。為了考慮節(jié)點在所有傳播路徑下的全局影響力，本文認為節(jié)點影響力評價指標和節(jié)點的前k步路徑節(jié)點整體影響力都有一定的比例關系。此外，相關研究[3]表明：節(jié)點影響力的傳播路徑上存在噪音干擾，傳播的影響力大小與路徑長度成反比。

定義3節(jié)點影響力評價指標AC(i)：節(jié)點的影響力評價指標等于標準化的全體k步路徑節(jié)點整體影響力ufk與路徑長度k的比值之和，計算公式如下所示。

(5)

其中，K為任意兩節(jié)點之間不含閉環(huán)的最大可達路徑長度。在G中，當K=15時，根據(jù)公式(5)得到每個節(jié)點的AC值；同時，根據(jù)EC算法得到每個節(jié)點的全局影響力，結果如表2所示。

表2 AC算法和EC算法的節(jié)點影響力計算結果

從表2可以看出，根據(jù)AC算法和EC算法計算出的節(jié)點影響力排序所得到的兩組節(jié)點序列完全一致，進而證明了AC算法具有與EC算法相同的節(jié)點影響力排序有效性。

大量實驗證明，任意兩節(jié)點間不含閉環(huán)的最大可達路徑長度K的大小與網(wǎng)絡的拓撲結構和傳染概率有關，當傳染概率較大時，K通常等于網(wǎng)絡中任意兩個節(jié)點間最短路徑中的最大值(即網(wǎng)絡直徑)，此時可得到節(jié)點影響力的最優(yōu)評價指標，具體詳見4.2節(jié)的K值分析。由于現(xiàn)實世界的網(wǎng)絡具有小世界特性，網(wǎng)絡的K值通常較小，可降低AC算法的計算復雜度。

3 實驗設計與結果分析

為驗證AC算法的有效性以及其在不同集聚度網(wǎng)絡上的性能，本文分別采用Email、Ariport等四種真實網(wǎng)絡數(shù)據(jù)，以及Holme-Kim(HK)聚類系數(shù)可變無標度網(wǎng)絡[22]，并選取EC算法等四種主流重要節(jié)點發(fā)現(xiàn)算法進行對比分析。實驗運行環(huán)境為CPU Intel E5-4650 2.7GHz CPU, 32GB內(nèi)存，Window Server 2008操作系統(tǒng)，Matlab R2014b。

3.1 實驗設計

3.1.1 實驗數(shù)據(jù)

(1)真實網(wǎng)絡數(shù)據(jù)

本文使用四個真實的無向基準網(wǎng)絡數(shù)據(jù)對比驗證AC算法的有效性，四個真實網(wǎng)絡包含文本網(wǎng)絡Word、社交網(wǎng)絡Email、交通運輸網(wǎng)絡Airport以及生物網(wǎng)絡Protein[3]，四個網(wǎng)絡的特征信息如表3所示。

在表3中，最佳感染概率[23]β0=/。當β<β0時，網(wǎng)絡中節(jié)點的影響力不會大規(guī)模地傳播。當β>β0時，節(jié)點的影響力開始在網(wǎng)絡中大規(guī)模傳播。

表3 基準網(wǎng)絡特征信息

(2)人工網(wǎng)絡數(shù)據(jù)

HK網(wǎng)絡模型具有小世界、高聚類、無標度特性，非常接近現(xiàn)實中的社會網(wǎng)絡和生物網(wǎng)絡，可用于分析網(wǎng)絡聚類系數(shù)對AC算法性能的影響[24]。HK模型的生成由一系列參數(shù)控制：N代表節(jié)點數(shù)量，m為每一個新節(jié)點隨機連接邊的數(shù)量，p表示新節(jié)點隨機連接一條邊后再連接一條邊可構成三角形的概率，p越大，網(wǎng)絡的平均集聚系數(shù)越大。本文取N=500，m=3,p∈[0,0.9]且以步長0.1遞增，生成N0至N9共10個網(wǎng)絡。

3.1.2傳染病傳播模型

SIR和SI模型是復雜網(wǎng)絡中用于測試節(jié)點傳播能力的經(jīng)典模型[9]。SIR模型中，節(jié)點可能處于三個狀態(tài)：易感者(Susceptible State, SS)，感染者(Infected State, IS)和恢復者(Recovered State, RS)，而SI模型中節(jié)點只可能處于SS和IS兩種狀態(tài)中的一種。

在仿真初始時刻，待測節(jié)點i為IS節(jié)點，其他節(jié)點為SS節(jié)點，IS節(jié)點以傳染概率β將其的SS鄰居節(jié)點轉換為IS節(jié)點。在SIR中，IS節(jié)點能以恢復率μ轉換成RS節(jié)點，RS節(jié)點不再轉換為IS節(jié)點。若在仿真時間(timespace)未結束前，系統(tǒng)中不存在SS節(jié)點，仿真過程結束。節(jié)點i的傳播影響力如公式(6)所示。

(6)

其中，T表示最大重復仿真次數(shù)，ki(t)等于節(jié)點i在第t次仿真時的影響力傳播值。由上式可得節(jié)點的影響力序列S=[S1,S2,…,SN]。

3.1.3 對比算法及評估函數(shù)

為測試AC算法的性能，本文引入其他四種代表性的重要節(jié)點發(fā)現(xiàn)算法進行比較，分別是度中心性算法 (Degree Centrality, DC)[5]，介數(shù)中心性算法(Betweenness Centrality,BC)[6]，EC算法[8]和LeaderRank算法[18]。

為評估每個算法得到的節(jié)點影響力序列是否與模擬的傳染病模型得到的節(jié)點傳播能力序列一致，本文利用Kendall’s Tau系數(shù)[24]作為評價指標。該系數(shù)通過比較兩段序列：D(例如節(jié)點度序列D=[D1,D2,…，DN])和S序列的一致程度，來評估節(jié)點傳播能力。如果Di>Dj且Si>Sj，或者Di

(7)

其中，τ值越大，兩列序列的一致程度越高。當τ=1時，兩列數(shù)列完全一致；當τ=-1時，兩列數(shù)列完全不同。

3.2 K取值分析和HK模型仿真結果分析

為確定網(wǎng)絡中K的取值，本文以人工網(wǎng)絡N0和N9為研究對象。其中，N0網(wǎng)絡直徑為7，p=0，K∈[1,10]；N9網(wǎng)絡直徑為8，p=0.9，K∈[1,11]。將該實驗結果與SIR模型上的實驗結果進行對比，SIR模型參數(shù)timespace=5，β={0.04，0.06，0.08}，μ=0.05，T=1000。實驗結果分別如圖4和圖5所示。

圖4 K取值分析結果

圖4結果顯示了參數(shù)K對節(jié)點影響力評估指標AC值準確性影響：τ值隨著K值的增加呈現(xiàn)先增加后降低的趨勢，不同傳染概率下均表現(xiàn)一致。隨著傳染概率的升高，τ值的增長逐漸變緩。當β分別等于0.06和0.08時，N0中K=7、N9中K=8時τ值分別達到最優(yōu)。當β=0.04時，可適當降低K的取值以可達到最優(yōu)效果。

圖5 不同集聚系數(shù)條件下AC指標準確性變化

圖5則顯示了不同集聚系數(shù)對節(jié)點AC值準確性的影響：隨著p值的增加，τ值總體呈下降趨勢，但下降幅度較小。該結果表明AC算法能夠更準確地定位集聚系數(shù)較低的網(wǎng)絡，找出其中隱含的集聚效應。相對的，對于平均集聚系數(shù)較高的網(wǎng)絡，AC算法的效果相差不大。

3.3 實驗結果及分析

為保證節(jié)點的傳播能力是有限的，本文在實驗中將傳染概率β設置為相對較小的值，β∈[0.01,0.1]，并以步長0.01遞增。SIR、SI模型參數(shù)μ=0.05，T=1000。AC算法中K值分別對應各網(wǎng)絡的直徑。

3.3.1 AC算法有效性分析

為評估AC算法對節(jié)點影響力的有效性，本文分別在SIR和SI仿真環(huán)境中對比AC與其他四種算法，實驗對比結果分別如圖6和圖7所示。

由圖6可知，在Airport和Protein網(wǎng)絡中，AC算法的性能完全優(yōu)于其他四類算法；在Word網(wǎng)絡中，AC算法在β的可變范圍優(yōu)于EC和DC算法，且當β>0.02時，AC算法優(yōu)于DC和LR算法。在Email網(wǎng)絡中，AC算法在β的可變范圍內(nèi)優(yōu)于EC、LR和DC算法，當β>0.02時，AC算法比其他四種算法更有效。從總體上來看，當β>β0時，AC算法的τ值隨著β增加而增加，這是因為待測節(jié)點的鄰居數(shù)量以及鄰居節(jié)點被影響的概率增加，導致其他節(jié)點的被影響概率也隨之增加，使得節(jié)點影響力的傳播范圍變大。當β<<β0時，節(jié)點影響力的傳播僅發(fā)生在待測節(jié)點周圍，度越大的節(jié)點可影響節(jié)點數(shù)量越多。此時，基于局部發(fā)現(xiàn)的DC算法的τ值較大，優(yōu)于基于全局影響力節(jié)點發(fā)現(xiàn)的EC算法。但隨著β的逐漸增加，DC算法的τ值轉而降低，很快劣于基于節(jié)點長期影響力的EC和AC算法。在相同條件下，AC算法可以在β<<β0時就獲到比EC更優(yōu)的τ值，說明AC算法在較低的傳染概率條件下也能得到有效的節(jié)點影響力評估。此外，AC和EC算法的τ值曲線在Airport網(wǎng)絡中的差異最小，而且Airport網(wǎng)絡的平均集聚系數(shù)遠高于其他三個網(wǎng)絡，進一步證明了AC算法在低集聚系數(shù)網(wǎng)絡上的有效性要優(yōu)于高集聚系數(shù)網(wǎng)絡。從總體上看，ACfigureEC算法。

圖6 五類算法節(jié)點影響力與SIR模型模擬結果對比τ值變化趨勢

圖7 五類算法節(jié)點影響力與SI模型模擬結果對比τ值變化趨勢

通過觀察圖7的4個子圖，可發(fā)現(xiàn)在SI仿真環(huán)境下，AC及其他四種算法的對比效果與圖6中的效果基本一致：在Word和Email數(shù)據(jù)上，當β>0.02時，AC算法優(yōu)于其他四類算法；在Airport和Protein數(shù)據(jù)集上，AC算法則完全優(yōu)于其他四類算法。同時，當β>β0時，AC算法的τ值隨著β增加而增加；當β<<β0時，相對于EC算法，AC算法可更有效地評估網(wǎng)絡節(jié)點的影響力，說明AC算法更適用于分析低集聚系數(shù)網(wǎng)絡?？梢哉f，在SI仿真環(huán)境下，AC算法在四個網(wǎng)絡上的節(jié)點評估能力均優(yōu)于EC算法。

五種算法在β∈[0.01,0.1]上的平均τ值<τ>分別如表4和表5所示。從表4和表5可以看出，AC算法在四個網(wǎng)絡上與SIR、SI模擬結果對比均能得到最優(yōu)<τ>，說明基于網(wǎng)絡拓撲結構的AC算法在所有網(wǎng)絡中評價節(jié)點重要性時具有最佳的有效性，進一步證實了網(wǎng)絡拓撲結構在發(fā)現(xiàn)重要節(jié)點過程的重要性。換句話說，結合網(wǎng)絡拓撲結構分析重要節(jié)點對網(wǎng)絡結構穩(wěn)定性和功能的影響會更加有效、更有意義。

表4 五個中心性算法與SIR模型模擬序列對比τ平均值

表5 五個中心性算法與SI模型模擬序列對比τ平均值

3.3.2 AC算法準確性分析

圖8 五類算法在前top-N節(jié)點影響力評估τ值變化趨勢

由圖8可知，AC算法在Word、Email和Protein網(wǎng)絡中都具有最優(yōu)τ值。在Airport網(wǎng)絡中，當top-N∈[100,300]時，AC算法的精度比其他算法更高；當top-N∈(300,700]時，AC算法和EC算法的精度在總體上保持一致；當top-N∈(700,1000]時，AC算法精度又優(yōu)于其他四種算法。從整體上看，AC算法相比其他四類算法能夠更準確地發(fā)現(xiàn)網(wǎng)絡中最有影響力的節(jié)點或者重要節(jié)點。由于現(xiàn)實中的大型網(wǎng)絡有相當一部分節(jié)點通過網(wǎng)絡中的重要節(jié)點或者最有影響力的節(jié)點與網(wǎng)絡中的其他部分連通，通過AC算法準確地發(fā)現(xiàn)該類節(jié)點，并對其采取有效控制措施，可進而有效控制整個網(wǎng)絡。例如，如果能在社交網(wǎng)絡中有效控制其中的關鍵重要節(jié)點(最有影響力的用戶)，就能在最大程度上阻斷信息(如謠言等)的傳播路徑，進而控制輿論。

4 結論

本文在深入研究EC算法的基礎上，分析了網(wǎng)絡拓撲結構和信息傳播特性對節(jié)點重要性的影響，提出基于網(wǎng)絡拓撲結構的可達中心性算法。該算法不但考慮了節(jié)點所有的傳播路徑，可計算節(jié)點的全局影響力，還能根據(jù)不同路徑長度下節(jié)點的傳播影響力計算出節(jié)點的局部影響力。然后，本文分析了網(wǎng)絡節(jié)點集聚系數(shù)對AC算法的影響，證明AC算法在集聚系數(shù)較低網(wǎng)絡上的準確性較高。最后，通過模擬SIR和SI兩種傳染病模型在四個真實網(wǎng)絡中的傳播過程，對比分析了AC算法的有效性和準確性。實驗結果表明，與LeaderRank等四類算法相比， AC算法在不同傳染概率下所得到節(jié)點影響力序列更接近與SIR和SI模型所得到的節(jié)點影響力序列，說明AC算法的準確性比其他四類算法更高，可在不同拓撲結構的網(wǎng)絡中更有效地評估節(jié)點的影響力、準確發(fā)現(xiàn)重要節(jié)點，同時更適用于分析聚集系數(shù)較低的網(wǎng)絡。

本文通過計算節(jié)點在不同路徑長度下到達其他節(jié)點的節(jié)點間影響力計算節(jié)點的全局影響力，進而獲得節(jié)點的影響力評價指標，以探索無向網(wǎng)絡中的重要節(jié)點挖掘方法。對于有向網(wǎng)絡而言，其節(jié)點影響其他節(jié)點的路徑包括傳入路徑和傳出路徑，如何分配不同路徑長度下影響力傳入及傳出的權重，進而得到最優(yōu)評價指標尚有待于進一步研究和解決。