盧鵬麗, 許星舟

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

復(fù)雜系統(tǒng)存在于現(xiàn)實(shí)生活中的各個(gè)領(lǐng)域.為了更好地研究事物間的聯(lián)系，人們對(duì)復(fù)雜系統(tǒng)進(jìn)行抽象，并將得到的理想模型稱為復(fù)雜網(wǎng)絡(luò).其中網(wǎng)絡(luò)中的實(shí)體對(duì)象被抽象為節(jié)點(diǎn)，實(shí)體對(duì)象之間的顯性或隱性關(guān)系被抽象為邊[1].伴隨著全球數(shù)字化進(jìn)程加快，人們?cè)谟?jì)算機(jī)、通信、刑偵、社會(huì)、金融、交通、生物等諸多領(lǐng)域中都抽象出了復(fù)雜網(wǎng)絡(luò)，并吸引了大量相關(guān)領(lǐng)域的研究[2].關(guān)鍵節(jié)點(diǎn)是構(gòu)成一個(gè)網(wǎng)絡(luò)并實(shí)現(xiàn)其信息傳遞功能的核心要素，因此識(shí)別關(guān)鍵節(jié)點(diǎn)一直是復(fù)雜網(wǎng)絡(luò)研究中的熱門課題.研究發(fā)現(xiàn)，保護(hù)關(guān)鍵節(jié)點(diǎn)既可以提升網(wǎng)絡(luò)的抗毀性，也可以從關(guān)鍵節(jié)點(diǎn)入手提出更高效的網(wǎng)絡(luò)攻擊策略[3].通過(guò)對(duì)交通網(wǎng)絡(luò)進(jìn)行關(guān)鍵節(jié)點(diǎn)識(shí)別，可以找到網(wǎng)絡(luò)中易擁堵的路段，積極改善這一問(wèn)題，能夠促進(jìn)智慧交通的建設(shè)[4].通過(guò)對(duì)恐怖分子網(wǎng)絡(luò)進(jìn)行關(guān)鍵節(jié)點(diǎn)識(shí)別有助于發(fā)掘潛藏的恐怖分子頭目首領(lǐng)，從而搗毀整個(gè)犯罪網(wǎng)絡(luò)，促進(jìn)地區(qū)的和平穩(wěn)定[5].通過(guò)對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行關(guān)鍵節(jié)點(diǎn)識(shí)別能夠找到神經(jīng)信號(hào)傳遞時(shí)的關(guān)鍵神經(jīng)元，從而提升癱瘓類疾病的治愈效果[6].

為了識(shí)別關(guān)鍵節(jié)點(diǎn)，人們提出了一系列的節(jié)點(diǎn)中心性評(píng)估指標(biāo)來(lái)衡量節(jié)點(diǎn)的重要性.其中最常見(jiàn)的經(jīng)典指標(biāo)包括：度中心性(degree centrality)[7]、介數(shù)中心性(betweenness centrality)[8]、k核(k-shell)[9]、H指數(shù)中心性(H-index centrality)[10]等.度中心性是最簡(jiǎn)單基礎(chǔ)的節(jié)點(diǎn)評(píng)估指標(biāo)，直觀反映了節(jié)點(diǎn)擁有的鄰居數(shù)量.介數(shù)中心性是根據(jù)經(jīng)過(guò)節(jié)點(diǎn)的最短路徑數(shù)量占網(wǎng)絡(luò)中所有最短路徑數(shù)量的比例來(lái)衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度.k核采用類似剝洋蔥的方式，根據(jù)度中心性由小到大的順序依次剝離網(wǎng)絡(luò)中的節(jié)點(diǎn)，再按照節(jié)點(diǎn)被剝離的先后次序來(lái)確定其重要性.H指數(shù)中心性由學(xué)術(shù)成就的評(píng)估指標(biāo)H指數(shù)演化而來(lái)，能夠利用鄰居節(jié)點(diǎn)的信息來(lái)評(píng)估節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力.然而，在實(shí)際應(yīng)用中都存在不同程度的局限性[11].例如：度中心性由于忽略了局部特征和全局結(jié)構(gòu)，從而導(dǎo)致識(shí)別關(guān)鍵節(jié)點(diǎn)的準(zhǔn)確性較低;介數(shù)中心性需要找出整個(gè)網(wǎng)絡(luò)中所有的最短路徑,導(dǎo)致時(shí)間復(fù)雜度較高,難以適用于大規(guī)模網(wǎng)絡(luò);k核在節(jié)點(diǎn)剝離過(guò)程中會(huì)破壞整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)信息;而H指數(shù)中心性只考慮到鄰居節(jié)點(diǎn)的影響力,卻忽視了節(jié)點(diǎn)自身的信息.為了消除這些局限性，人們結(jié)合節(jié)點(diǎn)的局部特征信息或全局拓?fù)浣Y(jié)構(gòu)信息提出了一些新的節(jié)點(diǎn)評(píng)估指標(biāo)，例如：鄰域核心度(neighborhood coreness)[12]、重力中心性(gravity centrality)[13]、局部DH中心性(local DH-index centrality)[14]和改進(jìn)的k核(improvedk-shell)[15]等.

本文基于k核分解的核心思想提出了精準(zhǔn)k核(accuratek-shell,Ak).該指標(biāo)重新定義了節(jié)點(diǎn)的k核劃分規(guī)則，能夠?qū)⒃緦儆谕籯核的節(jié)點(diǎn)按照剝離次序?qū)ζ溥M(jìn)行量化區(qū)分.然而精準(zhǔn)k核在節(jié)點(diǎn)剝離過(guò)程中依然會(huì)破壞網(wǎng)絡(luò)的結(jié)構(gòu)信息并且忽視了鄰居節(jié)點(diǎn)的影響力.為了更加充分地考慮節(jié)點(diǎn)局部特征和網(wǎng)絡(luò)整體拓?fù)浣Y(jié)構(gòu)對(duì)節(jié)點(diǎn)的影響，本文將精準(zhǔn)k核應(yīng)用到近年來(lái)較為熱門的重力中心性中提出了精準(zhǔn)重力中心性(accurate gravity centrality,AGC)，以此來(lái)消除精準(zhǔn)k核的局限性.此外，出于對(duì)節(jié)點(diǎn)重要性多元評(píng)估的目的，本文引入了信息學(xué)中的香農(nóng)熵，結(jié)合節(jié)點(diǎn)的鄰域度熵、鄰域精準(zhǔn)k核熵以及精準(zhǔn)重力熵,最終提出了混合中心性(mixed centrality,MC).通過(guò)對(duì)度中心性、介數(shù)中心性、k核、鄰域核心度、重力中心性、H指數(shù)中心性、局部DH中心性、改進(jìn)的k核和混合中心性在7種真實(shí)網(wǎng)絡(luò)下進(jìn)行了一系列性能實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明,本文提出的混合中心性在單調(diào)性和精準(zhǔn)性方面性能均優(yōu)于其他節(jié)點(diǎn)評(píng)估指標(biāo).

1 相關(guān)算法定義及本文算法

任何由復(fù)雜系統(tǒng)抽象得到的復(fù)雜網(wǎng)絡(luò)都可以由簡(jiǎn)單無(wú)向圖G=(V,E)來(lái)表示，其中V是實(shí)體對(duì)象的集合對(duì)應(yīng)網(wǎng)絡(luò)中的節(jié)點(diǎn)集，E是實(shí)體對(duì)象之間相互聯(lián)系的集合對(duì)應(yīng)網(wǎng)絡(luò)中的邊集.A代表網(wǎng)絡(luò)的鄰接矩陣，當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j之間存在連邊時(shí)，則Aij=1，否則Aij=0.

1.1 相關(guān)研究

以下是本文中所涉及到的節(jié)點(diǎn)評(píng)估指標(biāo)，在后續(xù)的實(shí)驗(yàn)部分中將對(duì)這些指標(biāo)進(jìn)行單調(diào)性和精準(zhǔn)性的對(duì)比實(shí)驗(yàn).

1) 度中心性(degree centrality)

度中心性[7]是衡量節(jié)點(diǎn)重要性最基礎(chǔ)的指標(biāo)，定義為與節(jié)點(diǎn)相連邊的數(shù)量或節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量.節(jié)點(diǎn)的度越大，則可以傳播信息的渠道和對(duì)象越多，其自身的重要性也越高.節(jié)點(diǎn)i的度中心性可以表示為

(1)

其中:N是網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù).

2) 介數(shù)中心性(betweenness centrality)

介數(shù)中心性[8]是一種全局指標(biāo)，能夠反映一個(gè)節(jié)點(diǎn)作為交通樞紐的重要程度.通過(guò)計(jì)算經(jīng)過(guò)節(jié)點(diǎn)的最短路徑數(shù)量在整個(gè)網(wǎng)絡(luò)最短路徑數(shù)量的占比來(lái)評(píng)估節(jié)點(diǎn)的重要性，其公式為

(2)

其中:σst代表節(jié)點(diǎn)s和節(jié)點(diǎn)t之間所有最短路徑的數(shù)目;σst(i)表示網(wǎng)絡(luò)中所有最短路徑中經(jīng)過(guò)節(jié)點(diǎn)i的路徑總數(shù).

3)k核(k-shell)

k核是Kitsak等[9]提出的一種基于位置信息來(lái)評(píng)估節(jié)點(diǎn)重要性的指標(biāo)，其基本思想為：首先設(shè)置ks=1，即將網(wǎng)絡(luò)中所有度中心性為1的節(jié)點(diǎn)視為重要性最低的節(jié)點(diǎn)進(jìn)行剝離.檢測(cè)剝離后的子網(wǎng)絡(luò)中是否仍然存在度中心性為1的節(jié)點(diǎn)，如果仍然存在則繼續(xù)剝離直至子網(wǎng)絡(luò)中不再存在度中心性為1的節(jié)點(diǎn)，此時(shí)已被剝離節(jié)點(diǎn)的k核值即為1.隨后設(shè)置ks=2，再將網(wǎng)絡(luò)中所有度中心性為2的節(jié)點(diǎn)進(jìn)行剝離，循環(huán)往復(fù)直到所有節(jié)點(diǎn)都被分配到k核值.k核能夠通過(guò)網(wǎng)絡(luò)中節(jié)點(diǎn)被剝離的次序?qū)?jié)點(diǎn)進(jìn)行評(píng)估，越是最后被剝離的節(jié)點(diǎn)其k核越大，節(jié)點(diǎn)的重要性越高.

Baus等[12]在k核中心性基礎(chǔ)上充分考慮了節(jié)點(diǎn)局部的重要性,提出了鄰域核心度(neighborhood coreness)，將鄰居節(jié)點(diǎn)的k核之和作為評(píng)估其重要性的指標(biāo)，其公式為

(3)

其中:Neii表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集;ks(j)代表節(jié)點(diǎn)j的k核.

4) 重力中心性(gravity centrality)[13]

受牛頓重力公式的靈感啟發(fā)，Ma等[13]將網(wǎng)絡(luò)中的節(jié)點(diǎn)類比成為天體行星，將節(jié)點(diǎn)的k核類比為行星的質(zhì)量，將節(jié)點(diǎn)之間的最短距離類比為行星之間的距離，從而計(jì)算節(jié)點(diǎn)間的相互影響力，其公式為

(4)

其中:ks(i)代表節(jié)點(diǎn)i的k核;φi代表距離節(jié)點(diǎn)i的距離不超過(guò)3的節(jié)點(diǎn)集;dij代表節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離.

重力中心性是指節(jié)點(diǎn)從鄰居節(jié)點(diǎn)處受到的相互影響力之和，其公式為

(5)

其中:Neii表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集.

5)H指數(shù)中心性(H-index centrality)

H指數(shù)是學(xué)術(shù)界中普遍用于評(píng)估學(xué)者學(xué)術(shù)成果的指標(biāo)，Korn等[10]將其思想推廣到了復(fù)雜網(wǎng)絡(luò)當(dāng)中并提出了H指數(shù)中心性，其定義為

Hindex(i)=H(dj1,dj2,…,djn)

(6)

其中:n是節(jié)點(diǎn)i的度;(j1,j2,…,jn)是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集;(dj1,dj2,…,djn)是其鄰居節(jié)點(diǎn)的度集.函數(shù)H(dj1,dj2,…,djn)的最終返回值為y，并使得鄰居節(jié)點(diǎn)的度集中有y個(gè)值大于等于y.

Lu等[14]通過(guò)將度中心性和H指數(shù)中心性結(jié)合的方式提出了局部DH指數(shù)中心性，其定義為

DHindex(i)=αDC(i)+βHindex(i)+

(7)

其中:DC(i)代表節(jié)點(diǎn)i的度中心性;Hindex(i)代表節(jié)點(diǎn)i的H指數(shù)中心性;Neii表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集；α=β=0.15.

6) 改進(jìn)的k核(improvedk-shell)

Wang等[15]通過(guò)將信息學(xué)中的香農(nóng)熵引入復(fù)雜網(wǎng)絡(luò)中對(duì)k核進(jìn)行了改進(jìn).根據(jù)節(jié)點(diǎn)熵的大小對(duì)k核中每一層元素進(jìn)行排序，從而得到網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性序列.其節(jié)點(diǎn)的度熵定義為

其中:DC(i)代表節(jié)點(diǎn)i的度中心性;N代表網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù);Neii代表節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集.

1.2 本文算法

本文提出了一種識(shí)別復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的評(píng)估指標(biāo)混合中心性.該方法首先改進(jìn)了k核的分解過(guò)程，大幅提升了k核識(shí)別關(guān)鍵節(jié)點(diǎn)的精準(zhǔn)度.其次，將改進(jìn)后的k核應(yīng)用到重力中心性中，彌補(bǔ)了其忽視節(jié)點(diǎn)局部特征和網(wǎng)絡(luò)整體拓?fù)浣Y(jié)構(gòu)的不足.考慮到單一指標(biāo)在評(píng)估節(jié)點(diǎn)時(shí)產(chǎn)生的片面性，本文引入了信息學(xué)中的香農(nóng)熵并對(duì)節(jié)點(diǎn)的鄰域度中心性、鄰域精準(zhǔn)k核以及精準(zhǔn)重力中心性進(jìn)行了歸一化處理.最后，通過(guò)將這三種熵結(jié)合來(lái)實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的多元化評(píng)估.

1) 精準(zhǔn)k核(accuratek-shell)

基于k核分解法的思想，本文認(rèn)為網(wǎng)絡(luò)中越早被剝離的節(jié)點(diǎn)重要性越低，即使擁有相同k核的節(jié)點(diǎn)也應(yīng)該根據(jù)剝離次序進(jìn)行評(píng)估區(qū)分.本文提出了一種可以根據(jù)節(jié)點(diǎn)剝離次序逐層量化k核的方法，其核心思想為：默認(rèn)初始ks=1，統(tǒng)計(jì)ks每次變動(dòng)前一共經(jīng)歷了多少次剝離過(guò)程.假設(shè)ks=1到ks=2期間一共經(jīng)歷了N次剝離過(guò)程，那么最先剝離的節(jié)點(diǎn)的k核為ks=1+0/N，第二次被剝離節(jié)點(diǎn)的k核中心性為ks=1+1/N，依此類推，最后一次被剝離節(jié)點(diǎn)的k核為ks=1+(N-1)/N.

根據(jù)圖1所示，精準(zhǔn)k核分解法能夠?qū)W(wǎng)絡(luò)進(jìn)行更加細(xì)致的劃分，使處于同一k核的元素得到區(qū)分.而由表1可知，k核只能將網(wǎng)絡(luò)區(qū)分為3個(gè)重要性等級(jí)，而精準(zhǔn)k核能夠在此基礎(chǔ)上進(jìn)行細(xì)分并最終得到8個(gè)重要性等級(jí).相較于傳統(tǒng)的k核分解，精準(zhǔn)k核分解能夠?qū)⒏嗟墓?jié)點(diǎn)細(xì)分量化，在識(shí)別關(guān)鍵節(jié)點(diǎn)的準(zhǔn)確性上性能更優(yōu)秀.盡管如此，精準(zhǔn)k核依舊忽視了節(jié)點(diǎn)的局部特征信息和全局結(jié)構(gòu)信息.

圖1 精準(zhǔn)k核對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的分解Fig.1 Accurate k-shell decomposition of network nodes

2) 精準(zhǔn)重力中心性(accurate gravity centrality)

重力中心性是基于k核提出的一種節(jié)點(diǎn)評(píng)估指標(biāo)，而由于精準(zhǔn)k核在識(shí)別關(guān)鍵節(jié)點(diǎn)的性能優(yōu)于k核，因此本文將精準(zhǔn)k核應(yīng)用到重力中心性中對(duì)其進(jìn)行改進(jìn).其節(jié)點(diǎn)間的精準(zhǔn)相互影響力為

(10)

其中:Ak(i)代表節(jié)點(diǎn)i的精準(zhǔn)k核;φi代表距離節(jié)點(diǎn)i的距離不超過(guò)3的節(jié)點(diǎn)集;dij代表節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離.

精準(zhǔn)重力中心性定義為節(jié)點(diǎn)i與鄰居節(jié)點(diǎn)間的精準(zhǔn)相互影響力之和，其公式為

(11)

其中:Neii表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集.

3) 鄰域中心性(neighbourhood centrality)

精準(zhǔn)重力中心性和鄰域核心度都是將鄰居節(jié)點(diǎn)的重要性之和作為衡量自身重要性的新指標(biāo)，這種方法能夠充分考慮到局部特征信息對(duì)節(jié)點(diǎn)重要性的影響.基于這種思想，本文提出了鄰域度中心性和鄰域精準(zhǔn)k核兩種新的節(jié)點(diǎn)評(píng)估指標(biāo)，其公式為

其中:Neii表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集.

4) 香農(nóng)熵(Shannon entropy)

香農(nóng)熵在復(fù)雜網(wǎng)絡(luò)中具有良好的拓展性，將香農(nóng)熵公式中事物出現(xiàn)的概率替換成節(jié)點(diǎn)的重要性，有助于從信息學(xué)角度對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估分析.在信息論中，香農(nóng)熵是衡量信息不確定性的指標(biāo)，熵值越大則說(shuō)明這條信息的不確定性越高，理解成本越高.而在復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)的熵值越大則說(shuō)明節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力越大.假設(shè)節(jié)點(diǎn)的鄰域度重要性為

則節(jié)點(diǎn)的鄰域精準(zhǔn)k核重要性和鄰域精準(zhǔn)重力重要性分別為

其中:DCnei(i)代表節(jié)點(diǎn)i的鄰域度中心性;Aknei(i)代表節(jié)點(diǎn)i的鄰域精準(zhǔn)k核;AGCnei(i)代表節(jié)點(diǎn)i的精準(zhǔn)重力中心性;N代表網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù).則節(jié)點(diǎn)的鄰域度熵、鄰域精準(zhǔn)k核熵和精準(zhǔn)重力熵分別為

其中:Neii表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集.

5) 混合中心性(mixed centrality)

通過(guò)結(jié)合鄰域度熵、鄰域精準(zhǔn)k核熵和精準(zhǔn)重力熵，本文提出了混合中心性，其公式為

MC(i)=EDCnei(i)+EAknei(i)+EAGCnei(i)

(17)

混合中心性中所涉及的鄰域度中心性、鄰域精準(zhǔn)k核和精準(zhǔn)重力中心性中包含了節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)信息、位置信息、局部特征信息和網(wǎng)絡(luò)整體拓?fù)浣Y(jié)構(gòu)信息.利用香農(nóng)熵對(duì)這三種指標(biāo)進(jìn)行歸一化處理再結(jié)合，不僅能將這些信息充分融合，還能確保節(jié)點(diǎn)均衡地受到這三種指標(biāo)的影響.此外，還可以消除單一指標(biāo)評(píng)估節(jié)點(diǎn)時(shí)產(chǎn)生的片面性，從而達(dá)到多元化評(píng)估的目的.

2 實(shí)驗(yàn)數(shù)據(jù)與評(píng)估方法

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

為了測(cè)試本文所提出的節(jié)點(diǎn)重要性評(píng)估指標(biāo)的性能，選取了7種真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集：海豚社交網(wǎng)[17]、美國(guó)大學(xué)生足球俱樂(lè)部網(wǎng)(Football)[18]、政治圖書(shū)網(wǎng)(Polbooks)[19]、爵士樂(lè)網(wǎng)(Jazz)[20]、美國(guó)航空運(yùn)輸網(wǎng)(USAir)[21]、大學(xué)生電子郵件網(wǎng)(Email)[22]和倉(cāng)鼠網(wǎng)(Hamster)[23].

表2反映了各個(gè)網(wǎng)絡(luò)的詳細(xì)信息，介紹了網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)(|V|)、邊數(shù)(|E|)、節(jié)點(diǎn)平均度數(shù)(Ave degree)、網(wǎng)絡(luò)中節(jié)點(diǎn)最大度數(shù)(Max degree)、閾值(βth)、感染率(β)和同配系數(shù)(Assortativity).

表2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的屬性

2.2 SIR模型

SIR模型的抽象概念源自于對(duì)傳染病的研究，當(dāng)今學(xué)者將其廣泛應(yīng)用于傳染病動(dòng)力學(xué)和信息傳播學(xué)中來(lái)發(fā)現(xiàn)具有較大影響力的人，以此來(lái)抑制傳染病擴(kuò)散和終結(jié)謠言[24-27].SIR模型分別由S、I、R三種狀態(tài)持有者構(gòu)成，分別為：

1) 易感者(Susceptibles)：免疫力低下，極易被病毒侵染.

2) 感染者(Infectives)：病毒攜帶者，已經(jīng)被病毒侵染，有幾率將病毒傳播給周圍人.

3) 康復(fù)者(Recovered)：已康復(fù)的感染者，體內(nèi)已經(jīng)產(chǎn)生了抗體，不會(huì)再受該病毒影響.

在初始階段，整個(gè)網(wǎng)絡(luò)中僅有一個(gè)感染者，其余均為易感者.每間隔一段時(shí)間感染者節(jié)點(diǎn)都會(huì)以β的傳染概率向其鄰居節(jié)點(diǎn)的易感者傳播病毒.同時(shí)，感染者也都會(huì)獲得θ=2β的康復(fù)率，康復(fù)后的感染者不會(huì)被再次感染.傳播過(guò)程將持續(xù)到網(wǎng)絡(luò)中不再有感染者節(jié)點(diǎn)時(shí)停止，將傳播期間每個(gè)節(jié)點(diǎn)成功傳染的節(jié)點(diǎn)數(shù)作為該節(jié)點(diǎn)的重要性.為了確保實(shí)驗(yàn)數(shù)據(jù)精準(zhǔn)，消除SIR模型在傳播過(guò)程時(shí)產(chǎn)生的隨機(jī)性，本文分別對(duì)表2中的7個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行1000 次SIR病毒傳播實(shí)驗(yàn)，并取其平均值作為節(jié)點(diǎn)在網(wǎng)絡(luò)中的真實(shí)重要性.

2.3 評(píng)估方法

在測(cè)試節(jié)點(diǎn)重要性評(píng)估指標(biāo)的性能時(shí)，學(xué)者們通常采用M單調(diào)函數(shù)[28-29]和肯德?tīng)栂嚓P(guān)系數(shù)[30-32]這兩種方法.其中，M單調(diào)函數(shù)能夠反應(yīng)節(jié)點(diǎn)評(píng)估指標(biāo)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的區(qū)分能力，肯德?tīng)栂嚓P(guān)系數(shù)能夠衡量節(jié)點(diǎn)評(píng)估指標(biāo)的準(zhǔn)確性.

1)M單調(diào)函數(shù)

M單調(diào)函數(shù)能通過(guò)計(jì)算節(jié)點(diǎn)重要性序列中相同元素的比例來(lái)衡量節(jié)點(diǎn)評(píng)估指標(biāo)的性能，其公式如下：

(18)

其中:R表示由節(jié)點(diǎn)評(píng)估指標(biāo)得到的節(jié)點(diǎn)重要性序列;r表示節(jié)點(diǎn)重要性序列中的元素;N表示節(jié)點(diǎn)重要性序列中元素的數(shù)量;Nr表示節(jié)點(diǎn)重要性序列中元素r的數(shù)量.M的取值范圍為[0,1]，M的值越大則說(shuō)明評(píng)估指標(biāo)能夠區(qū)分的節(jié)點(diǎn)越多.當(dāng)M=1時(shí)，說(shuō)明網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都能夠得以區(qū)分；而當(dāng)M=0時(shí)，說(shuō)明網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都具有相同的重要性，無(wú)法區(qū)分.

2) 肯德?tīng)栂嚓P(guān)系數(shù)

假設(shè)X與Y是元素?cái)?shù)量均為R的兩個(gè)集合，分別從兩個(gè)集合的第i個(gè)位置和第j個(gè)位置取出元素并構(gòu)成數(shù)據(jù)組，即(xi,yi)和(xj,yj).當(dāng)xi>xj且yi>yj或者xiyj或者xi>xj且yi

(19)

其中:RT和RF分別表示一致組和非一致組的數(shù)量.肯德?tīng)栂嚓P(guān)系數(shù)的取值范圍為[-1,1].當(dāng)τ=1時(shí)，說(shuō)明兩個(gè)集合中元素的等級(jí)相關(guān)性相同；當(dāng)τ=-1時(shí)，說(shuō)明兩個(gè)集合中元素的等級(jí)相關(guān)性相反；當(dāng)τ=0時(shí)，則表示這兩個(gè)集合中的元素相互獨(dú)立.

3 實(shí)驗(yàn)結(jié)果分析

本節(jié)中，將提出的節(jié)點(diǎn)評(píng)估指標(biāo)MC與其他節(jié)點(diǎn)評(píng)估指標(biāo)進(jìn)行單調(diào)性和相關(guān)性的對(duì)比來(lái)驗(yàn)證其性能.本文選擇度中心性(DC)、介數(shù)中心性(BC)、k核(ks)、鄰域核心度(NC)、重力中心性(GC)、H指數(shù)中心性(H)6種常見(jiàn)的節(jié)點(diǎn)評(píng)估指標(biāo)作為傳統(tǒng)對(duì)照組.此外，還選擇了兩種近期提出的性能優(yōu)秀的節(jié)點(diǎn)評(píng)估指標(biāo)作為新階對(duì)照組，分別是局部DH指數(shù)中心性(DH)和改進(jìn)的k核(Iks).

3.1 單調(diào)性比較

表3中的數(shù)據(jù)反映出了各個(gè)節(jié)點(diǎn)評(píng)估指標(biāo)在7種真實(shí)網(wǎng)絡(luò)下的M單調(diào)性，實(shí)驗(yàn)結(jié)果表明，由于MC和GC都考慮到了網(wǎng)絡(luò)的整體拓?fù)浣Y(jié)構(gòu)信息，因此都具備優(yōu)秀的節(jié)點(diǎn)區(qū)分能力.其中MC僅在爵士樂(lè)網(wǎng)中略低于傳統(tǒng)對(duì)照組中GC的單調(diào)性，在剩下6種網(wǎng)絡(luò)中其單調(diào)性都達(dá)到了最大值.此外，MC在大學(xué)生足球俱樂(lè)部網(wǎng)、政治圖書(shū)網(wǎng)和大學(xué)生電子郵件網(wǎng)中的單調(diào)性都達(dá)到了0.999 9，明顯高于新階對(duì)照組的兩個(gè)指標(biāo).而ks由于算法特性的原因在各個(gè)網(wǎng)絡(luò)中區(qū)分節(jié)點(diǎn)的性能普遍較差.

表3 不同指標(biāo)在7種真實(shí)網(wǎng)絡(luò)中的M單調(diào)性

3.2 相關(guān)性比較

表4匯總了7種不同規(guī)模的真實(shí)網(wǎng)絡(luò)在特定感染率β下各個(gè)節(jié)點(diǎn)評(píng)估指標(biāo)的肯德?tīng)栂嚓P(guān)系數(shù).實(shí)驗(yàn)數(shù)據(jù)表明,在新階對(duì)照組中只有Iks在美國(guó)航空運(yùn)輸網(wǎng)絡(luò)中取得了最佳性能，而在大學(xué)生足球俱樂(lè)部網(wǎng)絡(luò)傳統(tǒng)對(duì)照組中的NC取得了最好性能.其中由于BC的算法局限性導(dǎo)致其幾乎在所有的網(wǎng)絡(luò)中都取得了最差的結(jié)果.MC在其中的5種網(wǎng)絡(luò)中都表現(xiàn)出了最佳的性能，尤其是海豚社交網(wǎng)絡(luò)中τ(MC)=0.950 8,遠(yuǎn)超其余對(duì)比節(jié)點(diǎn)指標(biāo)的肯德?tīng)栂嚓P(guān)系數(shù).然而同樣具有優(yōu)秀節(jié)點(diǎn)區(qū)分能力的GC在評(píng)估節(jié)點(diǎn)的準(zhǔn)確性上卻不及MC，這證明了多元化評(píng)估思想的先進(jìn)性，也反映出MC具備精準(zhǔn)評(píng)估節(jié)點(diǎn)重要性的能力.

表4 7種不同規(guī)模真實(shí)網(wǎng)絡(luò)中的肯德?tīng)栂嚓P(guān)系數(shù)τ

為了更好地驗(yàn)證MC識(shí)別關(guān)鍵節(jié)點(diǎn)的性能，消除特定網(wǎng)絡(luò)閾值對(duì)實(shí)驗(yàn)結(jié)果的影響，本文從政治圖書(shū)網(wǎng)、爵士樂(lè)網(wǎng)、大學(xué)生電子郵件網(wǎng)和倉(cāng)鼠網(wǎng)的閾值附近均勻地取出10個(gè)數(shù)據(jù)作為感染率，對(duì)不同感染率下SIR病毒傳播模型中各個(gè)節(jié)點(diǎn)評(píng)估指標(biāo)的準(zhǔn)確性進(jìn)行了研究.如圖2所示，在這4種網(wǎng)絡(luò)中起初感染率β較小時(shí)，MC并未表現(xiàn)出較好的節(jié)點(diǎn)評(píng)估性能.隨著感染率β逐漸增大,MC的節(jié)點(diǎn)評(píng)估性能開(kāi)始變得越來(lái)越好.尤其是當(dāng)感染率β接近乃至大于網(wǎng)絡(luò)閾值時(shí)，可以發(fā)現(xiàn)MC的性能明顯優(yōu)于其他節(jié)點(diǎn)評(píng)估指標(biāo)，這表明MC更能精準(zhǔn)有效地評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性.

圖2 真實(shí)網(wǎng)絡(luò)在不同的感染率β下的節(jié)點(diǎn)重要性與各節(jié)點(diǎn)評(píng)估指標(biāo)的肯德?tīng)栂嚓P(guān)系數(shù)

此外，本文還研究了構(gòu)成MC的三種熵對(duì)算法整體的貢獻(xiàn)，熵的肯德?tīng)栂嚓P(guān)系數(shù)越大則代表該熵對(duì)MC的貢獻(xiàn)越大.通過(guò)觀察圖3中海豚社交網(wǎng)和美國(guó)大學(xué)生足球俱樂(lè)部網(wǎng)的鄰域度熵、精準(zhǔn)k核熵和精準(zhǔn)重力熵的肯德?tīng)栂禂?shù)，可以發(fā)現(xiàn)鄰域度熵在感染率β較小時(shí)具有更高的準(zhǔn)確性，精準(zhǔn)重力熵的準(zhǔn)確性較差.而當(dāng)感染率β接近或大于閾值時(shí)精準(zhǔn)重力熵能夠取得較高的準(zhǔn)確性.在政治圖書(shū)網(wǎng)中鄰域度熵和精準(zhǔn)k核熵都表現(xiàn)出了較高的準(zhǔn)確性，精準(zhǔn)重力熵的節(jié)點(diǎn)識(shí)別準(zhǔn)確性相對(duì)較弱.在大學(xué)生電子郵件網(wǎng)中，精準(zhǔn)重力熵在初始階段表現(xiàn)出了較高的準(zhǔn)確性，在感染率β接近閾值時(shí)被鄰域度熵和精準(zhǔn)k核熵的準(zhǔn)確性超越.由此可見(jiàn)，不同網(wǎng)絡(luò)中三種熵對(duì)算法整體的貢獻(xiàn)各不相同，其中鄰域度熵和精準(zhǔn)重力熵的貢獻(xiàn)較為突出，精準(zhǔn)k核熵的貢獻(xiàn)較弱.然而相較于構(gòu)成MC的三種香農(nóng)熵而言，MC在不同規(guī)模真實(shí)網(wǎng)絡(luò)中的大多數(shù)情況下都能取得最高的肯德?tīng)栂嚓P(guān)系數(shù)，這表明MC有效消除了單一指標(biāo)評(píng)估節(jié)點(diǎn)時(shí)的片面性，提升了自身的算法性能.

圖3 真實(shí)網(wǎng)絡(luò)在不同的感染率β下的混合中心性與其組成部分的肯德?tīng)栂嚓P(guān)系數(shù) Fig.3 The node importance of real networks under different infection rate β and correlation coefficient τ of the mixed centrality and its components

4 結(jié)論

關(guān)鍵節(jié)點(diǎn)的識(shí)別能夠促進(jìn)人們對(duì)網(wǎng)絡(luò)的認(rèn)識(shí)，在諸多領(lǐng)域都具有重大意義，而如何精準(zhǔn)有效識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)一直是復(fù)雜網(wǎng)絡(luò)領(lǐng)域中的一大難題.本文首先在k核分解思想的基礎(chǔ)上提出了一種精準(zhǔn)k核中心性Ak，并將其應(yīng)用到重力中心性中提出了精準(zhǔn)重力中心性AGC，通過(guò)結(jié)合鄰域度中心性、鄰域精準(zhǔn)k核中心性以及精準(zhǔn)重力中心性三者的香農(nóng)熵最終提出了混合中心性MC.在7種不同的真實(shí)網(wǎng)絡(luò)下，通過(guò)對(duì)MC與幾種流行的節(jié)點(diǎn)評(píng)估指標(biāo)進(jìn)行了單調(diào)性和精準(zhǔn)性對(duì)比實(shí)驗(yàn)，數(shù)據(jù)表明MC具備更優(yōu)秀的關(guān)鍵節(jié)點(diǎn)識(shí)別能力.在后續(xù)的研究中，可以將精準(zhǔn)k核應(yīng)用到更多基于k核提出的指標(biāo)中對(duì)其進(jìn)行改進(jìn).