基于度與H指數(shù)擴展的復(fù)雜網(wǎng)絡(luò)節(jié)點排序方法

盧鵬麗, 于 洲

(蘭州理工大學(xué) 計算機與通信學(xué)院, 甘肅 蘭州 730050)

在現(xiàn)實生活中,有很多網(wǎng)絡(luò)都是以復(fù)雜網(wǎng)絡(luò)(complex network)的形式存在,例如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、生命科學(xué)領(lǐng)域的各種網(wǎng)絡(luò)等.復(fù)雜網(wǎng)絡(luò)中識別有影響力的節(jié)點作為網(wǎng)絡(luò)科學(xué)的重要研究內(nèi)容之一,己經(jīng)被應(yīng)用到諸多領(lǐng)域,特別在各類傳播行為(如病毒式營銷[1]、流行病傳播與控制[2]、社交網(wǎng)絡(luò)分析[3])的研究中表現(xiàn)得尤為重要.

所謂有影響力的節(jié)點是指相比于網(wǎng)絡(luò)中其他節(jié)點能夠?qū)W(wǎng)絡(luò)的連通性、魯棒性、平均距離以及同步等產(chǎn)生重要影響力的一類特殊節(jié)點.當(dāng)一些有影響力的節(jié)點受到攻擊破壞時,會影響到網(wǎng)絡(luò)的整體結(jié)構(gòu)和功能.因此,如何識別網(wǎng)絡(luò)中有影響力的節(jié)點己成為近年來的熱點問題.

國內(nèi)外學(xué)者對節(jié)點影響力的評估進行了大量研究,己經(jīng)有很多用于識別節(jié)點影響力的中心性指標(biāo),如度中心性[4]、介數(shù)中心性[5]、緊密中心性[6]、K-shell中心性[7]、H指數(shù)中心性[8]和聚類系數(shù)[9]等.度中心性是目前最簡單的一種評估方法,該方法通過計算鄰居節(jié)點的數(shù)量來衡量其影響力,即節(jié)點的鄰居節(jié)點越多,其影響力越大.然而,該方法雖然簡單直觀,相關(guān)算法的時間復(fù)雜度也很低,但只考慮了節(jié)點的局部屬性,因此具有一定的局限性.介數(shù)中心性和緊密中心性都是全局中心性方法,它們都需要遍歷整個網(wǎng)絡(luò)來確定節(jié)點的影響力,時間復(fù)雜度較大,因此全局中心性方法效率較低,不適合于大型的復(fù)雜網(wǎng)絡(luò).H指數(shù)中心性雖然考慮了相鄰節(jié)點的影響力,但卻忽略了自身的度以及網(wǎng)絡(luò)上部分結(jié)構(gòu)信息.

如果只考慮節(jié)點本身的重要性來確定其中心性,則可能忽略網(wǎng)絡(luò)上的部分結(jié)構(gòu)信息,降低了識別網(wǎng)絡(luò)中節(jié)點影響力的準(zhǔn)確性.例如,對于圖1網(wǎng)絡(luò)中的一些節(jié)點,本文通過SIR模型取1 000次傳播過程的平均值作為節(jié)點的影響力(SC),根據(jù)網(wǎng)絡(luò)節(jié)點SC值可知節(jié)點5的影響力大于節(jié)點10,然而,節(jié)點5和節(jié)點10的度都是6,即其度中心性都是6.出現(xiàn)這種情況的原因在于節(jié)點5的相鄰節(jié)點比節(jié)點10的相鄰節(jié)點具有更大的影響力.

H指數(shù)是赫西(Hirsch)[10]在2005年提出的,是用于衡量學(xué)者出版物的數(shù)量和引文影響的一個經(jīng)典指標(biāo).近年來,有學(xué)者引入H指數(shù)來衡量網(wǎng)絡(luò)中節(jié)點的影響力.例如,Li等[11]驗證了H指數(shù)在許多現(xiàn)實世界網(wǎng)絡(luò)中衡量節(jié)點影響力的有效性.然而,在一些網(wǎng)絡(luò)中用H指數(shù)中心性識別網(wǎng)絡(luò)中節(jié)點的影響力時,存在著一些節(jié)點具有相同的H指數(shù)值,但這些節(jié)點的真實影響力卻不同.如圖1,節(jié)點5和節(jié)點9的H指數(shù)值均為4,但節(jié)點9的真實影響力(SC)卻大于節(jié)點5,其主要原因在于計算節(jié)點H指數(shù)值時,忽略了鄰居節(jié)點中度較小的節(jié)點以及自身的度,這使得H指數(shù)中心性無法區(qū)分這些節(jié)點的真實影響力.

本文在H指數(shù)與度中心性的啟發(fā)下,提出了一種基于度與H指數(shù)擴展的局部中心性方法來識別網(wǎng)絡(luò)中節(jié)點的影響力,稱之為局部DH指數(shù)中心性.該方法同時考慮了節(jié)點自身的度、H指數(shù)和鄰居節(jié)點的H指數(shù)三個因素.一方面,一個節(jié)點的H指數(shù)取決于鄰居節(jié)點的度;另一方面,其鄰居節(jié)點的H指數(shù)取決于鄰居節(jié)點的鄰居的度.本文通過病毒傳染模型(SIR)以及單調(diào)函數(shù)M來評價局部度與H指數(shù)中心性在識別節(jié)點影響力方面的性能.實驗結(jié)果表明,較一些常用的中心性方法,本文的方法在一些實際網(wǎng)絡(luò)以及無標(biāo)度網(wǎng)絡(luò)(BA)中能更有效地識別節(jié)點的影響力.

1 相關(guān)研究及本文算法

實驗中要用到五種經(jīng)典的中心性指標(biāo),即度中心性(DC)[4]、介數(shù)中心性(BC)[5]、緊密中心性(CC)[6]、K-shell中心性(Ks)[7]以及H指數(shù)中心性(H)[8].

假設(shè)每個網(wǎng)絡(luò)都可以表示為G=(V,E),其中節(jié)點集V={v1,v2,…,v|V|}表示個體,邊集E={e1,e2,…,e|E|}表示個體與個體之間的關(guān)系.如果兩個節(jié)點vi和vj之間有關(guān)系,則eij=1,否則eij=0.di表示節(jié)點vi的度,為其鄰居節(jié)點的個數(shù),這些鄰居節(jié)點的集合由Ni表示,各中心性指標(biāo)介紹如下.

1.1 度中心性

在網(wǎng)絡(luò)中節(jié)點vi的度是指在網(wǎng)絡(luò)中與節(jié)點vi直接相連的節(jié)點個數(shù),節(jié)點的鄰居節(jié)點越多,節(jié)點越重要.節(jié)點vi的度中心性為

(1)

式中:N表示網(wǎng)絡(luò)中的節(jié)點總數(shù).

1.2 介數(shù)中心性

在網(wǎng)絡(luò)中節(jié)點vi的介數(shù)中心性是指網(wǎng)絡(luò)中所有最短路徑中經(jīng)過節(jié)點vi的路徑總數(shù)占所有節(jié)點對的最短路徑總數(shù)的比例,因而在運行此算法時需要遍歷整個網(wǎng)絡(luò).節(jié)點vi的介數(shù)中心性為

(2)

式中:Ljk是指每一對節(jié)點vj與vk之間的最短路徑數(shù);Ljik是指節(jié)點vj與vk最短路徑中經(jīng)過節(jié)點vi的路徑總數(shù).

1.3 緊密中心性

在網(wǎng)絡(luò)中節(jié)點vi的緊密中心性值是節(jié)點vi到網(wǎng)絡(luò)中其他節(jié)點的最短路徑長度的倒數(shù)之和,因而在運行此算法時需要遍歷整個網(wǎng)絡(luò).節(jié)點vi的緊密中心性為

(3)

式中:dij表示節(jié)點vi與vj之間的最短路徑長度.

1.4 K-shell中心性

K-shell中心性是根據(jù)節(jié)點的位置度量節(jié)點影響力.K-shell分解算法通過迭代刪除節(jié)點,給網(wǎng)絡(luò)中所有節(jié)點賦予K-shell值.算法思想如下：

1) 首先,從圖中刪除所有度為1的節(jié)點以及相關(guān)的連邊,若剩下的節(jié)點里,仍有度值為1的節(jié)點,則繼續(xù)上述過程,直到圖中所有節(jié)點的度值都大于1,然后,將所有刪除的節(jié)點的K-shell值記為1.

2) 刪除度為2的節(jié)點,直到?jīng)]有度為2的節(jié)點.然后將所有刪除的節(jié)點的K-shell值記為2,這個過程一直持續(xù)到所有節(jié)點都刪除為止.顯然,K-shell值越大的節(jié)點越接近網(wǎng)絡(luò)的中心位置,節(jié)點影響力越大.

1.5 H指數(shù)中心性

H指數(shù)中心性是利用H指數(shù)的概念,通過考慮鄰居節(jié)點的度來確定節(jié)點的中心性.節(jié)點vi的H指數(shù)中心性為

H-index(vi)=H(du1,du2,du3,…,dudj)

(4)

式中:(u1,u2,u3,…,udj)為節(jié)點vi的鄰居節(jié)點;dui表示節(jié)點ui的度;函數(shù)H(du1,du2,du3,…,dudj)返回值y,使得du1,du2,du3,…,dudj中有y個值大于等于y.

除了上述方法外,近來學(xué)者還提出了一些新方法.Hu等[12]試圖通過同時使用多個中心性指標(biāo)來確定節(jié)點的影響力,Wang等[13]提出了一種混合的中心性度量方法用于描述多層網(wǎng)絡(luò)中節(jié)點的影響力,Wang等[14]提出了衡量加權(quán)圖中節(jié)點影響能力的方法,Fu等[15]提出了一種基于模量密度譜優(yōu)化的中心性度量方法.

本文考慮了度中心性與H指數(shù)中心性在識別網(wǎng)絡(luò)中節(jié)點影響力的局限性,并在此基礎(chǔ)上提出了局部DH指數(shù)中心性.

1.6 局部DH指數(shù)中心性

由式⑷可知,H指數(shù)中心性通過考慮鄰居節(jié)點的度來確定節(jié)點的中心性,但忽略了鄰居節(jié)點的部分信息,例如完全忽略了度小于y的鄰居節(jié)點,導(dǎo)致確定節(jié)點影響力的準(zhǔn)確性降低.如圖1,節(jié)點10的H指數(shù)中心性H-index(10)=2,節(jié)點12的H指數(shù)中心性H-index(12)=3.然而,根據(jù)網(wǎng)絡(luò)節(jié)點的影響力SC值可知,節(jié)點10的真實影響力大于節(jié)點12.考慮到H指數(shù)的不足,本文提出了一種基于度與H指數(shù)擴展的局部中心性方法.該方法既繼承了H指數(shù)中心性與度中心性的所有優(yōu)點,又解決了H指數(shù)中心性的不足.節(jié)點vi的DH指數(shù)值定義如下：

(5)

式中:a,b是[0,1]的可調(diào)參數(shù),經(jīng)過實驗,本文取a=0.15,b=0.15;D(i)表示節(jié)點vi的度;Hindex(i)表示節(jié)點vi的H指數(shù);Ni是節(jié)點vi的所有相鄰節(jié)點的集合.由式(5)可知,該方法同時考慮了節(jié)點自身以及鄰居節(jié)點和鄰居的鄰居節(jié)點;該方法分為三部分,第一部分是節(jié)點自身的度,第二部分是節(jié)點的H指數(shù),它根據(jù)具有較高度的鄰居節(jié)點的數(shù)量來評估節(jié)點的影響力.然而,對于某些網(wǎng)絡(luò),H指數(shù)中心性識別節(jié)點的影響力的能力是有限的,有可能存在多個節(jié)點具有相同的H指數(shù)值,因此,也考慮了鄰居節(jié)點的H指數(shù),進而,第三部分鄰居節(jié)點的H指數(shù)相加.

2 實驗數(shù)據(jù)與評估方法

2.1 數(shù)據(jù)集

為了檢驗本文方法的有效性,將其應(yīng)用于真實網(wǎng)絡(luò)和模擬網(wǎng)絡(luò),真實網(wǎng)絡(luò)包括：空手道俱樂部網(wǎng)絡(luò)(Karate)[16],海豚社會網(wǎng)絡(luò)(Dolphins)[17],爵士音樂家網(wǎng)絡(luò)(Jazz)[18],美國航空運輸網(wǎng)絡(luò)(USAir)[19],大學(xué)電子郵件網(wǎng)絡(luò)(Email)[20],聯(lián)合作者科學(xué)家網(wǎng)絡(luò)(Authorship)[21],芽殖酵母蛋白質(zhì)相互作用網(wǎng)絡(luò)(Yeast)[22].表1介紹了相關(guān)網(wǎng)絡(luò)的頂點數(shù)(|V|)、邊數(shù)(|E|)、閾值(βc)、平均度(average degree)、最大度(maximum degree)以及同配系數(shù)(assortativity).

表1 網(wǎng)絡(luò)數(shù)據(jù)集的一些統(tǒng)計特性Tab.1 Some statistical characteristics of network data sets

2.2 傳播模型

易感染-感染-恢復(fù)(SIR)傳播模型[23]被廣泛用于描述和模擬疫情或信息的傳播過程.本文采用SIR傳播模型來評估排序節(jié)點的真實影響力.在SIR傳播模型中,個體可以處于三種可能狀態(tài)之一：易感染狀態(tài)(S)、感染狀態(tài)(I)和恢復(fù)狀態(tài)(R).在易感染狀態(tài)下,此類個體一般為健康個體,但是可以被病毒感染.在感染狀態(tài)下,此類個體己經(jīng)被病毒感染,并具備感染其他健康個體的能力.在恢復(fù)狀態(tài)下,此類個體既不能感染其他個體,也不能被其他個體感染.

在SIR傳播模型中,網(wǎng)絡(luò)初始狀態(tài)時只有一個節(jié)點處于感染狀態(tài)(I),其余所有節(jié)點處于易感染狀態(tài)(S).然后,己感染的節(jié)點試圖以感染率β感染其他節(jié)點.在每個時間段,每個被感染的節(jié)點都會選擇繼續(xù)感染其他節(jié)點,或者根據(jù)Gillespie算法[24]進入恢復(fù)狀態(tài).這個過程重復(fù)進行,直到網(wǎng)絡(luò)中沒有受感染的節(jié)點.一個節(jié)點的影響力即為該節(jié)點在傳播過程可以感染的節(jié)點數(shù),進而,可以得到網(wǎng)絡(luò)中所有節(jié)點影響力的排序表.本文實驗取100次傳播過程的平均值作為節(jié)點的影響力.

本文實驗將SIR傳播模型得到的排序結(jié)果與各中心性方法計算得到的排序結(jié)果進行比較,中心性方法計算得到的結(jié)果越接近于SIR傳播模型得到的排序結(jié)果,說明該中心性方法的準(zhǔn)確性越高.

2.3 評價方法

本文用到了單調(diào)函數(shù)(M)[26]和肯德爾相關(guān)系數(shù)[27]兩種方法來評價本文所提方法識別網(wǎng)絡(luò)中節(jié)點影響力的有效性.下面將分別說明這兩種方法.

在本文中,單調(diào)函數(shù)用于檢驗各中心性方法識別網(wǎng)絡(luò)中不同影響力節(jié)點的能力,利用下式計算各中心性方法計算出網(wǎng)絡(luò)中節(jié)點影響力的排序表R的單調(diào)性：

(6)

式中:n為排序表R上的排序數(shù);nr為排序表R上元素為r的數(shù)量.M值的取值為[0,1],M值越大,相關(guān)中心性方法識別網(wǎng)絡(luò)中不同影響力節(jié)點的能力越強.

肯德爾相關(guān)系數(shù)用于評價兩個序列的相關(guān)程度,肯德爾相關(guān)系數(shù)T的取值范圍在-1到1之間,T值越接近1,表示兩個序列的相關(guān)性越高,T值為0表示兩個序列相互獨立.

假設(shè)兩個集合X和Y,其元素個數(shù)均為n,兩個集合取的第i(1≤i≤n)個值分別用xi和yi表示.X與Y中的對應(yīng)元素組成一個元素對集合XY,其中包含的元素為(xi,yi).對于集合中任意兩個元素(xi,yi)與(xj,yj),當(dāng)xi>xj且yi>yj或者當(dāng)xixj且yiyj時,這兩個元素就被認(rèn)為是不和諧對；當(dāng)出現(xiàn)xi=xj或者yi=yj時,這兩個元素既不是和諧對也不是不和諧對.

在本文中,兩個序列集合一個是通過SIR傳播模型識別網(wǎng)絡(luò)中節(jié)點的影響力得到的結(jié)果,另一個是通過中心性方法計算得到的排序結(jié)果.肯德爾相關(guān)系數(shù)T值越接近1,說明中心性方法計算得到的排序結(jié)果越接近SIR傳播模型得到的結(jié)果,從而說明中心性方法越準(zhǔn)確.肯德爾相關(guān)系數(shù)定義如下：

(7)

式中:nc表示和諧對的個數(shù);nd表示不和諧對的個數(shù).使用肯德爾系數(shù)計算利用SIR模型感染過程得到的排序結(jié)果與中心性方法計算得到的排序結(jié)果的相關(guān)性可以評價排序結(jié)果的準(zhǔn)確性.

3 結(jié)果分析

在實驗過程中用DC表示度中心性、BC表示介數(shù)中心性、CC表示緊密中心性、Ks表示K-shell中心性、H表示H指數(shù)中心性、DH表示局部DH指數(shù)中心性.

3.1 單調(diào)性

在第一個實驗中,根據(jù)單調(diào)函數(shù)(M)計算出不同網(wǎng)絡(luò)數(shù)據(jù)集上各中心性方法得到節(jié)點影響力排序表的M值,表2為實驗結(jié)果.從表2的結(jié)果可以看出,本文的方法除了在聯(lián)合作者科學(xué)家網(wǎng)絡(luò)中的單調(diào)性M值低于CC方法外,在其余6個網(wǎng)絡(luò)上的單調(diào)性M值都接近于1且高于其余5個中心性方法,因此,本文所提出的DH方法較其他幾個中心性能更好地識別網(wǎng)絡(luò)中不同影響力的節(jié)點.

表2 7個網(wǎng)絡(luò)數(shù)據(jù)集上不同中心性指標(biāo)的排序表的單調(diào)性M值Tab.2 Monotone M value of sorting tables with different centrality indexes on seven network data sets

3.2 準(zhǔn)確性

在第二個實驗中,為了驗證本文中的方法用于識別網(wǎng)絡(luò)中不同影響力節(jié)點的準(zhǔn)確性,利用式(7)計算出本文的中心性方法以及5個傳統(tǒng)的中心性,在識別7個真實網(wǎng)絡(luò)中節(jié)點影響力生成的排序表與在特定的感染率β下進行SIR傳播模型實驗計算出排序表的肯德爾相關(guān)系數(shù)T值.肯德爾系數(shù)T值越大,相關(guān)方法識別真實網(wǎng)絡(luò)中節(jié)點影響力的準(zhǔn)確性越高.從表3的實驗結(jié)果可以看出,本文方法的肯德爾相關(guān)系數(shù)T值高于其他5個中心性方法,因此,局部DH指數(shù)中心性方法能更準(zhǔn)確地識別網(wǎng)絡(luò)中節(jié)點的影響力.

表3 在7種不同規(guī)模的真實網(wǎng)絡(luò)中,節(jié)點影響力與各指標(biāo)的肯德爾相關(guān)系數(shù)TTab.3 Kendall correlation coefficient T values in seven real networks with different scales

在實驗過程中,為了減少感染率β對實驗結(jié)果的影響,SIR傳播模型中β的取值設(shè)置為0.01～0.10.本文實驗將中心性計算得到的結(jié)果和通過SIR傳播模型得到的結(jié)果進行相關(guān)性比較,并計算肯德爾相關(guān)系數(shù)T值,實驗結(jié)果如圖2所示.將各中心性方法在爵士音樂家網(wǎng)絡(luò)、美國航空運輸網(wǎng)絡(luò)、大學(xué)電子郵件網(wǎng)絡(luò)和芽殖酵母蛋白質(zhì)相互作用網(wǎng)絡(luò)中計算出的節(jié)點影響力排序表,與通過傳播模型(SIR)在不同的感染率β下計算出的排序表進行相關(guān)性比較,得出肯德爾相關(guān)系數(shù)T值.從圖2可以看出,對于爵士音樂家網(wǎng)絡(luò),DH方法和傳播模型的肯德爾系數(shù)T值一直優(yōu)于其余5個中心性方法.對于其余三個網(wǎng)絡(luò),當(dāng)感染率β較小時,DH方法的T值并不完全優(yōu)于其余5個中心性方法,但是隨著感染率β增大到閾值βc附近乃至大于βc時,DH方法卻明顯優(yōu)于其余中心性方法.這充分說明了較一些傳統(tǒng)的中心性方法,本文提出的局部DH指數(shù)中心性能更準(zhǔn)確地識別網(wǎng)絡(luò)中節(jié)點的影響力.

為了更好地驗證局部DH指數(shù)中心性的準(zhǔn)確性,本文還將其在無標(biāo)度網(wǎng)絡(luò)模型(BA)[28]中與其他中心方法進行了比較.BA模型生成網(wǎng)絡(luò)的主要步驟如下：首先,網(wǎng)絡(luò)從一個初始連接的m0節(jié)點網(wǎng)絡(luò)開始;然后,每次將每個新節(jié)點添加到網(wǎng)絡(luò)中,用m(m

4 結(jié)論

本文提出了一種基于局部度與H指數(shù)擴展的復(fù)雜網(wǎng)絡(luò)節(jié)點排序方法(局部DH指數(shù)中心性),該方法同時考慮了節(jié)點自身的度與H指數(shù)以及鄰居的H指數(shù),結(jié)合了度中心性與H指數(shù)中心性的優(yōu)點.為了驗證所提方法的有效性,首先,本文通過單調(diào)函數(shù)(M)驗證各中心性指標(biāo)識別網(wǎng)絡(luò)中不同影響力節(jié)點的能力,實驗在7個真實網(wǎng)絡(luò)中與其余5個中心性方法的結(jié)果比較,發(fā)現(xiàn)局部DH指數(shù)中心性更優(yōu)于其余5個中心性方法.然后,本文將所提方法應(yīng)用到7個真實復(fù)雜網(wǎng)絡(luò)以及無標(biāo)度網(wǎng)絡(luò)模型(BA)中,并且使用SIR傳播模型模擬傳播過程,使用肯德爾相關(guān)系數(shù)計算各中心性方法得到的排序結(jié)果和SIR傳播模型得到的排序結(jié)果的相關(guān)性.通過對比發(fā)現(xiàn),局部DH指數(shù)中心性更能準(zhǔn)確地識別網(wǎng)絡(luò)中有影響力的節(jié)點.