基于有效距離的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)影響力度量方法

馬媛媛,韓 華

(武漢理工大學(xué)理學(xué)院，武漢 430070)

0 引言

現(xiàn)實(shí)世界中的許多復(fù)雜系統(tǒng)可以抽象為復(fù)雜網(wǎng)絡(luò)模型。近年來(lái)，網(wǎng)絡(luò)科學(xué)研究受到了物理、數(shù)學(xué)、化學(xué)、醫(yī)學(xué)、生物學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域?qū)W者的廣泛關(guān)注[1-3]，其中度量節(jié)點(diǎn)的影響力并挖掘關(guān)鍵節(jié)點(diǎn)是網(wǎng)絡(luò)科學(xué)的重要研究之一。一方面，關(guān)鍵節(jié)點(diǎn)的數(shù)量通常較少，但對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和功能有著很大的影響，例如，在電力網(wǎng)絡(luò)中某主要區(qū)段的線路故障將導(dǎo)致整個(gè)網(wǎng)絡(luò)癱瘓；另一方面，識(shí)別關(guān)鍵節(jié)點(diǎn)在檢測(cè)金融風(fēng)險(xiǎn)、防止恐怖襲擊、控制流行病傳播等方面有廣泛的應(yīng)用價(jià)值[4-5]。

目前，許多經(jīng)典的中心性被提出，其中度中心性[6]、介數(shù)中心性[7]、接近中心性[8]、特征向量中心性[9]、PageRank[10]和k-shell中心性[11]等在度量節(jié)點(diǎn)影響力中得到了廣泛的應(yīng)用。現(xiàn)有的算法研究可分為三大類：一是基于網(wǎng)絡(luò)局部信息，如度中心性，僅利用節(jié)點(diǎn)本身的信息，時(shí)間復(fù)雜度低，適合于大規(guī)模網(wǎng)絡(luò)，但忽略網(wǎng)絡(luò)的大部分信息，精度較低；二則基于網(wǎng)絡(luò)全局信息，如介數(shù)中心性、接近中心性和特征向量中心性，根據(jù)整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)特征確定節(jié)點(diǎn)的傳播能力，具有較高的準(zhǔn)確性，但計(jì)算復(fù)雜度較高，不適合大規(guī)模網(wǎng)絡(luò)；此外，近年來(lái)出現(xiàn)了一種介于局部中心性與全局中心性之間的折衷方法—半局部中心性算法，具有精度高、時(shí)間復(fù)雜度低、考慮的信息較全面的特點(diǎn)。例如，胡鋼等[12]通過(guò)研究節(jié)點(diǎn)與其直接鄰居及間接鄰居之間的關(guān)聯(lián)關(guān)系，提出了基于鄰接信息熵的網(wǎng)絡(luò)節(jié)點(diǎn)重要性識(shí)別算法；Wang等[13]基于網(wǎng)絡(luò)中節(jié)點(diǎn)與多階鄰居的殼值，利用向量形式表示節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的相對(duì)重要性,提出了多階鄰居殼數(shù)向量中心性算法。

近幾年，學(xué)者們認(rèn)為用單一的中心性算法來(lái)描述網(wǎng)絡(luò)節(jié)點(diǎn)的重要性是片面的，嘗試從不同角度來(lái)度量節(jié)點(diǎn)的重要性，并將多屬性決策方法(MCDM)[14-15]和機(jī)器學(xué)習(xí)方法[16]應(yīng)用到節(jié)點(diǎn)的影響力度量上。如Bian等[17]將多種不同的中心性作為復(fù)雜網(wǎng)絡(luò)的多屬性度量指標(biāo)，利用層次分析法(AHP)對(duì)多屬性指標(biāo)進(jìn)行聚合，評(píng)價(jià)節(jié)點(diǎn)的影響力；郭強(qiáng)等[18]采用多屬性排序方法(TOPSIS)對(duì)時(shí)序網(wǎng)絡(luò)不同時(shí)間片段節(jié)點(diǎn)的影響力進(jìn)行綜合評(píng)價(jià)；韓忠明等[19]選取了7個(gè)經(jīng)典節(jié)點(diǎn)重要性度量指標(biāo),并引入List Net排序?qū)W習(xí)方法構(gòu)建了一個(gè)基于結(jié)構(gòu)洞的節(jié)點(diǎn)重要性排序綜合評(píng)價(jià)方法。

節(jié)點(diǎn)的影響力是指節(jié)點(diǎn)傳播信息的能力，而信息傳播依附于具體的網(wǎng)絡(luò)，故網(wǎng)絡(luò)結(jié)構(gòu)必定會(huì)對(duì)信息的傳播過(guò)程產(chǎn)生影響，進(jìn)而影響節(jié)點(diǎn)的重要性，然而上述研究并未充分考慮網(wǎng)絡(luò)結(jié)構(gòu)特征對(duì)節(jié)點(diǎn)重要性的影響。因此，本文基于網(wǎng)絡(luò)結(jié)構(gòu)特征引入有效距離函數(shù)，同時(shí)從節(jié)點(diǎn)和鄰居兩個(gè)角度度量節(jié)點(diǎn)的傳播能力，提出一種新的半局部中心性度量方法，然后根據(jù)熵權(quán)法計(jì)算權(quán)重，并用VIKOR方法對(duì)節(jié)點(diǎn)的重要性進(jìn)行排序。

1 相關(guān)研究

假設(shè)無(wú)向網(wǎng)絡(luò)G=(V,E)包含|V|=N個(gè)節(jié)點(diǎn)和|E|=M條邊，網(wǎng)絡(luò)的鄰接矩陣用A=(aij)N×N表示，當(dāng)節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間存在連接時(shí)aij=1，否則aij=0。

1.1 度中心性

度為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基本參數(shù)，度中心性(DC)是一種簡(jiǎn)單直觀的排序方法，節(jié)點(diǎn)的度表示節(jié)點(diǎn)vi的鄰居個(gè)數(shù)，其中τ(i)表示節(jié)點(diǎn)vi的鄰居集合。

(1)

1.2 接近中心性

接近中心性(CC)反應(yīng)節(jié)點(diǎn)在網(wǎng)絡(luò)中居于中心的程度，式(2)中dij表示節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的距離。

(2)

1.3 介數(shù)中心性

(3)

1.4 k-shell中心性

k-shell分解是一種粗粒度的網(wǎng)絡(luò)分解算法，主要根據(jù)節(jié)點(diǎn)的度數(shù)的更新不斷地刪除網(wǎng)絡(luò)中的節(jié)點(diǎn)，進(jìn)而得到節(jié)點(diǎn)的核值，一般用字母ks表示節(jié)點(diǎn)的核值，分解過(guò)程如下：

1)首先計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)，刪除節(jié)點(diǎn)度數(shù)k≤1的節(jié)點(diǎn)及其相連的邊，更新網(wǎng)絡(luò)并重新計(jì)算度數(shù)，再刪除度k≤1的節(jié)點(diǎn)，直到網(wǎng)絡(luò)中不存在度數(shù)k≤1的節(jié)點(diǎn)，記這些刪除的節(jié)點(diǎn)ks=1。

2)遞歸地刪除網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)k≤2的節(jié)點(diǎn)及其相連的邊，之后更新網(wǎng)絡(luò)并重新計(jì)算度，記ks=2。

3)重復(fù)上述過(guò)程，直到每個(gè)節(jié)點(diǎn)都被賦予ks值。

1.5 GIN中心性

GIN中心性[20]是一種同時(shí)考慮節(jié)點(diǎn)和鄰居信息的節(jié)點(diǎn)重要性評(píng)估算法，式(4)中ki表示節(jié)點(diǎn)vi的度，dij表示節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的距離。

(4)

2 一種新的節(jié)點(diǎn)影響力度量算法

2.1 有效距離

任意相鄰節(jié)點(diǎn)之間的距離設(shè)置為1，是計(jì)算節(jié)點(diǎn)間距離最基本的方法，但它與現(xiàn)實(shí)網(wǎng)絡(luò)中信息流交互的原理相違背。信息通過(guò)節(jié)點(diǎn)后，根據(jù)節(jié)點(diǎn)與鄰居的連接情況，將信息流分配到不同的路徑，故任意兩節(jié)點(diǎn)間距離不應(yīng)總相等。2013年,Brockmann和Helbing等[21]基于網(wǎng)絡(luò)拓?fù)涞木植啃畔?，提出了兩個(gè)連通節(jié)點(diǎn)之間的有效距離,將任意兩個(gè)節(jié)點(diǎn)vi和vj間的有效距離定義為

d(i,j)=1-logPji

(5)

2.2 SN中心性

考慮到節(jié)點(diǎn)的重要性不僅與節(jié)點(diǎn)本身有關(guān)，還與鄰居節(jié)點(diǎn)的信息有關(guān)，本文從兩個(gè)角度考慮節(jié)點(diǎn)的重要性，提出了一種基于節(jié)點(diǎn)度值和有效距離量化節(jié)點(diǎn)影響力的中心性—SN中心性。

從節(jié)點(diǎn)的本身考慮，用度屬性來(lái)表征節(jié)點(diǎn)的重要性，定義為

(6)

從鄰居角度考慮，用鄰居度與相對(duì)距離的比值來(lái)表征節(jié)點(diǎn)的重要性，定義為

(7)

為接近真實(shí)傳播情況,式(7)中τ(i)表示節(jié)點(diǎn)的兩步內(nèi)鄰居。避免兩角度結(jié)合的主觀性,本文采用VIKOR方法[22]得到距理想解最近的折衷可行解SN,權(quán)重依據(jù)熵權(quán)法確定,具體過(guò)程如下:

1)根據(jù)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的SEi和NEi值，建立一個(gè)決策矩陣D。

(8)

2)標(biāo)準(zhǔn)化決策矩陣D,并構(gòu)建標(biāo)準(zhǔn)矩陣R。

(9)

(10)

3)計(jì)算第j個(gè)屬性的熵。

(11)

4)則第j個(gè)準(zhǔn)則的權(quán)重為

(12)

5)確定出正理想解r+和負(fù)理想解r-。

(13)

其中,J和J′是效益標(biāo)準(zhǔn)集(標(biāo)準(zhǔn)越高，節(jié)點(diǎn)越重要)和成本標(biāo)準(zhǔn)集(條件越高，節(jié)點(diǎn)越不重要)，文中這兩個(gè)標(biāo)準(zhǔn)都是效益標(biāo)準(zhǔn)。

6)各節(jié)點(diǎn)的群體效用值Si和個(gè)體遺憾值Ri按式(14)計(jì)算:

(14)

7)計(jì)算節(jié)點(diǎn)i的VIKOR重要度。

SNi=v(Si-S-)/(S+-S-)+(1-v)(Ri-R-)/(R+-R-)

(15)

S+=maxSi,S-=minSi,R+=maxRi,R-=minRi

(16)

其中,v為決策機(jī)制系數(shù)，取v=0.5，兼顧群體效用最大化和個(gè)體遺憾最小化。SNi是第i個(gè)節(jié)點(diǎn)重要性的綜合評(píng)價(jià)值，SNi越小則第i個(gè)節(jié)點(diǎn)越重要。節(jié)點(diǎn)重要性的向量可表示為

Te=[SN1,…,SNi,…,SNn]

(17)

8)根據(jù)節(jié)點(diǎn)的重要性值將Te升序排列。

(18)

2.3 算例分析

示例網(wǎng)絡(luò)中節(jié)點(diǎn)在不同排序方法下的排序結(jié)果如表1所示，其中最后一列補(bǔ)充了各節(jié)點(diǎn)SN算法的值。由表1可知，DC算法給予節(jié)點(diǎn)3、節(jié)點(diǎn)7相同排名，但刪除節(jié)點(diǎn)7后，圖1將不是一個(gè)連通圖，故節(jié)點(diǎn)7的影響力應(yīng)強(qiáng)于節(jié)點(diǎn)3；KS算法區(qū)分節(jié)點(diǎn)的能力較差；BC算法給予8個(gè)節(jié)點(diǎn)相同的排名，表明算法的穩(wěn)定性較差；CC算法給節(jié)點(diǎn)8的排名靠前，而其他算法中節(jié)點(diǎn)8則處于較后的排名，是因其側(cè)重與其他節(jié)點(diǎn)間距離而出現(xiàn)的偏差；GNI、SN算法的排序結(jié)果較優(yōu)，但GNI算法給出節(jié)點(diǎn)8的排名低于節(jié)點(diǎn)10，從兩節(jié)點(diǎn)的連邊情況看，節(jié)點(diǎn)8應(yīng)優(yōu)于節(jié)點(diǎn)10的排名，故SN算法的排序結(jié)果更優(yōu)。

圖1 示例

表1 示例網(wǎng)絡(luò)的排序結(jié)果

2.4 算法流程

算法在引入有效距離的基礎(chǔ)上，從兩個(gè)角度考慮了節(jié)點(diǎn)重要性。已知網(wǎng)絡(luò)的鄰接矩陣A，具體算法步驟如下:

2)根據(jù)式(6)和式(7)分別計(jì)算各角度下節(jié)點(diǎn)的重要性；

3)構(gòu)建決策矩陣D并將其標(biāo)準(zhǔn)化得到標(biāo)準(zhǔn)化矩陣R;

4)根據(jù)式(11)計(jì)算各重要性的信息熵;

5)根據(jù)式(12)計(jì)算權(quán)重;

6)根據(jù)式(13)確定正理想解r+和負(fù)理想解r-;

7)根據(jù)式(14)計(jì)算各節(jié)點(diǎn)的群體效用值Si和個(gè)體遺憾值Ri;

8)根據(jù)式(15)計(jì)算VIKOR重要度，并得到Te;

9)將Te按升序排列,得到節(jié)點(diǎn)排序。

3 評(píng)價(jià)標(biāo)準(zhǔn)

3.1 SIR模型

為衡量各種指標(biāo)影響力排序結(jié)果的準(zhǔn)確性，需已知節(jié)點(diǎn)的實(shí)際影響力排序。SIR(Susceptible-Infected-Recovered)模型[23]被廣泛用于描述疾病、謠言、信息傳播過(guò)程，故采用SIR模型對(duì)傳播過(guò)程進(jìn)行模擬，得到節(jié)點(diǎn)影響力的標(biāo)準(zhǔn)排名σ。在SIR模型中，節(jié)點(diǎn)處于易感狀態(tài)S，感染狀態(tài)I，恢復(fù)狀態(tài)R三種狀態(tài)之一。個(gè)體被感染后以概率λ被治愈，治愈后對(duì)該疾病免疫,不再被感染。初始階段，設(shè)定網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)為感染狀態(tài)，其他節(jié)點(diǎn)為易感狀態(tài)。傳播過(guò)程中，每個(gè)處于感染狀態(tài)的節(jié)點(diǎn)試圖用感染概率α(α也稱為傳播概率)感染其處于易感狀態(tài)的鄰居，然后以概率β進(jìn)入恢復(fù)狀態(tài)，且不再被感染。這個(gè)過(guò)程重復(fù)進(jìn)行，直到網(wǎng)絡(luò)中沒(méi)有受感染的節(jié)點(diǎn)。不失一般性,本文取傳播概率在傳播閾值附近，恢復(fù)概率β為1。Φ′為網(wǎng)絡(luò)中最后處于恢復(fù)狀態(tài)的節(jié)點(diǎn)總數(shù)，等同于初始感染節(jié)點(diǎn)的影響力。為了保證計(jì)算結(jié)果的可靠性，取M次試驗(yàn)的平均值作為節(jié)點(diǎn)的實(shí)際影響力Φ(i)。

(19)

3.2 評(píng)估指標(biāo)

3.2.1 區(qū)分度

TRF指標(biāo)[24]的數(shù)值反映某種指標(biāo)下節(jié)點(diǎn)得分的內(nèi)部情況，TRF=0表示所有節(jié)點(diǎn)被賦予不同的中心性值,TRF=1表示所有節(jié)點(diǎn)被賦予相同的中心性值,故TRF指標(biāo)值越小，節(jié)點(diǎn)獲得相同得分的數(shù)量越少，算法效果越好。TRF指標(biāo)的定義如式(20)所示：

(20)

其中,n為將要排序數(shù)據(jù)的個(gè)數(shù)，一般是網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，ns為數(shù)據(jù)中獲得相同得分的節(jié)點(diǎn)的數(shù)目。

3.2.2 相關(guān)性

實(shí)驗(yàn)采用Kendall tau相關(guān)系數(shù)[25]衡量各指標(biāo)排序結(jié)果準(zhǔn)確性，其表達(dá)式為

(21)

4 實(shí)驗(yàn)數(shù)據(jù)及分析

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

為評(píng)估提出算法的效果，實(shí)驗(yàn)選取6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)，包括Karate[26]，Dolphin[27]，Jazz[28]，F(xiàn)ootball[29]，USAir[30]，Netscience[31]。這些網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)統(tǒng)計(jì)特征如表2所示。其中，N與M分別為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)與連邊數(shù)，C為網(wǎng)絡(luò)集聚系數(shù)，〈k〉為節(jié)點(diǎn)平均度。

表2 6個(gè)真實(shí)網(wǎng)絡(luò)的拓?fù)鋮?shù)

4.2 結(jié)果及分析

在6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上，將提出的SN中心性分別與度中心性、K-Shell中心性、介數(shù)中心性、接近中心性、GIN中心性進(jìn)行對(duì)比。

不同指標(biāo)值的排序即節(jié)點(diǎn)傳播能力的排名，當(dāng)排名結(jié)果出現(xiàn)某一排名下頻率較高時(shí)，說(shuō)明該排名下的節(jié)點(diǎn)眾多，對(duì)應(yīng)的中心性性能較差；當(dāng)排名長(zhǎng)度相對(duì)更接近網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)時(shí)，排名結(jié)果分散，中心性性能較好。圖2展示了6個(gè)真實(shí)網(wǎng)絡(luò)中各指標(biāo)下節(jié)點(diǎn)的排名分布情況,顯然,DC和KS在6個(gè)網(wǎng)絡(luò)中排名分布的高頻數(shù)高于其他中心性，且排名長(zhǎng)度較短，表明DC和KS區(qū)分節(jié)點(diǎn)的傳播能力較弱。相比之下，DC、CC比BC、CC排名分布較好。幾乎所有情況下，GIN和SN的排名分布似一條直線，且排名分布長(zhǎng)度與網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)接近，表明其排名分布效果很好；同時(shí)從排名頻率高于直線的部分觀察，SN更優(yōu)一些。

圖2 6個(gè)真實(shí)網(wǎng)絡(luò)中各指標(biāo)下節(jié)點(diǎn)的排名分布情況

不同指標(biāo)在不同網(wǎng)絡(luò)數(shù)據(jù)的TRF值見(jiàn)表3，結(jié)果表明所提出的SN算法在Karate，Dolphin，F(xiàn)ootball，Netscience網(wǎng)絡(luò)中得到的排序具有最高TRF值，即SN算法對(duì)節(jié)點(diǎn)排名有較好的差異性。SN算法在Jazz，USAir網(wǎng)絡(luò)中單調(diào)性值也處于第二位，優(yōu)于DC，KS，BC，CC的排序結(jié)果。

表3 不同指標(biāo)在不同網(wǎng)絡(luò)數(shù)據(jù)的TRF值

各個(gè)指標(biāo)在不同的傳播率下的排序準(zhǔn)確性如圖3所示，當(dāng)傳播率較小時(shí)，度中心性的準(zhǔn)確性較高，是因?yàn)閭鞑ヂ瘦^小時(shí)，單節(jié)點(diǎn)開始的SIR傳播過(guò)程易局限于節(jié)點(diǎn)的局部鄰域，此時(shí)節(jié)點(diǎn)的度越大，感染到的節(jié)點(diǎn)也越多。當(dāng)傳播率變大，接近傳播閾值時(shí)，SN中心性的準(zhǔn)確性逐漸高于前者，說(shuō)明同時(shí)考慮節(jié)點(diǎn)與鄰居的度與有效距離更接近于真實(shí)結(jié)果。

圖3 6個(gè)真實(shí)網(wǎng)絡(luò)中不同指標(biāo)評(píng)估準(zhǔn)確性對(duì)比

表4 各指標(biāo)下Karate網(wǎng)絡(luò)中排名前五的節(jié)點(diǎn)

表5 各指標(biāo)下Dolphin網(wǎng)絡(luò)中排名前五的節(jié)點(diǎn)

表6 各指標(biāo)下Football網(wǎng)絡(luò)中排名前五的節(jié)點(diǎn)

表7 各指標(biāo)下Jazz網(wǎng)絡(luò)中排名前五的節(jié)點(diǎn)

表8 各指標(biāo)下Usair網(wǎng)絡(luò)中排名前五的節(jié)點(diǎn)

表4～表9分別比較6個(gè)不同網(wǎng)絡(luò)中各中心性度量排名前5的節(jié)點(diǎn)。KS算法將較多節(jié)點(diǎn)分解在同一層，故未在此比較。SN算法融合了DC，BC，CC，GIN四者中出現(xiàn)頻率高的節(jié)點(diǎn)，排名的相關(guān)性較高。

表9 各指標(biāo)下Netscience網(wǎng)絡(luò)中排名前五的節(jié)點(diǎn)

5 結(jié)論

準(zhǔn)確度量復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性對(duì)于加快積極信息在網(wǎng)絡(luò)中的傳播、預(yù)防網(wǎng)絡(luò)攻擊、抑制傳染病的爆發(fā)具有現(xiàn)實(shí)意義。本文考慮到任意相鄰節(jié)點(diǎn)間距離不等的情況，引入相對(duì)距離，提出了考慮節(jié)點(diǎn)度與節(jié)點(diǎn)間距離的中心性，并用熵權(quán)法和VIKOR法對(duì)節(jié)點(diǎn)重要性進(jìn)行排序。在6個(gè)實(shí)際網(wǎng)絡(luò)進(jìn)行了數(shù)值仿真，驗(yàn)證所提方法的可行性和有效性。實(shí)驗(yàn)結(jié)果表明，該方法不僅可以得到更準(zhǔn)確的排序結(jié)果，而且有效減少了相同排序節(jié)點(diǎn)的出現(xiàn)頻率。