基于Tsallis 熵的復雜網絡節點重要性評估方法*

楊松青 蔣沅? 童天馳 嚴玉為 淦各升

1) (南昌航空大學信息工程學院,南昌 330063)

2) (南京理工大學自動化學院,南京 210094)

復雜網絡中節點重要性的評估是網絡特性研究中的一項重要課題,相關研究具有廣泛的應用.目前提出了許多方法來評估網絡中節點的重要性,然而大多數方法都存在評估角度片面或者時間復雜度過高的不足.為了突破現有方法的局限性,本文提出了一種基于Tsallis 熵的復雜網絡節點重要性評估方法.該方法兼顧節點的局部和全局拓撲信息,綜合考察節點的結構洞特征和K 殼中心性,并充分考慮節點及其鄰域節點的影響.為了驗證該方法的有效性,本文采用單調性指標、SIR 模型和Kendall 相關系數作為評價標準,在8 個來自不同領域的真實網絡上與其他方法進行比較.實驗結果表明,此方法能更有效和準確地評估網絡節點的重要性,可以顯著區分不同節點的重要性.此外,該方法的時間復雜度僅為 O(n2),適用于大型復雜網絡.

1 引言

隨著網絡信息技術的發展與進步,對復雜網絡的研究已經在許多領域受到關注.關鍵節點作為復雜網絡的核心要素之一,對網絡的結構和功能有著重要影響,被廣泛的研究與應用[1-3].例如,通過對電力網絡中某關鍵的調度中心和變電所進行維保,能保證整個電力網絡正常運轉的穩定性與高效性[4];通過對病毒傳播網絡中超級傳播源實施隔離,能夠大幅降低病毒的傳播速度和減小擴散范圍[5];通過對社交網絡中核心的言論加以控制,能夠有效促進或抑制信息的傳播[6].因此,評估網絡中節點重要性具有重大意義.

在不同研究背景下,研究人員提出了眾多節點重要性評估方法.目前,度中心性[7]是評估網絡節點重要性的常用方法,該方法簡單但不夠精準.介數中心性[8]和接近中心性[9]分別考慮的是節點間的最短路徑數量和平均最短距離,此類方法從全局信息的角度出發,效果明顯但計算時間復雜度較高,不適用于大型復雜網絡.Kitsak 等[10]依據網絡中節點處于網絡的核心位置往往有較高影響力的思想,提出用K 殼分解法確定網絡中節點的位置,此方法時間復雜度低,適用于大型復雜網絡,然而其區分度過于粗粒化.為了提高節點區分度,Zeng 等[11]提出了混合度分解(mixed degree decomposition,MDD)法,以網絡中剩余的鄰居節點以及刪除的鄰居節點的混合度進行K 殼分解.Bae和Kim[12]在改進K 殼算法時提出了鄰域核心的概念,利用節點自身及其鄰居的K 殼值之和來評估網絡中節點的重要性.Hou 等[13]考慮多指標評估,基于歐拉距離公式計算節點的度值、介數、K 殼等3 個不同指標的組合度量,更為綜合地評估了節點的重要性.王凱莉等[14]提出了一種基于多階鄰居殼數的向量中心性方法,利用向量的形式來表示節點在網絡中的相對重要性.Burt 等[15]提出經典社會學中的“結構洞”理論,設計了網格約束系數來量化節點形成結構洞時所受到的約束,該方法利用了節點的局部信息,具有良好的精度和較低的計算時間復雜度.蘇曉萍和宋玉蓉[16]提出一種基于節點及其鄰域結構洞的評估節點重要性的方法,該方法綜合考慮了節點及其鄰域的度值和拓撲結構,能有效評估網絡中節點的重要性.韓忠民等[17]提出了一種融合結構洞等7 個度量指標的方法,該方法利用基于ListNet 的排序學習方法,能夠較為全面地評估網絡中節點的重要性.

當使用熵來評估復雜網絡時,復雜網絡的結構越有序,熵值就越小,反之亦然.同時,熵也可用來描述整個網絡結構的復雜性和復雜網絡的統計特性.例如,Chen 等[18]提出了結構熵來量化復雜網絡的結構特征.Zhang 等[19]提出了一種基于非廣延統計力學的結構熵來度量網絡的復雜性.黃麗亞等[20]提出了一種基于網絡節點在K步內可達的節點總數的K-階結構熵,用于度量復雜網絡的異構性.Wang 等[21]提出了一種基于K 殼和節點信息熵的改進算法,用于區分上層外殼和下層外殼中節點的重要性.

受到上述研究工作的啟發,本文提出了一種基于Tsallis 熵的復雜網絡節點重要性評估方法(TSM).該方法不僅考慮了節點的結構洞特征和K 殼中心性,還充分考慮了節點自身及其鄰域節點的影響,在兼顧節點的局部和全局拓撲信息的同時,采用Tsallis 熵來度量網絡結構的復雜性.時間復雜度分析表明,該方法的時間復雜度僅為O(n2),適用于大型復雜網絡.為了說明該方法的有效性和適用性,本文選用了8 個來自不同領域的真實網絡,并采用了7 個現有的節點重要性評估方法作為比較方法.在此基礎上,利用單調性指標、SIR 模型和Kendall 相關系數τ說明了該方法的優越性以及不同方法之間的關系.

2 理論基礎

2.1 網絡定義

設圖G=(V,E) 是1 個無向無權網絡,其中V={v1,v2,···,vn}表示G中節點的集合,|V|=n,E={(vi,vj)|vi,vj ∈V}表示G中邊的集合,|E|=m.記An×n=(aij)n×n為G對應的鄰接矩陣,如果節點vi和節點vj之間存在連邊關系,則aij=1,否則aij=0 .

2.2 度中心性

度中心性(degree centrality,DC)[7]是衡量節點影響力的最簡單指標.節點擁有的度數越大,該節點的影響力就越大.節點vi的DC 定義為

其中,n為網絡中節點的∑數量.于是,節點vi的鄰接度可以定義為,其中,Γ(i)為節點vi的鄰居節點的集合.

2.3 介數中心性

介數中心性(betweenness centrality,BC)[8]是基于節點的最短路徑數定義的全局指標.通常,節點的BC 越大,該節點的影響力就越大.節點vi的介數中心性定義為

其中,σst為網絡中任意兩個節點vs和vt之間的最短路徑數目,為經過節點vi的最短路徑數目.

2.4 混合度分解方法

混合度分解方法(mixed degree decomposition method,MDD)由Zeng 等[11]提出,該方法有效提高了K 殼分解方法的區分度.它通過同時考慮節點的剩余度值和節點的已移除度值對K 殼分解過程進行了改進,網絡按照新的混合度值繼續分層,節點vi的混合度定義為

其中,λ是0 到1 之間的可調參數.當λ=0 時,MDD方法與K 殼分解方法一致,但當λ=1 時,它等同于DC.在本文中,設定了參考文獻[11]中使用的參數λ=0.7 .

2.5 全方位距離

Hou 等[13]提出了全方位距離(all-around distance,AAD)指標,其綜合考慮了節點的度值、BC、K 殼等3 個不同指標的影響,采用歐拉距離公式計算了這3 個指標的組合度量,計算公式如下所示:

其中,KS(i) 為節點vi的K 殼值.

2.6 改進的K 殼方法

改進的K 殼方法(improved K-shell method,IKS)由Wang 等[21]提出,該方法結合了K 殼分解方法和節點信息熵.它按照K 殼分層從大到小的順序進行迭代,在每層未被選中節點中選擇節點信息熵最高的節點,直至網絡中所有節點都被選中為止,節點vi的節點信息熵定義為

2.7 結構洞理論

結構洞理論(structural holes theory)是Burt等[15]在1992 年研究社交網絡中的競爭關系時提出的.在社會網絡中,結構洞是指個體之間為非冗余關系,且存在互補信息的差距.為了量化結構洞節點對這些關系的控制,Burt 采用約束系數來測量結構洞中節點形成的約束.當系數越小,節點越容易形成結構洞,節點的影響力越大.節點vi的約束系數為

其中,節點vq是節點vi和節點vj的共同鄰居節點;Lij表示在節點vi的所有鄰居節點中節點vj所占的權重比例.

在計算節點的約束系數時,考慮到節點及其鄰域的度值和拓撲結構對節點重要性的影響將Lij定義為

2.8 Tsallis 非廣延統計力學

對于1 個有限的離散概率集,Boltzmann-Gibbs熵[22]被定義為

其中,k是玻爾茲曼常數,pi滿足標準化條件.

1988 年,基于Boltzmann-Gibbs 熵[22]和Shan non 熵[23],Tsallis[24]提出了一種新的熵,它是一種更一般的形式,能夠描述廣延的和非廣延的系統,被定義為

(9)式中的q-對數函數為

根據(11)式可以將(9)式改寫為

其中,N是子系統的數量.將非廣延參數q用于描述子系統之間相互作用,當q=1 時,Tsallis 熵將退化為Boltzmann-Gibbs 熵.

3 基于Tsallis 熵的節點重要性評估方法

3.1 方法構造

基于Tsallis 熵的節點重要性評估方法構造的基本思想是在綜合考慮節點的結構洞特征和K 殼中心性的同時,利用Tsallis 熵度量網絡結構的復雜性,評估網絡中節點的重要性.由于結構洞特征能體現節點的局部拓撲信息,而K 殼中心性表征了節點的全局拓撲信息,結合這兩種拓撲信息,利用Tsallis 熵度量網絡結構復雜性,并通過對每個節點的自身及其鄰域節點的綜合考察,可以給出1 個合理的評估網絡中節點重要性的方法,即本文提出的TSM 方法.

基于Tsallis 非廣延統計力學,可以得到Tsallis熵的如下形式:

因為結構洞約束系數是基于網絡局部拓撲信息的評估指標,考慮到相鄰節點的結構洞特征對該節點重要性的影響,可以得到Pij的定義:

由于K 殼中心性是描述節點在網絡中所處位置的全局指標,因此它可以用來表示每個節點與整個網絡之間的關系以及不同節點之間的關系.本文運用MDD 方法得到節點vi的K 殼中心性 Ksi及其與網絡中所有節點的K 殼中心性數值之和的比值.進而,可得到節點vi的Tsallis 參數qi:

(17)式的目的是使參數qi＞1,以反映子系統對網絡的次可加性影響.在信息論中,不同的q值表示不同子系統對Tsallis 熵的可加性不同,即q <1,q=1 ,q ＞1 分別代表超可加性、可加性和次可加性.擴展到復雜網絡中,整個網絡可以看作1 個系統,每個節點和相應的連邊可以看作網絡的子系統.

利用Tsallis 熵度量網絡結構復雜性得到T(vi)后,再結合節點自身的結構洞特征,可得

Bae 和Kim[12]在改進K 殼算法時提出了鄰域核心的概念,通過對所有鄰居的K 殼值進行求和來衡量網絡中節點的重要性.本文借鑒了這一概念,充分考慮鄰域節點的影響.對于節點vi,將其所有相鄰節點的IC 值進行相加,得到節點vi的鄰域核心(核心鄰域中心性) Cnc(vi):

在(19)式的基礎上,對其所有相鄰節點的鄰域核心值Cnc 進行求和,可以得到節點vi的擴展鄰域核心Cnc+(vi),最終得到了節點vi的重要性評估值TSM(vi):

3.2 時間復雜度分析

本節將對本文提出的TSM 算法進行計算時間復雜度分析,其具體計算步驟如表1 所列.由表1可知,TSM 要遍歷網絡中每個節點,在計算節點的結構洞約束系數值RCi時,考慮了節點的度及其與鄰居拓撲結構間的關系,故時間復雜度應為O(n2);在計算Tsallis 參數qi時,采用了MDD 方法得到節點的K 殼重要性指標,其時間復雜度為O(n);在計算節點的Ti值時,需要考慮節點的鄰居節點信息,則時間復雜度為O(n*k) ;而在對IC 進行累加時,時間復雜度為O(n) .由此可以看出,TSM 算法的時間復雜度取決于節點的結構洞約束系數值RCi的計算,因此本文提出的TSM 算法的時間復雜度為O(n2) .其中,n為網絡中節點的總數,k為網絡的平均度.

表1 計算步驟Table 1.Step of the calculation.

表2 列出了幾種不同方法的時間復雜度,并按照評估方法所包含的網絡信息將這些方法分成了局部、全局、混合等3 個類型.其中,m為網絡中連邊的總數.當n

圖3 不同傳播率下SIR 和各評估方法之間的Kendall 相關系數,圖中黑色虛線為傳播閾值 βth (a) Karate 網絡;(b) Dolphins網絡;(c) Polbooks 網絡;(d) Jazz 網絡;(e) USAir 網絡;(f) C.Elegans 網絡;(g) Email 網絡;(h) PowerGrid 網絡Fig.3.Kendall correlation coefficient between SIR and the evaluation methods under different transmission rates,the black dashed line in the figure is the propagation threshold βth :(a) Karate network;(b) Dolphins network;(c) Polbooks network;(d) Jazz network;(e) USAir network;(f) C.Elegans network;(g) Email network;(h) PowerGrid network.

表2 不同方法的時間復雜度Table 2.Time complexity of different methods.

4 實驗數據與結果分析

4.1 實驗數據

本文選用了8 個來自不同領域的真實網絡進行實驗,分別是:空手道俱樂部社交網絡Karate network[25]、海豚社交網絡Dolphins network[26]、美國政治書籍網絡Polbooks network[27]、爵士音樂家網絡Jazzmusic network[28]、美國航空運輸網絡USAirline network[29]、秀麗隱桿線蟲網絡C.Elegans network[30]、大學電子郵件網絡Email network[31]、美國電力網絡PowerGrid network[1].各網絡的統計特征如表3 所列.其中n為節點總數,m為連邊總數,〈k〉為平均度,c為聚類系數,〈d〉為平均最短路徑長度,βth為SIR 模型傳播率閾值,β為實際傳播率取值.

表3 網絡的統計特征Table 3.Statistical characteristics of the networks.

4.2 有效性分析

為了驗證本文提出的TSM 算法的有效性和準確性,首先以Karate 網絡為例進行仿真分析,其拓撲圖如圖1 所示.選用了DC[7]、BC[8]、MDD[11]、鄰域結構洞方法[16](N-Burt)、核心鄰域中心性[12](Cnc+)、AAD[13]以及IKS[21]等7 種方法與本文提出的TSM 方法進行對比,得到網絡前15 個關鍵節點的重要性評估結果如表4所列.

圖1 Karate 網絡的拓撲結構Fig.1.Topological structure of the Karate network.

通過結合Karate 網絡拓撲結構(圖1)與重要性評估結果(表4)分析可知:節點v4和節點v32擁有的鄰居數量均為6 且其所處的網絡信息傳輸位置相同,而在其他方法中節點v4和節點v32的重要性是不一樣的;節點v9,v14,v24擁有的鄰居數量相同均為5,而它們存在的鄰域結構洞差值較大,因此,僅僅考慮節點擁有的鄰居數量和其所處的網絡信息傳輸位置無法進一步區分節點的重要性.采用N-Burt 方法評估節點重要性時,未考慮到相鄰節點的結構洞特征對節點重要性的影響,如節點v32比節點v4存在更多的結構洞,但節點v4的相鄰節點較節點v32的相鄰節點在網絡中是更為重要的“橋接”節點,信息能通過它們更快地擴散至網絡.BC 是一種能夠很好地體現節點在網絡信息傳播過程中的重要性的方法,但是對于一些不在任何一條最短路徑上的節點以及信息負載能力相似的節點,如節點v6,v7,v8,v28等仍需要進一步考慮節點的局部信息來評估,而且此方法的計算時間復雜度較高.

表4 Karate 網絡的節點重要度評估結果Table 4.Node importance evaluation results in the Karate network.

表5 不同評估方法的單調性指標MTable 5.Monotonicity index M of different evaluation methods.

本文所提出的TSM 方法克服了以上方法的不足,它從節點的局部和全局拓撲信息兩個角度出發,綜合考慮節點自身的結構洞特征和網絡位置信息以及鄰域節點的影響,并基于Tsallis 熵度量網絡結構的復雜性,可提高節點重要性的區分度,準確地評估節點重要性.如表4 所列,通過TSM 方法評估出的前15 個重要節點與其他方法評估出的重要節點基本相同,說明TSM 方法能夠有效地評估節點的重要性.在TSM 方法中,節點v4比節點v32更為重要,這很好地體現了相鄰節點的結構洞特征對節點的影響,同時也說明本方法克服了BC的不足;節點v9,v14,v24和節點v8,v28,v30的重要性得到了進一步的區分,其中,節點v9的重要性高于節點v14,這說明了本方法既有效地識別了網絡中的“橋接”節點,亦克服了DC 的不足.通過對比,本文提出的TSM 方法能有效地評估節點重要性,可進一步提高節點重要性的區分度.

4.3 評價標準

接下來介紹驗證所提出的TSM 方法準確性的評價標準.它們分別是單調性指標[12]、SIR 模型[32]和Kendall 相關系數[33].

本文采用單調性指標[12]M(R) 來量化不同重要性評估方法的分辨率,如下所示:

其中,R為評估方法得到的每個節點的重要性排序向量,n為網絡中節點的個數,nr為重要性相同的節點的數量.M(R) 的取值介于0 到1 之間.如果M(R)=1,則排序向量R是完全單調的,說明該評估方法能將網絡中所有節點的重要性完全區分;如果M(R)=0,則表示網絡中所有節點的重要性相同.

目前,大多數學者采用標準的SIR 模型[32]來檢測信息和病毒的傳播能力.在SIR 模型中,網絡中的每個節點可以處于以下3 種狀態中的1 種:易感狀態S (susceptible)、感染狀態I (infected)以及恢復狀態R (removed).在傳播初始階段,網絡中只有節點vi處于感染狀態,其余節點均處于易感狀態.在每個時間步中,處于狀態I 的節點以傳播率β嘗試感染處于S 狀態的鄰居節點,同時以概率μ恢復成狀態R 后,不再被感染.傳播過程結束的標志是網絡中不再出現I 態節點.在整個SIR 傳播過程結束時,將網絡中處于狀態R 的節點的數量S(i)看作節點vi的傳播能力.為不失一般性,本文設定恢復率μ=1 .在設定傳播率時,如果傳播率β過小或過大,都會導致傳播過程無法正常進行,從而無法準確衡量每個節點的傳播能力.因此,本文設定傳播率閾值為βth≈〈k〉/〈k2〉.其中〈k〉為網絡平均度,〈k2〉為網絡二階鄰居平均度.為保證傳播過程正常進行,本文的傳播率β在傳播率閾值βth附近取值.

為了評估節點重要性評估方法的精準度,本文使用Kendall 相關系數[33]τ來度量每個評估方法得到的節點重要性排序列表R與從SIR 模型獲得的節點傳播能力排序列表σ之間的相關性.假設存在兩個包含n個節點的序列X和Y,其中X=(x1,x2,···,xn)和Y=(y1,y2,···,yn) ,將序列X和序列Y中的元素一一對應構造1 個新的序列XY=((x1,y1),···,(xi,yi),···,(xn,yn)).而對于序列XY中的任意一對元素XYi=(xi,yi)和XYj=(xj,yj),若xi ＞xj且xi ＞yj,或xi

其中,C和D分別表示同序對和異序對的數量.τ的取值介于—1 和1 之間,τ=1 時表示兩個序列完全正相關,即相關系數τ越接近1,精確度越高;反之,則表示完全負相關.

4.4 實驗分析

本節記錄并分析了不同節點重要性評估方法在不同真實網絡中的實驗結果.

首先選用了DC,BC,MDD,N-Burt,Cnc+,AAD 以及IKS 等7 種評估方法作為對比方法,利用單調性指標[12]M考察了7 種對比方法與本文所提出的TSM 方法的分辨率,即對節點重要性的區分度.表5 記錄了不同評估方法在8 個真實網絡中的分辨率,并在圖2 中更為直觀地呈現了它們之間的差異.從圖2 可以看出,TSM方法在8 個真實網絡中表現十分出色.此外,Cnc+和IKS 方法的區分度也很好.與其他7 種方法相比,TSM 方法大多數情況下可以給出更高M值,而且在所有網絡中M(TSM)都非常接近甚至等于1.因此,TSM 方法能夠更好地區分節點的重要性.

圖2 不同評估方法的單調性指標M (a) Karate 網絡、Dolphins 網絡、Polbooks 網絡和Jazz 網絡;(b) USAir 網絡、C.Elegans 網絡、Email 網絡和PowerGrid 網絡Fig.2.Monotonicity index M of different evaluation methods:(a) Karate network,Dolphins network,Polbooks network and Jazz network;(b) USAir network,C.Elegans network,Email network and PowerGrid network.

其次,使用SIR 模型得到節點的傳播能力排序σ,并計算了不同評估方法的排序與σ之間的Kendall 相關系數τ.相關性越高,對節點重要性的評估就越準確.由于SIR 模型迭代過程的隨機性,本文對每個節點重復模擬該過程,然后取其平均值.模擬將遵循以下規則:對于網絡|V| ＜ 100,模擬迭代104次;對于 100<|V|<104,模擬迭代103次.表6 展示了8 個真實網絡在選定傳播率下各評估方法的Kendall 相關系數,SIR 模型的實際傳播率取值如表3 所列.從表6 可以看出,TSM 方法的相關系數值在0.8 到1 之間.同時,與其他方法相比,TSM 方法的相關性在8 個真實網絡中都最為顯著.因此,TSM 方法的準確性得到了初步的驗證.

表6 選定傳播率下SIR 和各評估方法之間的Kendall 相關系數Table 6.Kendall correlation coefficient between SIR and evaluation methods under a certain transmission rate.

為了進一步驗證所提方法的準確性和可靠性,對比了不同傳播率下各評估方法與SIR 模型排序結果之間的Kendall 相關系數,如圖3 所示.從圖3可以看出,當傳播率β在傳播閾值βth附近取值時,TSM 方法的相關系數除了在Karate 網絡中略低于Cnc+方法以外,在大多數情況下都高于其他方法,與SIR 模型得到的節點傳播能力有顯著的相關性.同時,可以看出當傳播率β遠大于或者遠小于傳播閾值βth時,在除Karate,USAir 和PowerGrid網絡以外的5 個真實網絡中,DC,MDD 以及AAD等方法表現出了比TSM 方法更好的相關性.而BC的相關性在8 個真實網絡中表現最差.因此,TSM方法能夠更為準確地評估節點的重要性.

然后,對Kendall 相關系數的考察節點范圍進行了調整,將考察的節點從整體節點變為部分節點,進一步研究了各個評估方法得到的不同比例排序靠前的節點與節點傳播能力排序的相關性結果.在8 個真實網絡中進行實驗,設置節點比例L的變化范圍為0.05—1.如圖4 所示,給出不同比例節點下各評估方法的相關系數值.從圖4 可以看出,本文提出的TSM 算法在不同比例節點下都能取得不錯的節點重要性評估結果,且在更大范圍的L值下可以取得更好的評估結果.

圖4 不同比例節點下各評估方法的Kendall 相關系數 (a) Karate 網絡;(b) Dolphins 網絡;(c) Polbooks 網絡;(d) Jazz 網絡;(e) USAir 網絡;(f) C.Elegans 網絡;(g) Email 網絡;(h) PowerGrid 網絡Fig.4.Kendall correlation coefficient of the evaluation methods under different proportion nodes:(a) Karate network;(b) Dolphins network;(c) Polbooks network;(d) Jazz network;(e) USAir network;(f) C.Elegans network;(g) Email network;(h) PowerGrid network.

最后,分析了TSM 方法與其他評估方法之間的關系,如圖5 所示.圖中每個點代表復雜網絡中的1 個節點,點的顏色表示由SIR 模型得到的節點傳播能力,橫軸和縱軸分別為TSM 方法和其他方法得到的網絡中各節點重要性數值.當圖中的節點呈線性分布時,說明TSM 方法與該方法有強的相關性.從圖5 中的節點分布情況可以發現,TSM與DC,MDD,N-Burt 之間存在強的相關性,這說明TSM 方法既充分考慮了節點的DC 和位置信息,而且有能力識別到網絡中的“橋接”節點.此外,TSM 與Cnc+,AAD,IKS 之間節點分布呈較明顯的線性關系,這說明節點重要性排名總體相似,亦證明TSM 方法能有效評估節點重要性.從圖5 還可以發現,有一些節點盡管其BC 數值大,但其傳播能力并不是很強,因此僅靠BC 評估節點的重要性并不準確.所以在評估網絡中節點的重要性上,TSM 方法較其他方法更有優勢.

圖5 TSM 與其他評估方法之間的關系 (a) Karate 網絡,β=0.25;(b) Dolphins 網絡,β=0.15;(c) Polbooks 網絡,β=0.1;(d) Jazz 網絡,β=0.04Fig.5.Relationship between TSM and other evaluation methods (a) Karate network,β=0.25;(b) Dolphins network,β=0.15;(c) Polbooksnetwork,β=0.1;(d) Jazz network,β=0.04.

5 結論

本文提出了一種TSM 方法,有效地對復雜網絡中節點重要性進行評估和排序.TSM 方法兼顧局部拓撲信息和全局拓撲信息,結合了節點的結構洞特征和K 殼中心性,利用Tsallis 熵度量網絡結構的復雜性,彌補了現存方法評估角度片面的不足,優化了可用資源的利用,使信息得以有效傳播.該方法在考慮節點的鄰域結構和位置信息的同時,有能力識別到網絡中的“橋接”節點,從而對復雜網絡中節點的重要性進行有效的評估.在8 個真實網絡上的實驗結果表明,與其他評估方法如DC,BC,MDD,N-Burt,Cnc+,AAD 和IKS 相比,TSM 方法能更好地區分節點重要性的差異,在不同比例節點下都能準確地評估節點的重要性.此外,TSM 方法的時間復雜度僅為O(n2),適用于大型復雜網絡.尋找一種結合網絡結構和傳播動力學的更有效的方法來評估網絡中節點的重要性仍然是一個長期的挑戰.未來的工作將集中在如何應用所提出的TSM 方法來評估多層網絡中的節點重要性.