一種新的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估方法

張憲立，唐建新

（蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院，蘭州 730050）

0 概述

復(fù)雜網(wǎng)絡(luò)將現(xiàn)實(shí)社會(huì)中的復(fù)雜系統(tǒng)抽象為網(wǎng)絡(luò)結(jié)構(gòu)圖以便于描述與理解，并利用節(jié)點(diǎn)與節(jié)點(diǎn)間的連邊關(guān)系來描述系統(tǒng)中各組成部分之間的關(guān)系。在網(wǎng)絡(luò)信息時(shí)代，人們通過社交網(wǎng)絡(luò)獲取和傳遞消息，社交網(wǎng)絡(luò)的出現(xiàn)極大地便利了人們的生活，并將逐漸取代電視、廣播和報(bào)紙等傳統(tǒng)信息傳播方式。在整個(gè)社交網(wǎng)絡(luò)中通常由多個(gè)重要的節(jié)點(diǎn)控制信息傳播，因此準(zhǔn)確識別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)對于研究網(wǎng)絡(luò)信息交互問題具有重要作用［1-2］。

在現(xiàn)實(shí)世界中，每個(gè)社交網(wǎng)絡(luò)都可以被抽象為一張圖，其中節(jié)點(diǎn)代表網(wǎng)絡(luò)中的用戶，節(jié)點(diǎn)間的連邊代表用戶之間的關(guān)系［3］。近年來，研究人員對識別復(fù)雜網(wǎng)絡(luò)中具有影響力的傳播者進(jìn)行了大量研究并從不同角度分析節(jié)點(diǎn)中心性指標(biāo)，例如，只考慮節(jié)點(diǎn)本身拓?fù)浣Y(jié)構(gòu)性質(zhì)的度中心性（Degree Centrality，DC）［4］，判定一個(gè)給定節(jié)點(diǎn)是否位于其他節(jié)點(diǎn)最短路徑上的介數(shù)中心性（Betweenness Centrality，BC）［5］，代表一個(gè)給定節(jié)點(diǎn)到網(wǎng)絡(luò)中其他節(jié)點(diǎn)的距離之和的倒數(shù)的緊密中心性（Closeness Centrality，CC）［6］以及通過網(wǎng)絡(luò)分解確定節(jié)點(diǎn)重要性的K核分解中心性（K-Shell decomposition centrality，KS）［7］和H指數(shù)中心性（H-index centrality，H）［8］。

由于現(xiàn)有基于中心性的節(jié)點(diǎn)重要性評估方法經(jīng)常會(huì)出現(xiàn)重要程度不同的兩個(gè)節(jié)點(diǎn)被賦予相同的權(quán)值，因此不能保證網(wǎng)絡(luò)中所有節(jié)點(diǎn)的重要性得到準(zhǔn)確度量。此外，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)規(guī)模以及節(jié)點(diǎn)位置都會(huì)對評估指標(biāo)的精確性與適用性產(chǎn)生較大影響，因此，研究人員綜合考慮這些因素后對現(xiàn)有評估方法進(jìn)行了改進(jìn)。文獻(xiàn)［9］通過對K核分解中心性進(jìn)行再次分解提出混合度分解中心性，文獻(xiàn)［10］考慮了節(jié)點(diǎn)及其鄰居性質(zhì)提出局部結(jié)構(gòu)中心性，文獻(xiàn)［11］基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)提出混合度中心性，文獻(xiàn)［12］根據(jù)節(jié)點(diǎn)位置及其鄰居節(jié)點(diǎn)性質(zhì)提出一種新的節(jié)點(diǎn)重要性評估方法，上述方法均是通過可調(diào)參數(shù)來調(diào)整評估性能。文獻(xiàn)［13］提出一種兩層架構(gòu)的節(jié)點(diǎn)重要性評估方法，文獻(xiàn)［14］采用多屬性決策技術(shù)提高節(jié)點(diǎn)重要性的評估準(zhǔn)確性，但由于此類方法的評估性能取決于所采取組合方式的性能，因此與節(jié)點(diǎn)真實(shí)的重要程度存在一定差距。

在現(xiàn)有評估方法的基礎(chǔ)上，本文根據(jù)鄰居節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)定義改進(jìn)的H指數(shù)中心性（Improved H-index centrality，IH），通過IH計(jì)算節(jié)點(diǎn)本身及其鄰居節(jié)點(diǎn)的IH值之和（ILH），并將節(jié)點(diǎn)自身及其鄰居節(jié)點(diǎn)的ILH值分別作為節(jié)點(diǎn)質(zhì)量和鄰居節(jié)點(diǎn)的質(zhì)量，同時(shí)利用萬有引力定律公式定義改進(jìn)的重力中心性（Improved Gravity Centrality，IGC）。

1 相關(guān)定義

令G(V，E) 表示一個(gè)無向無權(quán)的簡單網(wǎng)絡(luò)，其中：V={ν1，ν2，…，νn}表示G中節(jié)點(diǎn)的集合；E={(νi，νj)|νi，νj∈V}表示G中邊的集合，且|V|=n，|E|=m。A表示G對應(yīng)的鄰接矩陣，如果節(jié)點(diǎn)νi和νj之間存在連邊，則其元素Aij=1，否則Aij=0。在復(fù)雜網(wǎng)絡(luò)中，評估節(jié)點(diǎn)重要性的方法主要分為：僅考慮節(jié)點(diǎn)本身及其鄰居節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)的局部評估方法，考慮節(jié)點(diǎn)在網(wǎng)絡(luò)全局中的作用的全局評估方法及考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中所處位置的位置屬性評估方法3種。

定義1網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)νi的度中心性為與該節(jié)點(diǎn)相連接的其他節(jié)點(diǎn)的數(shù)目，即該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)。度中心性的計(jì)算公式為：

其中，n為網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù)。

定義2網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)νj的介數(shù)中心性為任意兩個(gè)節(jié)點(diǎn)間的最短路徑通過該節(jié)點(diǎn)的數(shù)量與節(jié)點(diǎn)間總路徑數(shù)量的比值，介數(shù)中心性的計(jì)算公式為：

其中，σst為網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)s和t之間的最短路徑數(shù)量，σst(νi)為通過節(jié)點(diǎn)νi的最短路徑數(shù)量。當(dāng)節(jié)點(diǎn)的介數(shù)中心性較大時(shí)，說明該節(jié)點(diǎn)在傳輸信息、物質(zhì)和能量時(shí)負(fù)載較小。

定義3網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)νi的緊密中心性為該節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離之和的倒數(shù)，緊密中心性的計(jì)算公式為：

其中，dij為節(jié)點(diǎn)νi到網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)νj的最短距離。

定義4 K核分解為重復(fù)去除網(wǎng)絡(luò)中度值小于k（k=1，2，…）的所有節(jié)點(diǎn)及其連邊，使得網(wǎng)絡(luò)中剩下的節(jié)點(diǎn)的度值均大于等于k。通過對網(wǎng)絡(luò)進(jìn)行K核分解可計(jì)算出不同節(jié)點(diǎn)的ks值。首先將網(wǎng)絡(luò)中所有節(jié)點(diǎn)的ks值設(shè)置為1，然后找到網(wǎng)絡(luò)中所有度為1的節(jié)點(diǎn)并將這些節(jié)點(diǎn)及其連邊關(guān)系刪除，重新計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的度后，再將度為1的節(jié)點(diǎn)及其連邊關(guān)系刪除，直至網(wǎng)絡(luò)中沒有度為1的節(jié)點(diǎn)。此時(shí)，網(wǎng)絡(luò)中剩余節(jié)點(diǎn)的ks值設(shè)置為2，再重復(fù)執(zhí)行上述操作，直至網(wǎng)絡(luò)中沒有度為2的節(jié)點(diǎn)。以此類推，直至網(wǎng)絡(luò)中沒有節(jié)點(diǎn)存在。節(jié)點(diǎn)的ks值越大，意味著該節(jié)點(diǎn)越接近于網(wǎng)絡(luò)中心，最靠近中心的節(jié)點(diǎn)被稱為K核分解中心性節(jié)點(diǎn)。

定義5 H指數(shù)中心性通過考慮鄰居節(jié)點(diǎn)的度和節(jié)點(diǎn)自身的度來確定節(jié)點(diǎn)的重要性。節(jié)點(diǎn)中心性由節(jié)點(diǎn)自身及其鄰居的性質(zhì)決定，節(jié)點(diǎn)νi的H指數(shù)中心性計(jì)算公式為：

在上述定義中，度中心性、介數(shù)中心性和緊密中心性均只考慮網(wǎng)絡(luò)圖中單個(gè)節(jié)點(diǎn)的拓?fù)湮恢眉捌涮卣?，僅從網(wǎng)絡(luò)局部特性對節(jié)點(diǎn)重要性進(jìn)行分析，而K核分解中心性及H指數(shù)中心性則從網(wǎng)絡(luò)全局的拓?fù)浣Y(jié)構(gòu)來考慮節(jié)點(diǎn)的重要性，但其仍不能準(zhǔn)確反映出網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度?？梢?，僅考慮節(jié)點(diǎn)的單一影響因素不能準(zhǔn)確評估網(wǎng)絡(luò)中節(jié)點(diǎn)的性能與重要性。

2 節(jié)點(diǎn)重要性評估方法

一個(gè)節(jié)點(diǎn)可以被其鄰居節(jié)點(diǎn)影響，然而節(jié)點(diǎn)的H指數(shù)對節(jié)點(diǎn)本身及其鄰居節(jié)點(diǎn)信息的微小變化并不敏感，因此不利于評估節(jié)點(diǎn)在網(wǎng)絡(luò)鏈路信息發(fā)生微小變化時(shí)的傳播能力。此外，在多數(shù)情況下很難確保所收集的數(shù)據(jù)集完全正確且沒有任何鏈路信息錯(cuò)誤。對于一個(gè)節(jié)點(diǎn)，如果某些鄰居節(jié)點(diǎn)的信息發(fā)生變化，該節(jié)點(diǎn)的H指數(shù)值不會(huì)受到影響，這是因?yàn)镠指數(shù)只考慮具有高質(zhì)量信息的鄰居數(shù)量，少數(shù)鄰居的微小變化不會(huì)引起節(jié)點(diǎn)整體傳播能力的變化。對于基于度中心性和介數(shù)中心性等的節(jié)點(diǎn)重要性評估方法，少數(shù)邊缺失或不正確的連接信息會(huì)對節(jié)點(diǎn)排序結(jié)果產(chǎn)生重要的影響。

然而，H指數(shù)對于重要程度不同的節(jié)點(diǎn)總是賦予相同的值，這導(dǎo)致了在區(qū)分這些節(jié)點(diǎn)的實(shí)際傳播能力時(shí)存在分辨限制問題。針對該問題，本文提出一種改進(jìn)的H指數(shù)中心性（IH），IH綜合考慮了節(jié)點(diǎn)νi的所有鄰居的性能，將節(jié)點(diǎn)的重要性進(jìn)行進(jìn)一步劃分。節(jié)點(diǎn)νi的IH指數(shù)中心性計(jì)算公式為：

其中，α1和α2表示介于［0，1］的隨機(jī)變量，A1表示在νi的鄰居節(jié)點(diǎn)中度大于節(jié)點(diǎn)νi的節(jié)點(diǎn)個(gè)數(shù)，A2表示在νi的鄰居節(jié)點(diǎn)中度等于節(jié)點(diǎn)νi的節(jié)點(diǎn)個(gè)數(shù)，表示節(jié)點(diǎn)νi的鄰居節(jié)點(diǎn)集合，|表示節(jié)點(diǎn)νi的度。

節(jié)點(diǎn)νi及其鄰居節(jié)點(diǎn)的ILH值計(jì)算公式為：

受萬有引力定律的影響，本文以節(jié)點(diǎn)νi和節(jié)點(diǎn)νj的ILH值作為節(jié)點(diǎn)νi和節(jié)點(diǎn)νj的質(zhì)量，兩節(jié)點(diǎn)間的最短距離作為節(jié)點(diǎn)間的半徑，提出改進(jìn)的重力中心性。節(jié)點(diǎn)νi的改進(jìn)重力中心性計(jì)算公式為：

圖1為一個(gè)簡單網(wǎng)絡(luò)的示意圖，其中，節(jié)點(diǎn)數(shù)量|V|為13，邊數(shù)量|E|為17。將本文IGC方法與DC、H、IH、ILH評估方法進(jìn)行對比，結(jié)果如表1所示。在DC和H兩種經(jīng)典方法中，將所有節(jié)點(diǎn)分別賦予5種和3種不同的權(quán)值，即節(jié)點(diǎn)被劃分為5種和3種等級，因此出現(xiàn)了重要性不一樣的節(jié)點(diǎn)被賦予相同權(quán)值的情況，對于節(jié)點(diǎn)重要性的評估準(zhǔn)確性較差。IH、ILH和IGC方法分別將所有節(jié)點(diǎn)賦予8種、9種和12種權(quán)值，即節(jié)點(diǎn)被劃分為8種、9種和12種等級。本文IGC方法綜合考慮了節(jié)點(diǎn)自身性質(zhì)及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，相比其他方法在區(qū)分節(jié)點(diǎn)重要性方面效果更佳，找出的重要節(jié)點(diǎn)準(zhǔn)確性更高。

圖1 一個(gè)簡單網(wǎng)絡(luò)的示意圖Fig.1 Schematic diagram of a simple network

表1 簡單網(wǎng)絡(luò)中對應(yīng)DC、H、IH、ILH、IGC方法的權(quán)值設(shè)置Table 1 Weight setting corresponding to DC,H,IH,ILH,IGC methods in a simple network

3 評價(jià)標(biāo)準(zhǔn)及方式

3.1 SIR傳播模型

SIR傳播模型［16］可用于評估網(wǎng)絡(luò)中不同節(jié)點(diǎn)的傳播能力。在標(biāo)準(zhǔn)隨機(jī)SIR傳播模型中，每個(gè)節(jié)點(diǎn)可以被分為易感（S）、感染（I）和恢復(fù)（R）3種不同狀態(tài)［17-19］。在傳播過程開始時(shí)，只有一個(gè)節(jié)點(diǎn)被設(shè)置為I狀態(tài)，而其他節(jié)點(diǎn)均被設(shè)置為S狀態(tài)。然后，受感染的節(jié)點(diǎn)將以概率α擴(kuò)散至與之相連的所有易感節(jié)點(diǎn)，而受感染的節(jié)點(diǎn)將有可能以概率β進(jìn)行恢復(fù)并被設(shè)置為R狀態(tài)。在傳播過程結(jié)束后，整個(gè)網(wǎng)絡(luò)中只有I與R兩種狀態(tài)，而統(tǒng)計(jì)出的網(wǎng)絡(luò)中易感節(jié)點(diǎn)的數(shù)量即為節(jié)點(diǎn)的傳播能力。

在評估完節(jié)點(diǎn)的傳播能力后，使用Kendall相關(guān)系數(shù)表示各中心性指標(biāo)與真實(shí)數(shù)據(jù)之間的關(guān)系［20-21］。假設(shè)序列Χ=(x1，x2，…，xn)和序列Y=(y1，y2，…，yn)是兩個(gè)與節(jié)點(diǎn)相關(guān)的序列，兩個(gè)序列中的元素個(gè)數(shù)一致，且每個(gè)序列中的第i個(gè)元素都表示節(jié)點(diǎn)νi的某個(gè)屬性值。將兩個(gè)節(jié)點(diǎn)一一對應(yīng)組成一個(gè)新的序列ΧY=((x1，y1)，(x2，y2)，…，(xn，yn))，取ΧY中的兩個(gè)元素(xi，yi)和(xj，yj)(其中i≠j)，若xi＞xj且yi＞yj或者xi＜xj且yi＜yj，則認(rèn)為這兩個(gè)元素一致；若xi＞xj且yi＜yj或者xi＜xj且yi＞yj，則認(rèn)為這兩個(gè)元素不一致。Kendall相關(guān)系數(shù)τ的計(jì)算公式為：

其中，C表示XY中任意兩個(gè)元素所組成有序?qū)χ芯哂幸恢滦栽貙Φ臄?shù)量，D表示XY中任意兩個(gè)元素所組成有序?qū)χ芯哂胁灰恢滦栽貙Φ臄?shù)量。τ的取值范圍為［-1，1］，當(dāng)τ＞0時(shí)認(rèn)為兩個(gè)有序?qū)φ嚓P(guān)，當(dāng)τ＜0時(shí)認(rèn)為兩個(gè)有序?qū)ω?fù)相關(guān)。通過在SIR傳播模型中得到的節(jié)點(diǎn)傳播能力和中心性指標(biāo)所計(jì)算出的Kendall相關(guān)系數(shù)可以較好地反映節(jié)點(diǎn)重要性評估方法的優(yōu)劣，更優(yōu)的中心性指標(biāo)有助于更好地評估節(jié)點(diǎn)的重要性。

3.2 單調(diào)性

區(qū)分具有不同傳播能力及等級的節(jié)點(diǎn)的能力是度量復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性評估方法的重要指標(biāo)之一，而利用單調(diào)性（M）可以檢驗(yàn)不同中心性序列對于節(jié)點(diǎn)重要性的區(qū)分能力［13，22］。序列R的M值計(jì)算公式為：

其中：n表示序列R中的節(jié)點(diǎn)數(shù)量；nr表示在等級r上的節(jié)點(diǎn)數(shù)量；M的取值范圍為［0，1］，其數(shù)值較大表示該方法具有較高的評估準(zhǔn)確率。

4 實(shí)驗(yàn)數(shù)據(jù)集與結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本文共使用6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和2個(gè)人工網(wǎng)絡(luò)數(shù)據(jù)集。真實(shí)網(wǎng)絡(luò)包括Zachary空手道俱樂部工作成員關(guān)系網(wǎng)絡(luò)（Karate）［23］、Krebs美國政治圖書網(wǎng)絡(luò)（Polbooks）［24］、爵士音樂家網(wǎng)絡(luò)（Jazz）［25］、美國航空公司飛行路線網(wǎng)絡(luò)（USair）［26］、Rovira Virgili大學(xué)電子郵件信息網(wǎng)絡(luò)（Email）［27］和蛋白質(zhì)相互關(guān)系網(wǎng)絡(luò)（Yeast）［28］。人工網(wǎng)絡(luò)包含小世界網(wǎng)絡(luò)（WS）［29］和Lancichinetti-Fortunato-Radicchi隨機(jī)網(wǎng)絡(luò)（LFR）［30］，人工網(wǎng)絡(luò)都是通過Gephi軟件自動(dòng)生成。網(wǎng)絡(luò)數(shù)據(jù)集的具體設(shè)置如表2所示，其中βth表示各個(gè)網(wǎng)絡(luò)在SIR傳播模型中的感染率閾值。

表2 網(wǎng)絡(luò)數(shù)據(jù)集設(shè)置Table 2 Setting of network datasets

4.2 實(shí)驗(yàn)結(jié)果

為評價(jià)本文IGC方法的評估性能進(jìn)行以下實(shí)驗(yàn)：1）確定評估方法和SIR傳播模型之間的排序相關(guān)性，并計(jì)算出IGC方法相較于現(xiàn)有方法的評估準(zhǔn)確率提升比例；2）將IGC方法與DC、BC、CC、KS和H方法進(jìn)行單調(diào)性分析與比較。

4.2.1 準(zhǔn)確性分析

為驗(yàn)證評估方法與SIR傳播模型之間的排序相關(guān)性，通過計(jì)算節(jié)點(diǎn)傳播效率得到網(wǎng)絡(luò)中的最優(yōu)傳播者。在實(shí)驗(yàn)過程中：1）使用基于網(wǎng)絡(luò)屬性特征和拓?fù)浣Y(jié)構(gòu)的靜態(tài)評估方法計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)傳播效率序列；2）基于網(wǎng)絡(luò)數(shù)據(jù)集，采用SIR傳播模型及Kendall相關(guān)系數(shù)τ開展動(dòng)態(tài)傳播模擬仿真，近似計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)傳播效率序列。在6個(gè)真實(shí)網(wǎng)絡(luò)和2個(gè)人工網(wǎng)絡(luò)數(shù)據(jù)集上，將本文IGC方法與5種評估方法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖2所示，其中，β表示各個(gè)網(wǎng)絡(luò)在SIR傳播模型中的感染率，τ表示SIR傳播模型與評估方法之間的Kendall相關(guān)系數(shù)，平行于縱坐標(biāo)軸的虛線表示各個(gè)網(wǎng)絡(luò)的感染率閾值βth。在LFR網(wǎng)絡(luò)中，由于KS算法在感染率過低時(shí)效果不佳，為突出顯示其他算法間的性能差異，因此本文在圖2（h）中只呈現(xiàn)了τ≥0.4時(shí)的Kendall相關(guān)系數(shù)變化趨勢。實(shí)驗(yàn)結(jié)果表明，本文IGC方法與現(xiàn)有方法相比在多數(shù)網(wǎng)絡(luò)數(shù)據(jù)集中均具有更好的評估性能。由圖2可以看出，在β值較小時(shí)，本文IGC方法的Kendall相關(guān)系數(shù)τ與現(xiàn)有方法相比有一定差距，但隨著β的不斷增大且接近βth時(shí)，IGC方法的評估性能要優(yōu)于現(xiàn)有方法。在β＞βth的情況下，δ=0.01時(shí)不同評估方法的Kendall相關(guān)系數(shù)τ的平均值σ(τI)計(jì)算公式為：

圖2 在網(wǎng)絡(luò)數(shù)據(jù)集上不同評估方法與SIR傳播模型的Kendall相關(guān)系數(shù)變化趨勢1Fig.2 The change trend 1 of Kendall correlation coefficient between different evaluation methods and SIR propagation model on the network datasets

網(wǎng)絡(luò)數(shù)據(jù)集中不同評估方法的Kendall相關(guān)系數(shù)τ的平均值σ（τI）比較如表3所示。由此可以看出，本文IGC方法的σ(τI)在多數(shù)網(wǎng)絡(luò)中要優(yōu)于現(xiàn)有方法。

表3 網(wǎng)絡(luò)數(shù)據(jù)集中不同評估方法的Kendall相關(guān)系數(shù)平均值比較Table 3 Comparison of average value of Kendall correlation coefficient of different evaluation methods in the network datasets

為衡量本文IGC方法相比現(xiàn)有方法的評估準(zhǔn)確率提升比例，對Kendall相關(guān)系數(shù)τ的定義進(jìn)行改進(jìn)，計(jì)算公式修改為：

其中，τC(I)表示IGC方法和SIR模型之間的Kendall相關(guān)系數(shù)，τI表示現(xiàn)有方法和SIR模型之間的Kendall相關(guān)系數(shù)。當(dāng)ηI＞0時(shí)，意味著IGC方法優(yōu)于現(xiàn)有方法；當(dāng)ηI＜0時(shí)，意味著IGC方法劣于現(xiàn)有方法；當(dāng)ηI=0時(shí)，意味著IGC方法與現(xiàn)有方法相比無明顯優(yōu)劣區(qū)別。

圖3表明在不同網(wǎng)絡(luò)數(shù)據(jù)集中IGC方法與現(xiàn)有方法相比的評估準(zhǔn)確率提升比例，其中，β表示在SIR傳播模型中的不同感染率，η表示IGC方法與現(xiàn)有方法相比評估準(zhǔn)確率的提升比例，平行于橫坐標(biāo)軸的虛線表示τC(IGC)曲線，平行于縱坐標(biāo)軸的虛線表示各個(gè)網(wǎng)絡(luò)的βth。在WS和LFR網(wǎng)絡(luò)中，由于KS方法效果明顯劣于對比方法，性能接近兩個(gè)量級，因此為更直觀呈現(xiàn)本文IGC方法和其他方法間的性能差異，本文在圖3（g）和圖3（h）中未呈現(xiàn)KS方法的Kendall相關(guān)系數(shù)變化趨勢。

圖3 在網(wǎng)絡(luò)數(shù)據(jù)集上不同評估方法與SIR傳播模型的Kendall相關(guān)系數(shù)變化趨勢2Fig.3 The change trend 2 of Kendall correlation coefficient between different evaluation methods and SIR propagation model on the network datasets

由圖3可看出，在β＞βth時(shí)τC(IGC)相比τBC、τKS有較大的評估準(zhǔn)確率性能提升，盡管在Polbooks和Email網(wǎng)絡(luò)數(shù)據(jù)集中相比τKS優(yōu)勢不明顯，但在網(wǎng)絡(luò)數(shù)據(jù)集中的總體評估效果仍為最優(yōu)。對于τDC、τCC和τH而言，在大部分網(wǎng)絡(luò)數(shù)據(jù)集中τC(IGC)與其之間的η均大于0，即在這些網(wǎng)絡(luò)數(shù)據(jù)集中IGC方法的評估準(zhǔn)確性優(yōu)于現(xiàn)有方法。

4.2.2 單調(diào)性分析

單調(diào)性用于評估排序節(jié)點(diǎn)的唯一性，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)都被賦予不同的權(quán)值時(shí)所用評估方法的單調(diào)性最強(qiáng)，而當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)都被賦予相同的權(quán)值時(shí)，所用評估方法的單調(diào)性最弱。本文計(jì)算DC、BC、CC、KS、H和IGH方法的M值，如表4所示。可以看出，IGC方法在所有真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中的M值均優(yōu)于DC、CC、KS和H方法。然而在人工網(wǎng)絡(luò)數(shù)據(jù)集中，IGC和BC方法均表現(xiàn)出較好的單調(diào)性，但從整體上看，IGC方法單調(diào)性更優(yōu)，主要原因?yàn)镮GC方法相比現(xiàn)有方法能將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為更多不同的等級。

表4 網(wǎng)絡(luò)數(shù)據(jù)集中不同評估方法的M 值比較Table 4 Comparison of M value of different evaluation methods in the network datasets

5 結(jié)束語

本文根據(jù)鄰居節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)并結(jié)合萬有引力定律，提出一種基于改進(jìn)重力中心性的節(jié)點(diǎn)重要性評估方法。由于SIR傳播模型的Kendall相關(guān)系數(shù)和單調(diào)性與節(jié)點(diǎn)真實(shí)傳播能力之間有較強(qiáng)關(guān)聯(lián)性，且對于具有不同傳播能力的節(jié)點(diǎn)有較強(qiáng)的區(qū)分能力，因此通過實(shí)驗(yàn)驗(yàn)證了該方法的正確性與有效性，并表明其能準(zhǔn)確地評估節(jié)點(diǎn)的重要性。下一步可將多種節(jié)點(diǎn)重要性靜態(tài)評估方法與動(dòng)態(tài)網(wǎng)絡(luò)相結(jié)合，利用節(jié)點(diǎn)屬性關(guān)聯(lián)特性實(shí)現(xiàn)節(jié)點(diǎn)重要性排序。