楊松青 蔣沅? 童天馳 嚴(yán)玉為 淦各升

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

2) (南京理工大學(xué)自動(dòng)化學(xué)院,南京 210094)

復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的評(píng)估是網(wǎng)絡(luò)特性研究中的一項(xiàng)重要課題,相關(guān)研究具有廣泛的應(yīng)用.目前提出了許多方法來(lái)評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性,然而大多數(shù)方法都存在評(píng)估角度片面或者時(shí)間復(fù)雜度過(guò)高的不足.為了突破現(xiàn)有方法的局限性,本文提出了一種基于Tsallis 熵的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法.該方法兼顧節(jié)點(diǎn)的局部和全局拓?fù)湫畔?綜合考察節(jié)點(diǎn)的結(jié)構(gòu)洞特征和K 殼中心性,并充分考慮節(jié)點(diǎn)及其鄰域節(jié)點(diǎn)的影響.為了驗(yàn)證該方法的有效性,本文采用單調(diào)性指標(biāo)、SIR 模型和Kendall 相關(guān)系數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn),在8 個(gè)來(lái)自不同領(lǐng)域的真實(shí)網(wǎng)絡(luò)上與其他方法進(jìn)行比較.實(shí)驗(yàn)結(jié)果表明,此方法能更有效和準(zhǔn)確地評(píng)估網(wǎng)絡(luò)節(jié)點(diǎn)的重要性,可以顯著區(qū)分不同節(jié)點(diǎn)的重要性.此外,該方法的時(shí)間復(fù)雜度僅為 O(n2),適用于大型復(fù)雜網(wǎng)絡(luò).

1 引言

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

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

當(dāng)使用熵來(lái)評(píng)估復(fù)雜網(wǎng)絡(luò)時(shí),復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)越有序,熵值就越小,反之亦然.同時(shí),熵也可用來(lái)描述整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性和復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性.例如,Chen 等[18]提出了結(jié)構(gòu)熵來(lái)量化復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)特征.Zhang 等[19]提出了一種基于非廣延統(tǒng)計(jì)力學(xué)的結(jié)構(gòu)熵來(lái)度量網(wǎng)絡(luò)的復(fù)雜性.黃麗亞等[20]提出了一種基于網(wǎng)絡(luò)節(jié)點(diǎn)在K步內(nèi)可達(dá)的節(jié)點(diǎn)總數(shù)的K-階結(jié)構(gòu)熵,用于度量復(fù)雜網(wǎng)絡(luò)的異構(gòu)性.Wang 等[21]提出了一種基于K 殼和節(jié)點(diǎn)信息熵的改進(jìn)算法,用于區(qū)分上層外殼和下層外殼中節(jié)點(diǎn)的重要性.

受到上述研究工作的啟發(fā),本文提出了一種基于Tsallis 熵的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法(TSM).該方法不僅考慮了節(jié)點(diǎn)的結(jié)構(gòu)洞特征和K 殼中心性,還充分考慮了節(jié)點(diǎn)自身及其鄰域節(jié)點(diǎn)的影響,在兼顧節(jié)點(diǎn)的局部和全局拓?fù)湫畔⒌耐瑫r(shí),采用Tsallis 熵來(lái)度量網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性.時(shí)間復(fù)雜度分析表明,該方法的時(shí)間復(fù)雜度僅為O(n2),適用于大型復(fù)雜網(wǎng)絡(luò).為了說(shuō)明該方法的有效性和適用性,本文選用了8 個(gè)來(lái)自不同領(lǐng)域的真實(shí)網(wǎng)絡(luò),并采用了7 個(gè)現(xiàn)有的節(jié)點(diǎn)重要性評(píng)估方法作為比較方法.在此基礎(chǔ)上,利用單調(diào)性指標(biāo)、SIR 模型和Kendall 相關(guān)系數(shù)τ說(shuō)明了該方法的優(yōu)越性以及不同方法之間的關(guān)系.

2 理論基礎(chǔ)

2.1 網(wǎng)絡(luò)定義

設(shè)圖G=(V,E) 是1 個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò),其中V={v1,v2,···,vn}表示G中節(jié)點(diǎn)的集合,|V|=n,E={(vi,vj)|vi,vj ∈V}表示G中邊的集合,|E|=m.記An×n=(aij)n×n為G對(duì)應(yīng)的鄰接矩陣,如果節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間存在連邊關(guān)系,則aij=1,否則aij=0 .

2.2 度中心性

度中心性(degree centrality,DC)[7]是衡量節(jié)點(diǎn)影響力的最簡(jiǎn)單指標(biāo).節(jié)點(diǎn)擁有的度數(shù)越大,該節(jié)點(diǎn)的影響力就越大.節(jié)點(diǎn)vi的DC 定義為

其中,n為網(wǎng)絡(luò)中節(jié)點(diǎn)的∑數(shù)量.于是,節(jié)點(diǎn)vi的鄰接度可以定義為,其中,Γ(i)為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)的集合.

2.3 介數(shù)中心性

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

其中,σst為網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)vs和vt之間的最短路徑數(shù)目,為經(jīng)過(guò)節(jié)點(diǎn)vi的最短路徑數(shù)目.

2.4 混合度分解方法

混合度分解方法(mixed degree decomposition method,MDD)由Zeng 等[11]提出,該方法有效提高了K 殼分解方法的區(qū)分度.它通過(guò)同時(shí)考慮節(jié)點(diǎn)的剩余度值和節(jié)點(diǎn)的已移除度值對(duì)K 殼分解過(guò)程進(jìn)行了改進(jìn),網(wǎng)絡(luò)按照新的混合度值繼續(xù)分層,節(jié)點(diǎn)vi的混合度定義為

其中,λ是0 到1 之間的可調(diào)參數(shù).當(dāng)λ=0 時(shí),MDD方法與K 殼分解方法一致,但當(dāng)λ=1 時(shí),它等同于DC.在本文中,設(shè)定了參考文獻(xiàn)[11]中使用的參數(shù)λ=0.7 .

2.5 全方位距離

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

其中,KS(i) 為節(jié)點(diǎn)vi的K 殼值.

2.6 改進(jìn)的K 殼方法

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

2.7 結(jié)構(gòu)洞理論

結(jié)構(gòu)洞理論(structural holes theory)是Burt等[15]在1992 年研究社交網(wǎng)絡(luò)中的競(jìng)爭(zhēng)關(guān)系時(shí)提出的.在社會(huì)網(wǎng)絡(luò)中,結(jié)構(gòu)洞是指?jìng)€(gè)體之間為非冗余關(guān)系,且存在互補(bǔ)信息的差距.為了量化結(jié)構(gòu)洞節(jié)點(diǎn)對(duì)這些關(guān)系的控制,Burt 采用約束系數(shù)來(lái)測(cè)量結(jié)構(gòu)洞中節(jié)點(diǎn)形成的約束.當(dāng)系數(shù)越小,節(jié)點(diǎn)越容易形成結(jié)構(gòu)洞,節(jié)點(diǎn)的影響力越大.節(jié)點(diǎn)vi的約束系數(shù)為

其中,節(jié)點(diǎn)vq是節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的共同鄰居節(jié)點(diǎn);Lij表示在節(jié)點(diǎn)vi的所有鄰居節(jié)點(diǎn)中節(jié)點(diǎn)vj所占的權(quán)重比例.

在計(jì)算節(jié)點(diǎn)的約束系數(shù)時(shí),考慮到節(jié)點(diǎn)及其鄰域的度值和拓?fù)浣Y(jié)構(gòu)對(duì)節(jié)點(diǎn)重要性的影響將Lij定義為

2.8 Tsallis 非廣延統(tǒng)計(jì)力學(xué)

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

其中,k是玻爾茲曼常數(shù),pi滿足標(biāo)準(zhǔn)化條件.

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

(9)式中的q-對(duì)數(shù)函數(shù)為

根據(jù)(11)式可以將(9)式改寫(xiě)為

其中,N是子系統(tǒng)的數(shù)量.將非廣延參數(shù)q用于描述子系統(tǒng)之間相互作用,當(dāng)q=1 時(shí),Tsallis 熵將退化為Boltzmann-Gibbs 熵.

3 基于Tsallis 熵的節(jié)點(diǎn)重要性評(píng)估方法

3.1 方法構(gòu)造

基于Tsallis 熵的節(jié)點(diǎn)重要性評(píng)估方法構(gòu)造的基本思想是在綜合考慮節(jié)點(diǎn)的結(jié)構(gòu)洞特征和K 殼中心性的同時(shí),利用Tsallis 熵度量網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性,評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性.由于結(jié)構(gòu)洞特征能體現(xiàn)節(jié)點(diǎn)的局部拓?fù)湫畔?而K 殼中心性表征了節(jié)點(diǎn)的全局拓?fù)湫畔?結(jié)合這兩種拓?fù)湫畔?利用Tsallis 熵度量網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性,并通過(guò)對(duì)每個(gè)節(jié)點(diǎn)的自身及其鄰域節(jié)點(diǎn)的綜合考察,可以給出1 個(gè)合理的評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的方法,即本文提出的TSM 方法.

基于Tsallis 非廣延統(tǒng)計(jì)力學(xué),可以得到Tsallis熵的如下形式:

因?yàn)榻Y(jié)構(gòu)洞約束系數(shù)是基于網(wǎng)絡(luò)局部拓?fù)湫畔⒌脑u(píng)估指標(biāo),考慮到相鄰節(jié)點(diǎn)的結(jié)構(gòu)洞特征對(duì)該節(jié)點(diǎn)重要性的影響,可以得到Pij的定義:

由于K 殼中心性是描述節(jié)點(diǎn)在網(wǎng)絡(luò)中所處位置的全局指標(biāo),因此它可以用來(lái)表示每個(gè)節(jié)點(diǎn)與整個(gè)網(wǎng)絡(luò)之間的關(guān)系以及不同節(jié)點(diǎn)之間的關(guān)系.本文運(yùn)用MDD 方法得到節(jié)點(diǎn)vi的K 殼中心性 Ksi及其與網(wǎng)絡(luò)中所有節(jié)點(diǎn)的K 殼中心性數(shù)值之和的比值.進(jìn)而,可得到節(jié)點(diǎn)vi的Tsallis 參數(shù)qi:

(17)式的目的是使參數(shù)qi＞1,以反映子系統(tǒng)對(duì)網(wǎng)絡(luò)的次可加性影響.在信息論中,不同的q值表示不同子系統(tǒng)對(duì)Tsallis 熵的可加性不同,即q <1,q=1 ,q ＞1 分別代表超可加性、可加性和次可加性.擴(kuò)展到復(fù)雜網(wǎng)絡(luò)中,整個(gè)網(wǎng)絡(luò)可以看作1 個(gè)系統(tǒng),每個(gè)節(jié)點(diǎn)和相應(yīng)的連邊可以看作網(wǎng)絡(luò)的子系統(tǒng).

利用Tsallis 熵度量網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性得到T(vi)后,再結(jié)合節(jié)點(diǎn)自身的結(jié)構(gòu)洞特征,可得

Bae 和Kim[12]在改進(jìn)K 殼算法時(shí)提出了鄰域核心的概念,通過(guò)對(duì)所有鄰居的K 殼值進(jìn)行求和來(lái)衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性.本文借鑒了這一概念,充分考慮鄰域節(jié)點(diǎn)的影響.對(duì)于節(jié)點(diǎn)vi,將其所有相鄰節(jié)點(diǎn)的IC 值進(jìn)行相加,得到節(jié)點(diǎn)vi的鄰域核心(核心鄰域中心性) Cnc(vi):

在(19)式的基礎(chǔ)上,對(duì)其所有相鄰節(jié)點(diǎn)的鄰域核心值Cnc 進(jìn)行求和,可以得到節(jié)點(diǎn)vi的擴(kuò)展鄰域核心Cnc+(vi),最終得到了節(jié)點(diǎn)vi的重要性評(píng)估值TSM(vi):

3.2 時(shí)間復(fù)雜度分析

本節(jié)將對(duì)本文提出的TSM 算法進(jìn)行計(jì)算時(shí)間復(fù)雜度分析,其具體計(jì)算步驟如表1 所列.由表1可知,TSM 要遍歷網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn),在計(jì)算節(jié)點(diǎn)的結(jié)構(gòu)洞約束系數(shù)值RCi時(shí),考慮了節(jié)點(diǎn)的度及其與鄰居拓?fù)浣Y(jié)構(gòu)間的關(guān)系,故時(shí)間復(fù)雜度應(yīng)為O(n2);在計(jì)算Tsallis 參數(shù)qi時(shí),采用了MDD 方法得到節(jié)點(diǎn)的K 殼重要性指標(biāo),其時(shí)間復(fù)雜度為O(n);在計(jì)算節(jié)點(diǎn)的Ti值時(shí),需要考慮節(jié)點(diǎn)的鄰居節(jié)點(diǎn)信息,則時(shí)間復(fù)雜度為O(n*k) ;而在對(duì)IC 進(jìn)行累加時(shí),時(shí)間復(fù)雜度為O(n) .由此可以看出,TSM 算法的時(shí)間復(fù)雜度取決于節(jié)點(diǎn)的結(jié)構(gòu)洞約束系數(shù)值RCi的計(jì)算,因此本文提出的TSM 算法的時(shí)間復(fù)雜度為O(n2) .其中,n為網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù),k為網(wǎng)絡(luò)的平均度.

表1 計(jì)算步驟Table 1.Step of the calculation.

表2 列出了幾種不同方法的時(shí)間復(fù)雜度,并按照評(píng)估方法所包含的網(wǎng)絡(luò)信息將這些方法分成了局部、全局、混合等3 個(gè)類型.其中,m為網(wǎng)絡(luò)中連邊的總數(shù).當(dāng)n

圖3 不同傳播率下SIR 和各評(píng)估方法之間的Kendall 相關(guān)系數(shù),圖中黑色虛線為傳播閾值 βth (a) Karate 網(wǎng)絡(luò);(b) Dolphins網(wǎng)絡(luò);(c) Polbooks 網(wǎng)絡(luò);(d) Jazz 網(wǎng)絡(luò);(e) USAir 網(wǎng)絡(luò);(f) C.Elegans 網(wǎng)絡(luò);(g) Email 網(wǎng)絡(luò);(h) PowerGrid 網(wǎng)絡(luò)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 不同方法的時(shí)間復(fù)雜度Table 2.Time complexity of different methods.

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

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

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

表3 網(wǎng)絡(luò)的統(tǒng)計(jì)特征Table 3.Statistical characteristics of the networks.

4.2 有效性分析

為了驗(yàn)證本文提出的TSM 算法的有效性和準(zhǔn)確性,首先以Karate 網(wǎng)絡(luò)為例進(jìn)行仿真分析,其拓?fù)鋱D如圖1 所示.選用了DC[7]、BC[8]、MDD[11]、鄰域結(jié)構(gòu)洞方法[16](N-Burt)、核心鄰域中心性[12](Cnc+)、AAD[13]以及IKS[21]等7 種方法與本文提出的TSM 方法進(jìn)行對(duì)比,得到網(wǎng)絡(luò)前15 個(gè)關(guān)鍵節(jié)點(diǎn)的重要性評(píng)估結(jié)果如表4所列.

圖1 Karate 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)Fig.1.Topological structure of the Karate network.

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

表4 Karate 網(wǎng)絡(luò)的節(jié)點(diǎn)重要度評(píng)估結(jié)果Table 4.Node importance evaluation results in the Karate network.

表5 不同評(píng)估方法的單調(diào)性指標(biāo)MTable 5.Monotonicity index M of different evaluation methods.

本文所提出的TSM 方法克服了以上方法的不足,它從節(jié)點(diǎn)的局部和全局拓?fù)湫畔蓚€(gè)角度出發(fā),綜合考慮節(jié)點(diǎn)自身的結(jié)構(gòu)洞特征和網(wǎng)絡(luò)位置信息以及鄰域節(jié)點(diǎn)的影響,并基于Tsallis 熵度量網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性,可提高節(jié)點(diǎn)重要性的區(qū)分度,準(zhǔn)確地評(píng)估節(jié)點(diǎn)重要性.如表4 所列,通過(guò)TSM 方法評(píng)估出的前15 個(gè)重要節(jié)點(diǎn)與其他方法評(píng)估出的重要節(jié)點(diǎn)基本相同,說(shuō)明TSM 方法能夠有效地評(píng)估節(jié)點(diǎn)的重要性.在TSM 方法中,節(jié)點(diǎn)v4比節(jié)點(diǎn)v32更為重要,這很好地體現(xiàn)了相鄰節(jié)點(diǎn)的結(jié)構(gòu)洞特征對(duì)節(jié)點(diǎn)的影響,同時(shí)也說(shuō)明本方法克服了BC的不足;節(jié)點(diǎn)v9,v14,v24和節(jié)點(diǎn)v8,v28,v30的重要性得到了進(jìn)一步的區(qū)分,其中,節(jié)點(diǎn)v9的重要性高于節(jié)點(diǎn)v14,這說(shuō)明了本方法既有效地識(shí)別了網(wǎng)絡(luò)中的“橋接”節(jié)點(diǎn),亦克服了DC 的不足.通過(guò)對(duì)比,本文提出的TSM 方法能有效地評(píng)估節(jié)點(diǎn)重要性,可進(jìn)一步提高節(jié)點(diǎn)重要性的區(qū)分度.

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

接下來(lái)介紹驗(yàn)證所提出的TSM 方法準(zhǔn)確性的評(píng)價(jià)標(biāo)準(zhǔn).它們分別是單調(diào)性指標(biāo)[12]、SIR 模型[32]和Kendall 相關(guān)系數(shù)[33].

本文采用單調(diào)性指標(biāo)[12]M(R) 來(lái)量化不同重要性評(píng)估方法的分辨率,如下所示:

其中,R為評(píng)估方法得到的每個(gè)節(jié)點(diǎn)的重要性排序向量,n為網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù),nr為重要性相同的節(jié)點(diǎn)的數(shù)量.M(R) 的取值介于0 到1 之間.如果M(R)=1,則排序向量R是完全單調(diào)的,說(shuō)明該評(píng)估方法能將網(wǎng)絡(luò)中所有節(jié)點(diǎn)的重要性完全區(qū)分;如果M(R)=0,則表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的重要性相同.

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

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

其中,C和D分別表示同序?qū)彤愋驅(qū)Φ臄?shù)量.τ的取值介于—1 和1 之間,τ=1 時(shí)表示兩個(gè)序列完全正相關(guān),即相關(guān)系數(shù)τ越接近1,精確度越高;反之,則表示完全負(fù)相關(guān).

4.4 實(shí)驗(yàn)分析

本節(jié)記錄并分析了不同節(jié)點(diǎn)重要性評(píng)估方法在不同真實(shí)網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果.

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

圖2 不同評(píng)估方法的單調(diào)性指標(biāo)M (a) Karate 網(wǎng)絡(luò)、Dolphins 網(wǎng)絡(luò)、Polbooks 網(wǎng)絡(luò)和Jazz 網(wǎng)絡(luò);(b) USAir 網(wǎng)絡(luò)、C.Elegans 網(wǎng)絡(luò)、Email 網(wǎng)絡(luò)和PowerGrid 網(wǎng)絡(luò)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 模型得到節(jié)點(diǎn)的傳播能力排序σ,并計(jì)算了不同評(píng)估方法的排序與σ之間的Kendall 相關(guān)系數(shù)τ.相關(guān)性越高,對(duì)節(jié)點(diǎn)重要性的評(píng)估就越準(zhǔn)確.由于SIR 模型迭代過(guò)程的隨機(jī)性,本文對(duì)每個(gè)節(jié)點(diǎn)重復(fù)模擬該過(guò)程,然后取其平均值.模擬將遵循以下規(guī)則:對(duì)于網(wǎng)絡(luò)|V| ＜ 100,模擬迭代104次;對(duì)于 100<|V|<104,模擬迭代103次.表6 展示了8 個(gè)真實(shí)網(wǎng)絡(luò)在選定傳播率下各評(píng)估方法的Kendall 相關(guān)系數(shù),SIR 模型的實(shí)際傳播率取值如表3 所列.從表6 可以看出,TSM 方法的相關(guān)系數(shù)值在0.8 到1 之間.同時(shí),與其他方法相比,TSM 方法的相關(guān)性在8 個(gè)真實(shí)網(wǎng)絡(luò)中都最為顯著.因此,TSM 方法的準(zhǔn)確性得到了初步的驗(yàn)證.

表6 選定傳播率下SIR 和各評(píng)估方法之間的Kendall 相關(guān)系數(shù)Table 6.Kendall correlation coefficient between SIR and evaluation methods under a certain transmission rate.

為了進(jìn)一步驗(yàn)證所提方法的準(zhǔn)確性和可靠性,對(duì)比了不同傳播率下各評(píng)估方法與SIR 模型排序結(jié)果之間的Kendall 相關(guān)系數(shù),如圖3 所示.從圖3可以看出,當(dāng)傳播率β在傳播閾值βth附近取值時(shí),TSM 方法的相關(guān)系數(shù)除了在Karate 網(wǎng)絡(luò)中略低于Cnc+方法以外,在大多數(shù)情況下都高于其他方法,與SIR 模型得到的節(jié)點(diǎn)傳播能力有顯著的相關(guān)性.同時(shí),可以看出當(dāng)傳播率β遠(yuǎn)大于或者遠(yuǎn)小于傳播閾值βth時(shí),在除Karate,USAir 和PowerGrid網(wǎng)絡(luò)以外的5 個(gè)真實(shí)網(wǎng)絡(luò)中,DC,MDD 以及AAD等方法表現(xiàn)出了比TSM 方法更好的相關(guān)性.而B(niǎo)C的相關(guān)性在8 個(gè)真實(shí)網(wǎng)絡(luò)中表現(xiàn)最差.因此,TSM方法能夠更為準(zhǔn)確地評(píng)估節(jié)點(diǎn)的重要性.

然后,對(duì)Kendall 相關(guān)系數(shù)的考察節(jié)點(diǎn)范圍進(jìn)行了調(diào)整,將考察的節(jié)點(diǎn)從整體節(jié)點(diǎn)變?yōu)椴糠止?jié)點(diǎn),進(jìn)一步研究了各個(gè)評(píng)估方法得到的不同比例排序靠前的節(jié)點(diǎn)與節(jié)點(diǎn)傳播能力排序的相關(guān)性結(jié)果.在8 個(gè)真實(shí)網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn),設(shè)置節(jié)點(diǎn)比例L的變化范圍為0.05—1.如圖4 所示,給出不同比例節(jié)點(diǎn)下各評(píng)估方法的相關(guān)系數(shù)值.從圖4 可以看出,本文提出的TSM 算法在不同比例節(jié)點(diǎn)下都能取得不錯(cuò)的節(jié)點(diǎn)重要性評(píng)估結(jié)果,且在更大范圍的L值下可以取得更好的評(píng)估結(jié)果.

圖4 不同比例節(jié)點(diǎn)下各評(píng)估方法的Kendall 相關(guān)系數(shù) (a) Karate 網(wǎng)絡(luò);(b) Dolphins 網(wǎng)絡(luò);(c) Polbooks 網(wǎng)絡(luò);(d) Jazz 網(wǎng)絡(luò);(e) USAir 網(wǎng)絡(luò);(f) C.Elegans 網(wǎng)絡(luò);(g) Email 網(wǎng)絡(luò);(h) PowerGrid 網(wǎng)絡(luò)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 方法與其他評(píng)估方法之間的關(guān)系,如圖5 所示.圖中每個(gè)點(diǎn)代表復(fù)雜網(wǎng)絡(luò)中的1 個(gè)節(jié)點(diǎn),點(diǎn)的顏色表示由SIR 模型得到的節(jié)點(diǎn)傳播能力,橫軸和縱軸分別為TSM 方法和其他方法得到的網(wǎng)絡(luò)中各節(jié)點(diǎn)重要性數(shù)值.當(dāng)圖中的節(jié)點(diǎn)呈線性分布時(shí),說(shuō)明TSM 方法與該方法有強(qiáng)的相關(guān)性.從圖5 中的節(jié)點(diǎn)分布情況可以發(fā)現(xiàn),TSM與DC,MDD,N-Burt 之間存在強(qiáng)的相關(guān)性,這說(shuō)明TSM 方法既充分考慮了節(jié)點(diǎn)的DC 和位置信息,而且有能力識(shí)別到網(wǎng)絡(luò)中的“橋接”節(jié)點(diǎn).此外,TSM 與Cnc+,AAD,IKS 之間節(jié)點(diǎn)分布呈較明顯的線性關(guān)系,這說(shuō)明節(jié)點(diǎn)重要性排名總體相似,亦證明TSM 方法能有效評(píng)估節(jié)點(diǎn)重要性.從圖5 還可以發(fā)現(xiàn),有一些節(jié)點(diǎn)盡管其BC 數(shù)值大,但其傳播能力并不是很強(qiáng),因此僅靠BC 評(píng)估節(jié)點(diǎn)的重要性并不準(zhǔn)確.所以在評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性上,TSM 方法較其他方法更有優(yōu)勢(shì).

圖5 TSM 與其他評(píng)估方法之間的關(guān)系 (a) Karate 網(wǎng)絡(luò),β=0.25;(b) Dolphins 網(wǎng)絡(luò),β=0.15;(c) Polbooks 網(wǎng)絡(luò),β=0.1;(d) Jazz 網(wǎng)絡(luò),β=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 結(jié)論

本文提出了一種TSM 方法,有效地對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性進(jìn)行評(píng)估和排序.TSM 方法兼顧局部拓?fù)湫畔⒑腿滞負(fù)湫畔?結(jié)合了節(jié)點(diǎn)的結(jié)構(gòu)洞特征和K 殼中心性,利用Tsallis 熵度量網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性,彌補(bǔ)了現(xiàn)存方法評(píng)估角度片面的不足,優(yōu)化了可用資源的利用,使信息得以有效傳播.該方法在考慮節(jié)點(diǎn)的鄰域結(jié)構(gòu)和位置信息的同時(shí),有能力識(shí)別到網(wǎng)絡(luò)中的“橋接”節(jié)點(diǎn),從而對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性進(jìn)行有效的評(píng)估.在8 個(gè)真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明,與其他評(píng)估方法如DC,BC,MDD,N-Burt,Cnc+,AAD 和IKS 相比,TSM 方法能更好地區(qū)分節(jié)點(diǎn)重要性的差異,在不同比例節(jié)點(diǎn)下都能準(zhǔn)確地評(píng)估節(jié)點(diǎn)的重要性.此外,TSM 方法的時(shí)間復(fù)雜度僅為O(n2),適用于大型復(fù)雜網(wǎng)絡(luò).尋找一種結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)和傳播動(dòng)力學(xué)的更有效的方法來(lái)評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性仍然是一個(gè)長(zhǎng)期的挑戰(zhàn).未來(lái)的工作將集中在如何應(yīng)用所提出的TSM 方法來(lái)評(píng)估多層網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性.