基于信息熵與迭代因子的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)價(jià)方法

汪亭亭 梁宗文 張若曦

(西南石油大計(jì)算機(jī)科學(xué)學(xué)院,成都 610500)

在復(fù)雜網(wǎng)絡(luò)的研究中,如何有效地衡量節(jié)點(diǎn)的重要性一直都是學(xué)者們關(guān)心的問(wèn)題.在節(jié)點(diǎn)重要性研究領(lǐng)域,基于拓?fù)鋵W(xué)信息來(lái)判斷節(jié)點(diǎn)重要性的方法被大量提出,如K-shell 方法.K-shell 是一種尋找可能具有重要影響力節(jié)點(diǎn)的有效方法,在大量的研究工作中被廣泛引用.但是,K-shell 過(guò)多地強(qiáng)調(diào)了中心節(jié)點(diǎn)的影響力,卻忽視了處于網(wǎng)絡(luò)外圍節(jié)點(diǎn)作用力的影響.為了更好地衡量網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)對(duì)傳播的促進(jìn)作用,本文提出了一種基于迭代因子和節(jié)點(diǎn)信息熵的改進(jìn)方法來(lái)評(píng)估各個(gè)層次節(jié)點(diǎn)的傳播能力.為評(píng)價(jià)本文方法的性能,本文采用SIR 模型進(jìn)行仿真實(shí)驗(yàn)來(lái)對(duì)各節(jié)點(diǎn)的傳播效率進(jìn)行評(píng)估,并在實(shí)驗(yàn)中將本文算法和其他算法進(jìn)行了對(duì)比.實(shí)驗(yàn)結(jié)果表明,本文所提方法具有更好的性能,并且適合解決大規(guī)模復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性評(píng)價(jià)問(wèn)題.

1 引言

在網(wǎng)絡(luò)科學(xué)領(lǐng)域中,研究節(jié)點(diǎn)重要性的排序算法一直都是學(xué)者們追隨的熱點(diǎn)話題,其目的是為了通過(guò)對(duì)節(jié)點(diǎn)的重要性排序?qū)ふ页鰧?duì)傳播起關(guān)鍵性作用的節(jié)點(diǎn).在病毒網(wǎng)絡(luò)中通過(guò)對(duì)重要節(jié)點(diǎn)的及時(shí)控制可以抑制病毒大面積的擴(kuò)散[1],在社交網(wǎng)絡(luò)中,商家可以把新產(chǎn)品投放到重要客戶(hù)中,通過(guò)重要客戶(hù)的宣傳實(shí)現(xiàn)投資效益最大化[2].由此可以看出研究網(wǎng)絡(luò)中的重要節(jié)點(diǎn)不僅有重要的理論意義,更有重要的現(xiàn)實(shí)意義.

目前已經(jīng)提出了各種方法來(lái)對(duì)節(jié)點(diǎn)的重要性進(jìn)行排序.在網(wǎng)絡(luò)結(jié)構(gòu)拓?fù)浠A(chǔ)上發(fā)展起來(lái)的經(jīng)典算法有度中心性(DC)[3]、介數(shù)中心性(BC)[4]、接近中心性[5]和h指數(shù)[6]等,這些都是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的經(jīng)典算法[7].另外,pagerank[8]和leaderank[9]是基于隨機(jī)游走的兩個(gè)代表性方法.Kitsak 等[10]提出了K-shell 方法,該方法的算法實(shí)現(xiàn)非常簡(jiǎn)單,有研究顯示該算法對(duì)識(shí)別影響力節(jié)點(diǎn)具有顯著的度量作用[11].但是K-shell(ks)索引對(duì)網(wǎng)絡(luò)拓?fù)淙中畔⒁筝^高且在單調(diào)性(排名列表中擁有相同排名節(jié)點(diǎn)的比例)上表現(xiàn)不佳[12],即在同一個(gè)Kshell(ks)值中的所有節(jié)點(diǎn)都擁有相同的排名,這樣不利于唯一地區(qū)分節(jié)點(diǎn)的排名.之后研究者們?cè)贙-shell 基礎(chǔ)上提出了很多改進(jìn)的方法.Basaras 等[13]提出了基于混合度和K-shell 的算法,該方法提出了μ冪社區(qū)指數(shù)(μ-power community index,μ-PCI).它是K-shell 和中心度的混合,該算法以完全局部化的計(jì)算方式達(dá)到了適用于任何類(lèi)型的網(wǎng)絡(luò).Wang 等[14]利用k-shell 的迭代信息來(lái)區(qū)分具有相同ks 值的節(jié)點(diǎn),并同時(shí)考慮了節(jié)點(diǎn)度來(lái)綜合量化節(jié)點(diǎn)的重要性,具有很好的準(zhǔn)確性.網(wǎng)絡(luò)中少量的節(jié)點(diǎn)具有大量的邊,這些節(jié)點(diǎn)也被稱(chēng)為“富節(jié)點(diǎn)”,它們會(huì)出現(xiàn)傾向于彼此之間相互連接的現(xiàn)象,這種現(xiàn)象一般被稱(chēng)為富人俱樂(lè)部現(xiàn)象[15].如果通過(guò)排序方法選出來(lái)的重要節(jié)點(diǎn)作為種子節(jié)點(diǎn),種子節(jié)點(diǎn)之間具有高度連接,就會(huì)受富人俱樂(lè)部現(xiàn)象的影響,造成大量的活躍節(jié)點(diǎn)在傳播時(shí)出現(xiàn)交叉現(xiàn)象,傳播僅在小范圍內(nèi)擴(kuò)散.而這些以K-shell 為基礎(chǔ)的排序方法,往往無(wú)法避免網(wǎng)絡(luò)中富人俱樂(lè)部現(xiàn)象帶來(lái)的影響.

有研究學(xué)者已經(jīng)提出很多方法來(lái)規(guī)避富人俱樂(lè)部現(xiàn)象的帶來(lái)的影響,使得基于拓?fù)渑判虻姆椒ㄗ兊酶煽?針對(duì)富人俱樂(lè)部現(xiàn)象問(wèn)題,Wang 等[16]提出一種改進(jìn)的K-shell 方法(improved K-shell method,IKS),該方法通過(guò)迭代篩選出K-shell 各層中信息熵最高的節(jié)點(diǎn),從而有效地避免富人俱樂(lè)部現(xiàn)象,實(shí)驗(yàn)表明其對(duì)網(wǎng)絡(luò)中前K 個(gè)節(jié)點(diǎn)的傳播影響力衡量更準(zhǔn)確.但在同一shell 內(nèi)有大量信息熵相等的節(jié)點(diǎn)時(shí),該算法會(huì)隨機(jī)選取其中之一并把其余節(jié)點(diǎn)投入到下次迭代當(dāng)中,這就造成了本來(lái)排名靠前的節(jié)點(diǎn)因無(wú)限迭代而靠后.在Zareie 等[17]所提出的算法中考慮了節(jié)點(diǎn)及其鄰域集的公共層次,將迭代因子(iteration,IT)應(yīng)用于網(wǎng)絡(luò)分層中,使得網(wǎng)絡(luò)中節(jié)點(diǎn)更具有差異性,從而提出一種基于鄰域相關(guān)系數(shù)的關(guān)鍵節(jié)點(diǎn)識(shí)別算法.

受Zareie 等[17]所提算法的啟發(fā),本文沿用迭代因子(iteration,IT)對(duì)網(wǎng)絡(luò)進(jìn)行分層;在改進(jìn)的K-shell 方法(improved K-shell method,IKS)[18]的基礎(chǔ)之上,利用迭代因子來(lái)對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行分層,然后再分別計(jì)算每層中節(jié)點(diǎn)的信息熵,提出了基于迭代因子和信息熵相結(jié)合的方法(簡(jiǎn)稱(chēng)IE+)來(lái)衡量網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性,該方法對(duì)在迭代過(guò)程中因隨機(jī)選擇造成節(jié)點(diǎn)排序靠后的問(wèn)題有所改進(jìn),同時(shí)在具有富人俱樂(lè)部現(xiàn)象的網(wǎng)絡(luò)中進(jìn)行節(jié)點(diǎn)重要性排序時(shí)也具有較好的表現(xiàn).本文在八種常見(jiàn)網(wǎng)絡(luò)數(shù)據(jù)中使用SIR 模型[18,19]來(lái)模擬病毒傳播的過(guò)程,將所提出的算法與常見(jiàn)算法進(jìn)行比較,實(shí)驗(yàn)結(jié)果表明,本文所提方法具有更好的性能,并且適合解決大規(guī)模復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性評(píng)價(jià)問(wèn)題.

本文的其余部分安排如下.第2 節(jié)簡(jiǎn)要敘述了現(xiàn)有的一些經(jīng)典算法.第3 節(jié)中將詳細(xì)闡述本文的算法思想.數(shù)據(jù)集將在第4 節(jié)中介紹.第5 節(jié)將簡(jiǎn)要介紹評(píng)價(jià)指標(biāo).實(shí)驗(yàn)設(shè)置、結(jié)果和討論在第6 節(jié)中提及.最后,在第7 節(jié)中給出結(jié)論.

2 相關(guān)工作

一個(gè)無(wú)向未加權(quán)網(wǎng)絡(luò)通常表示為G=(V,E),其中V和E分別表示節(jié)點(diǎn)和邊的集合.它也可以定義為一個(gè)鄰接矩陣A=(aij)n×n,如果節(jié)點(diǎn)vi和vj有一條邊相連接,則aij=1,否則aij=0.

大部分算法都是基于拓?fù)浣Y(jié)構(gòu),關(guān)注節(jié)點(diǎn)的中心性.此前學(xué)者們提出了許多中心性度量方法,這些方法從不同的角度衡量了節(jié)點(diǎn)的重要性.在這里,簡(jiǎn)要回顧幾個(gè)中心性指標(biāo)的定義.

在度中心性算法中,DC 算法[3]主要考慮了節(jié)點(diǎn)度中心性,并得出節(jié)點(diǎn)鄰居數(shù)量越大傳播能力越強(qiáng);接近中心性(CC)[5]算法則更關(guān)注節(jié)點(diǎn)和整個(gè)網(wǎng)絡(luò)之間的關(guān)系,認(rèn)為節(jié)點(diǎn)與網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間距離的平均值越小,節(jié)點(diǎn)越重要;學(xué)者們還提出了相對(duì)新穎的方法,例如基于重力的方法論上,取兩個(gè)節(jié)點(diǎn)的ks 值作為質(zhì)量,兩個(gè)節(jié)點(diǎn)之間的最短路徑作為距離[20,21],兩個(gè)節(jié)點(diǎn)之間的相互作用關(guān)系隨著他們的距離而減小,模仿重力公式將兩個(gè)節(jié)點(diǎn)間的ks 值的乘積與兩節(jié)點(diǎn)間的最短距離的比值作為衡量節(jié)點(diǎn)傳播能力的度量,從而實(shí)現(xiàn)對(duì)節(jié)點(diǎn)重要性的排序.

Kitsak 等[10]提出了K-shell 方法,該方法認(rèn)為節(jié)點(diǎn)的影響力是由它的位置決定的,而最有影響力的節(jié)點(diǎn)應(yīng)該是網(wǎng)絡(luò)的核心.K-shell 分解是一個(gè)迭代過(guò)程,第一步是刪除所有度數(shù)為1 的節(jié)點(diǎn),直到網(wǎng)絡(luò)中沒(méi)有度數(shù)為1 的節(jié)點(diǎn),被移除節(jié)點(diǎn)ks=1.第二步是從網(wǎng)絡(luò)中移除所有度數(shù)為2 的節(jié)點(diǎn),直到網(wǎng)絡(luò)中沒(méi)有度數(shù)為2 的節(jié)點(diǎn),被移除節(jié)點(diǎn)ks=2.迭代繼續(xù),直到所有節(jié)點(diǎn)都從網(wǎng)絡(luò)中刪除.圖1 列出了一個(gè)包含26 個(gè)節(jié)點(diǎn)和32 條邊的網(wǎng)絡(luò)圖.通過(guò)K-shell分解得到每個(gè)節(jié)點(diǎn)的ks 值.K-shell 算法認(rèn)為ks值越大,傳播影響越大.這意味著在圖1 所示網(wǎng)絡(luò)中,節(jié)點(diǎn)1,2,3,4,5 的影響力最大,而ks=1的節(jié)點(diǎn)傳播影響力最小.在K-shell 的分解過(guò)程中,對(duì)度很大但位于網(wǎng)絡(luò)邊緣節(jié)點(diǎn)的影響力衡量不夠準(zhǔn)確,例如圖1 中的節(jié)點(diǎn)21.研究人員基于K-shell提出了大量的擴(kuò)展方法,如鄰域核心中心性(Cnc)、擴(kuò)展鄰域核心中心性方法(Cnc+)[22]等算法認(rèn)為,一個(gè)節(jié)點(diǎn)的影響不僅取決于它的自己的ks 值,也依賴(lài)于其鄰居節(jié)點(diǎn)的ks 值.

圖1 一個(gè)簡(jiǎn)單示例圖Fig.1.A sample graph.

最近,一些混合的度量方法被陸續(xù)提出.這些方法充分利用節(jié)點(diǎn)的拓?fù)湫畔?利用混合的衡量指標(biāo)從不同的角度來(lái)對(duì)節(jié)點(diǎn)的重要性進(jìn)行評(píng)價(jià).Bha 等[23]提出提高的混合排序方法,該方法結(jié)合了兩個(gè)中心性—擴(kuò)展的鄰居中心性(Cnc+)和h指數(shù)中心性,該方法在排序準(zhǔn)確性上具有很好的性能.阮逸潤(rùn)等[24]提出了基于結(jié)構(gòu)洞引力模型的改進(jìn)算法,綜合考慮節(jié)點(diǎn)h指數(shù)、節(jié)點(diǎn)核數(shù)以及節(jié)點(diǎn)的結(jié)構(gòu)洞位置.

除此之外,在動(dòng)態(tài)網(wǎng)絡(luò)中,網(wǎng)絡(luò)拓?fù)潆S著時(shí)間的推移而不斷變化,導(dǎo)致動(dòng)態(tài)網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的識(shí)別變成一項(xiàng)艱巨的任務(wù).研究者們通過(guò)不同時(shí)間段的網(wǎng)絡(luò)快照信息對(duì)節(jié)點(diǎn)進(jìn)行排名[25-30],Qu 等[31]提出時(shí)態(tài)網(wǎng)絡(luò)中的時(shí)態(tài)信息收集(TIG)過(guò)程,將TIG過(guò)程作為節(jié)點(diǎn)的重要性度量,可用于節(jié)點(diǎn)重要性排名.胡鋼等[32]依托復(fù)雜網(wǎng)絡(luò)的層間時(shí)序關(guān)聯(lián)耦合關(guān)系、層內(nèi)連接關(guān)系和層間逼近關(guān)系構(gòu)建時(shí)序網(wǎng)絡(luò)超鄰接矩陣,提出了基于時(shí)序網(wǎng)絡(luò)層間同構(gòu)率動(dòng)態(tài)演化的超鄰接矩陣建模的重要節(jié)點(diǎn)辨識(shí)方法.

無(wú)論是靜態(tài)網(wǎng)絡(luò)還是動(dòng)態(tài)網(wǎng)絡(luò),它們都遵循冪律網(wǎng)絡(luò)中的一個(gè)重要性質(zhì)就是少數(shù)幾個(gè)節(jié)點(diǎn)連接數(shù)量較多,而連接數(shù)量較多的節(jié)點(diǎn)更愿意去連接比它連接數(shù)量更多或同等多的節(jié)點(diǎn),這時(shí)就造成了富人俱樂(lè)部現(xiàn)象的出現(xiàn).為了避免富人俱樂(lè)部現(xiàn)象對(duì)排序結(jié)果帶來(lái)的影響,Liu 等[27]提出了一種基于每個(gè)節(jié)點(diǎn)的局部索引秩(local index rank,LIR)的算法,可以對(duì)具有富人俱樂(lè)部現(xiàn)象的網(wǎng)絡(luò)中的節(jié)點(diǎn)實(shí)現(xiàn)快速排序;Namtirtha 等[28]提出了一種混合指標(biāo)的度量方法,考慮了節(jié)點(diǎn)的度、節(jié)點(diǎn)間的聯(lián)合影響率和節(jié)點(diǎn)間的最短距離,從網(wǎng)絡(luò)中心到網(wǎng)絡(luò)邊緣來(lái)對(duì)節(jié)點(diǎn)進(jìn)行排序;改進(jìn)的K-shell 算法[16]采用K-shell 分層與節(jié)點(diǎn)信息熵相結(jié)合的方法來(lái)迭代地選取重要節(jié)點(diǎn),考慮了不同shell 層中網(wǎng)絡(luò)節(jié)點(diǎn)的重要性,但該算法會(huì)在具有相同信息熵的節(jié)點(diǎn)中隨機(jī)選擇一個(gè)并把其余節(jié)點(diǎn)投入到下次迭代當(dāng)中,這就造成了本來(lái)排名靠前的節(jié)點(diǎn)因無(wú)限迭代而靠后.受IKS 算法的啟發(fā),本文提出了一種基于迭代因子和信息熵的算法來(lái)識(shí)別從網(wǎng)絡(luò)外圍到核心的每個(gè)網(wǎng)絡(luò)級(jí)別的重要節(jié)點(diǎn),將此方法簡(jiǎn)稱(chēng)為IE+.

3 算法介紹

3.1 迭代因子

在IKS 方法中,網(wǎng)絡(luò)使用K-shell 進(jìn)行分層.從圖1 可以看出,雖然節(jié)點(diǎn)7,8 和9 在同一個(gè)K-shell中,但是節(jié)點(diǎn)7,8 較節(jié)點(diǎn)9 更接近網(wǎng)絡(luò)的核心,當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)被移除時(shí),節(jié)點(diǎn)9 在節(jié)點(diǎn)7,8 之前被移除.與被感染的節(jié)點(diǎn)9 相比,被感染的節(jié)點(diǎn)7,8 可以達(dá)到更好的傳播效果.鑒于K-shell 對(duì)節(jié)點(diǎn)重要性度量不夠完善,本文提出迭代因子(iteration,IT)對(duì)節(jié)點(diǎn)進(jìn)行分層,使得網(wǎng)絡(luò)層次結(jié)構(gòu)更加清晰.

以圖1 為例,設(shè)置迭代因子的初始值IT=1,然后將度數(shù)最小的節(jié)點(diǎn)從網(wǎng)絡(luò)中移除.這些被移除的節(jié)點(diǎn)屬于圖結(jié)構(gòu)的第一層,然后在本次迭代中被刪除節(jié)點(diǎn)的迭代因子IT=1.在下一階段,IT 值增加1,并再次從圖中刪除度最小節(jié)點(diǎn),并將在本次迭代中被刪除節(jié)點(diǎn)的IT=2.這個(gè)過(guò)程會(huì)一直迭代,直到圖中沒(méi)有剩余節(jié)點(diǎn).在每次迭代中,IT 的值都會(huì)加1 并分配給在此階段中被刪除的節(jié)點(diǎn).從圖1可以看出,節(jié)點(diǎn)7,8,9 不再處于同一結(jié)構(gòu)層級(jí),但節(jié)點(diǎn)7 和8 更靠近網(wǎng)絡(luò)中心,因此比節(jié)點(diǎn)9 具有較大的IT 值.同理,對(duì)位于網(wǎng)絡(luò)中心的節(jié)點(diǎn)(如節(jié)點(diǎn)1,2,3,4,5)的網(wǎng)絡(luò)層次劃分更細(xì),節(jié)點(diǎn)5 被認(rèn)為是網(wǎng)絡(luò)的核心,節(jié)點(diǎn)1,2,3 和4 被認(rèn)為是次要核心.

3.2 信息熵

在IKS 算法中,信息熵被定義為

其中j∈Γ(i) 是節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)的集合,其中:

從(1)式和(2)式可以看出,節(jié)點(diǎn)信息熵的計(jì)算主要依賴(lài)于節(jié)點(diǎn)的本地鄰居信息.節(jié)點(diǎn)17,18和19 都在網(wǎng)絡(luò)的外圍,如果僅依靠鄰居的度信息來(lái)計(jì)算節(jié)點(diǎn)的信息熵,那么這三個(gè)節(jié)點(diǎn)的信息熵和ks 值均相同.但節(jié)點(diǎn)17 的鄰居節(jié)點(diǎn)比其他兩個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)更接近網(wǎng)絡(luò)的中心,因而僅依靠鄰居節(jié)點(diǎn)的度信息顯然是不夠的.因此,本文結(jié)合節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置,基于ks 提出一種計(jì)算節(jié)點(diǎn)信息熵的新方法:

其中 (i) 是節(jié)點(diǎn)vi的鄰居集合;Ij的定義如(2)式所示;ksj表示節(jié)點(diǎn)j的ks 值.以節(jié)點(diǎn)17 為例計(jì)算其信息熵:

表1 節(jié)點(diǎn)在每個(gè)shell 中的信息熵Table 1.Information entropy of each node.

表2 節(jié)點(diǎn)在每個(gè)迭代層中的信息熵Table 2.Information entropy of each node.

3.3 算法步驟

本文基于迭代因子(IT),通過(guò)ks 值對(duì)節(jié)點(diǎn)信息熵的計(jì)算進(jìn)行改進(jìn),提出了迭代因子和信息熵相結(jié)合的算法(簡(jiǎn)稱(chēng)IE+)來(lái)對(duì)節(jié)點(diǎn)的重要性程度進(jìn)行度量,該算法的步驟如下:

1) 使用K-shell 算法計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的ks 值,然后令I(lǐng)T=1;

2) 將當(dāng)前網(wǎng)絡(luò)中度最小的節(jié)點(diǎn)的迭代因子記為IT,并根據(jù)(4)式來(lái)計(jì)算這些節(jié)點(diǎn)的信息熵 ei+;

3) 從網(wǎng)絡(luò)中刪除這些度最小的節(jié)點(diǎn);

4) 若網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)為0,記錄IT(max)=前迭代因子IT,跳轉(zhuǎn)步驟5;否則,IT 加1,跳轉(zhuǎn)步驟2;

5) 選擇當(dāng)前迭代因子IT 對(duì)應(yīng)節(jié)點(diǎn)集合中信息熵最大的節(jié)點(diǎn),按序放入節(jié)點(diǎn)重要性排序集合中.如果有多個(gè)節(jié)點(diǎn)信息熵值相等時(shí),按照節(jié)點(diǎn)的序號(hào)從大到小將所有信息熵相等的節(jié)點(diǎn)全部放入重要性排序集合中;

當(dāng)今，大部分高中學(xué)生在學(xué)習(xí)數(shù)學(xué)內(nèi)容時(shí)都喜歡用單一的思維去審視和理解課本，而且都采用的是比較陳舊的方法來(lái)解答習(xí)題，在解題思維上顯得比較呆板，缺乏變通.而習(xí)題又是教師對(duì)學(xué)生傳達(dá)自己解題步驟和核心技巧的載體，所以提高學(xué)生的解題能力至關(guān)重要.

6) 如果IT=0,則跳轉(zhuǎn)步驟7,否則IT 減1,跳轉(zhuǎn)步驟5;

7) 如果網(wǎng)絡(luò)中所有節(jié)點(diǎn)都已經(jīng)被放入重要性節(jié)點(diǎn)排序集合中,則結(jié)束算法;否則,令前迭代因子IT=IT(max),跳轉(zhuǎn)到步驟5.

算法偽代碼如下所示:

計(jì)算出每個(gè)節(jié)點(diǎn)的ks 值和迭代因子IT 后,將迭代因子相同的節(jié)點(diǎn)按照信息熵值降序排列,如表2 所列.然后對(duì)節(jié)點(diǎn)進(jìn)行排序,在最大迭代因子中選擇最大信息熵的節(jié)點(diǎn),顯而易見(jiàn)應(yīng)該選擇節(jié)點(diǎn)5,然后在下一個(gè)迭代因子中選擇節(jié)點(diǎn)1.在下一層中節(jié)點(diǎn)7 和8 具有相同的改進(jìn)的信息熵值.按節(jié)點(diǎn)序號(hào)從大到小順序放入,直到最小的迭代因子層次結(jié)構(gòu)中選擇信息熵最大的節(jié)點(diǎn).此時(shí),第一次迭代結(jié)束,下一次迭代繼續(xù)從迭代因子最高中選擇節(jié)點(diǎn),直到所有節(jié)點(diǎn)都被選中.

在表3 中,使用了不同的方法對(duì)圖1 中的網(wǎng)絡(luò)進(jìn)行排序.因?yàn)槊糠N方法對(duì)節(jié)點(diǎn)重要性的識(shí)別原理不同,可以看出每種方法的排序結(jié)果略有不同.與IKS 算法相比,在迭代次數(shù)相同的情況下,本文算法識(shí)別出的重要節(jié)點(diǎn)在網(wǎng)絡(luò)中的分布更廣,這表明本文算法能更有效地避免在迭代次數(shù)相同時(shí)出現(xiàn)的富人俱樂(lè)部現(xiàn)象.

表3 由不同方法得出的排名: DC,CC,ks,Cnc,Cnc+,IKS,IE+Table 3.The ranking lists determined by different methonds: DC,CC,ks,Cnc,Cnc+,IKS,IE+.

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

選擇了八種不同類(lèi)型的網(wǎng)絡(luò),其詳細(xì)信息見(jiàn)表4.1) NS 是一個(gè)由從事網(wǎng)絡(luò)科學(xué)工作的科學(xué)家組成的合作網(wǎng)絡(luò)[33].2) EEC 描述了一家大型歐洲研究機(jī)構(gòu)成員之間的電子郵件交換[34].3) PB 是美國(guó)政治博客的網(wǎng)絡(luò)[35].4) Facebook 描述了該網(wǎng)站的社交圈[36].5) WV 是一個(gè)維基百科網(wǎng)絡(luò),描述了投票記錄[37].6) Sport 是從體育網(wǎng)絡(luò)收集的有關(guān)Facebook 頁(yè)面上的體育運(yùn)動(dòng)的信息(2017 年1 月)[38].7) Sex 是一個(gè)二分網(wǎng)絡(luò),其中節(jié)點(diǎn)是女性和男性.當(dāng)男性寫(xiě)帖子表明與女性發(fā)生性接觸時(shí),他們之間的聯(lián)系就會(huì)建立起來(lái)[39].8) CondMat 是一個(gè)協(xié)作網(wǎng)絡(luò),涵蓋了凝聚態(tài)類(lèi)別中作者論文之間的科學(xué)合作關(guān)系[40].

5 評(píng)價(jià)指標(biāo)

5.1 SIR

在本文中,使用SIR 模型[18,19]來(lái)驗(yàn)證算法的表現(xiàn)能力.通過(guò)模擬SIR 模型的傳播過(guò)程,可以得到每個(gè)節(jié)點(diǎn)的傳播能力.在SIR 模型中,每個(gè)節(jié)點(diǎn)可以具有三種狀態(tài),即易感狀態(tài)、感染狀態(tài)和恢復(fù)狀態(tài).一開(kāi)始,網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都處于易感狀態(tài),除了原始的受感染節(jié)點(diǎn).在每個(gè)時(shí)間段中,每個(gè)被感染的節(jié)點(diǎn)都會(huì)以β的概率感染那些處于易感狀態(tài)的鄰居節(jié)點(diǎn).同時(shí),受感染節(jié)點(diǎn)將以λ的概率進(jìn)入恢復(fù)狀態(tài)并不會(huì)再次感染,當(dāng)網(wǎng)絡(luò)中沒(méi)有受感染節(jié)點(diǎn)時(shí),此傳播過(guò)程結(jié)束.在選擇傳播值β時(shí),它可以略大于網(wǎng)絡(luò)流行閾值βth=〈k〉/〈k2〉,其中k是平均度,k2是二階平均度[41].不同網(wǎng)絡(luò)中的βth和βc值如表4 所列.當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)時(shí),記錄恢復(fù)的節(jié)點(diǎn)總數(shù),可以用來(lái)衡量節(jié)點(diǎn)的傳播能力,對(duì)每個(gè)節(jié)點(diǎn)重復(fù)該過(guò)程來(lái)衡量它的傳播效率.為了獲得更準(zhǔn)確的實(shí)驗(yàn)數(shù)據(jù),SIR 模型傳播過(guò)程的模擬次數(shù)由網(wǎng)絡(luò)規(guī)模決定,在N＜104的小型網(wǎng)絡(luò)中模擬次數(shù)為1000 次,在N≥ 104大型網(wǎng)絡(luò)中模擬次數(shù)為100 次.

表4 八個(gè)常見(jiàn)網(wǎng)絡(luò)的基本拓?fù)涮卣?N 和|E|是節(jié)點(diǎn)和邊的數(shù)量,〈d〉 和〈k〉 是平均距離和平均度,c 是聚類(lèi)系數(shù),βth 和βc 是流行閾值和傳播值Table 4.The basic topological features of the eight real neworks,N and |E|,|E| are the number of nodes and edges,〈d〉and〈k〉 are the average distance and the average degree,c is the clustering coefficient,βth and βc are the epidemic threshold and the spread value.

5.2 相關(guān)系數(shù)

為了驗(yàn)證本文算法的性能,使用Kendall Tau[42]系數(shù)τ來(lái)衡量不同算法得到的節(jié)點(diǎn)重要性排名表與SIR 模型模擬的排名表之間的相關(guān)性,τ定義為

其中Nc和Nd分別是經(jīng)過(guò)計(jì)算后相關(guān)性一致和不一致的數(shù)量.考慮具有N個(gè)節(jié)點(diǎn)的兩個(gè)相關(guān)序列X和Y,X=(x1,x2,···,xn)和Y=(y1,y2,···,yn).任何一對(duì)二元組(xi,yi)和(xj,yj)(x≠y),當(dāng)xi＞xj和yi＞yj或xi＜xj和yi＜yj這兩個(gè)元素被認(rèn)為是一致的,如果xi＞xj和yi＜yj或xi＜xj和yi＞yj它們是不一致的,如果xi=xj或yi=yj時(shí)不計(jì)入Nc和Nd.系數(shù)必須在—1 ≤τ≤ 1 的范圍內(nèi),τ值越大,算法的排序結(jié)果越接近準(zhǔn)確值.

5.3 單調(diào)關(guān)系

一個(gè)好的節(jié)點(diǎn)重要性排序算法應(yīng)該是每個(gè)節(jié)點(diǎn)都被分配唯一的排名索引,如果在同一排名索引上出現(xiàn)多個(gè)節(jié)點(diǎn),那么這樣的算法被認(rèn)為是存在缺陷的.為了定量測(cè)量不同指標(biāo)的分辨率,使用了排名列表的單調(diào)性指標(biāo)M(R)[22]:

其中Nr是具有相同索引值r的節(jié)點(diǎn)數(shù).如果M(R)=1,表示該算法是完全單調(diào)的,并且每個(gè)節(jié)點(diǎn)被歸類(lèi)為不同的索引值,如果M(R)=0,則所有節(jié)點(diǎn)處于同一等級(jí).單調(diào)性指標(biāo)反映排序算法是否能很好地將節(jié)點(diǎn)區(qū)分開(kāi)來(lái).

5.4 平均最短路徑長(zhǎng)度

計(jì)算每對(duì)傳播者之間的平均最短路徑長(zhǎng)度[43],這是一個(gè)基本指標(biāo).如果每個(gè)節(jié)點(diǎn)感染其他節(jié)點(diǎn)的概率相同,則初始感染節(jié)點(diǎn)越分散,傳播范圍越廣.本文選擇初始節(jié)點(diǎn)S作為度量,其定義為

其中|S|和S 分別表示選擇的種子節(jié)點(diǎn)的數(shù)量和選擇的初始節(jié)點(diǎn)集合;duv是從節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的長(zhǎng)度.

6 實(shí) 驗(yàn)

6.1 相關(guān)系數(shù)

在表5 中顯示了所提出的方法以及其他索引方法與SIR 模型模擬得出的排名R之間的Kendallτ秩相關(guān)系數(shù),在表中加粗字體對(duì)應(yīng)最優(yōu)值.從表5可以看出經(jīng)典DC 網(wǎng)絡(luò)算法的性能并不太理想,在Sex 網(wǎng)絡(luò)中,雖然IE+算法表現(xiàn)不是最佳,但與最優(yōu)值對(duì)應(yīng)的算法Cnc+相比相差不大,盡管本文提出的IE+算法并不是在所有網(wǎng)絡(luò)中都表現(xiàn)最好,但在大多數(shù)網(wǎng)絡(luò)中比其他算法更具有表現(xiàn)力.

表5 SIR 模型中節(jié)點(diǎn)影響指數(shù)R 與五個(gè)中心性指數(shù)之間的Kendall TauTable 5.The Kendall Tau between the node influence index R of SIR model and five centrality indices.

6.2 單調(diào)關(guān)系

本文對(duì)各算法單調(diào)性進(jìn)行了度量.算法的單調(diào)性越高說(shuō)明該方法在確定唯一排名的能力越強(qiáng),在表中加粗字體對(duì)應(yīng)最優(yōu)值.從表6 可以看出,在大多數(shù)網(wǎng)絡(luò)中,本文提出的IE+算法與IKS 方法相比單調(diào)性較強(qiáng).雖然在一些網(wǎng)絡(luò)(如NS,EEC 等網(wǎng)絡(luò))單調(diào)性上表現(xiàn)不是最佳的,但在較大網(wǎng)絡(luò)上本文算法單調(diào)性要比其它算法單調(diào)性要高.

表6 不同排序方法的單調(diào)性 MTable 6.The monotonicity M of different ranking methods.

6.3 平均最短路徑長(zhǎng)度

為避免富人俱樂(lè)部現(xiàn)象帶來(lái)的影響,將排序得到的重要節(jié)點(diǎn)作為初始感染節(jié)點(diǎn),在傳播中當(dāng)節(jié)點(diǎn)的感染概率相等時(shí),為得到更廣的傳播范圍則需要更多的初始感染節(jié)點(diǎn)分散在網(wǎng)絡(luò)中.本文進(jìn)一步測(cè)試了不同算法下不同比例的初始感染節(jié)點(diǎn)之間的平均最短距離.如圖2 所示,通過(guò)不同算法排序得出的節(jié)點(diǎn)集合,選取了前2%—20%的重要節(jié)點(diǎn),發(fā)現(xiàn),除了EEC 網(wǎng)絡(luò),隨著初始感染節(jié)點(diǎn)的比例不斷擴(kuò)大,重要節(jié)點(diǎn)之間的平均距離也在相應(yīng)擴(kuò)大.這更進(jìn)一步說(shuō)明了本文提出的IE+算法在避免富人俱樂(lè)部現(xiàn)象方面具有較為優(yōu)秀的表現(xiàn).

圖2 不同方法下不同比例源擴(kuò)散器的平均最短路徑長(zhǎng)度Ls (a) NS;(b) EEC;(c) PB;(d) Facebook;(e) WV;(f) Sport;(g)Sex;(h) CondMatFig.2.Average shortest path length Ls under different proportion of source spreaders by different methods: (a) NS;(b) EEC;(c) PB;(d) Facebook;(e) WV;(f) Sport;(g) Sex;(h) CondMat.

6.4 重要節(jié)點(diǎn)性能

對(duì)節(jié)點(diǎn)進(jìn)行排序的最終目的是為了挖掘出對(duì)傳播過(guò)程起關(guān)鍵作用的節(jié)點(diǎn),換句話說(shuō),如果通過(guò)排序算法得到的重要節(jié)點(diǎn)對(duì)傳播過(guò)程起不到很好的作用,那么這樣的排序算法是不可靠的.本小節(jié)中從不同角度來(lái)評(píng)判IE+算法識(shí)別的重要節(jié)點(diǎn)的在網(wǎng)絡(luò)傳播中的表現(xiàn)情況.因在此部分討論的是前k個(gè)重要節(jié)點(diǎn)在網(wǎng)絡(luò)中的傳播規(guī)模,本文引入一些個(gè)經(jīng)典的影響力最大化算法(CI[44],CELF++[45],IRIE[46])作為比較算法.

在圖3 中,選擇網(wǎng)絡(luò)中排名靠前的2%—20%個(gè)節(jié)點(diǎn),計(jì)算在感染值為βc=2βth,λ=1,t=20 時(shí)感染的節(jié)點(diǎn)總數(shù)(不包括初始感染節(jié)點(diǎn))與網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的百分比.我們驚訝地發(fā)現(xiàn)在大多數(shù)網(wǎng)絡(luò)中,在CC,Cnc+,ks,IKS 算法下,隨著種子節(jié)點(diǎn)數(shù)的增加,感染的節(jié)點(diǎn)總數(shù)反而在減少,這種現(xiàn)象是因?yàn)殡S著種子節(jié)點(diǎn)越來(lái)越緊密地聚集在一起,它們開(kāi)始重疊,無(wú)法再有效地傳播.而在NS,Facebook,Sex 和CondMat 網(wǎng)絡(luò)中,IE+算法隨著初始感染節(jié)點(diǎn)總數(shù)的增加相應(yīng)的感染節(jié)點(diǎn)總數(shù)也在增加,在其余網(wǎng)絡(luò)中雖然IE+算法隨著初始感染節(jié)點(diǎn)的增加而略有下降,但下降趨勢(shì)相對(duì)緩慢.除EEC的其余網(wǎng)絡(luò)中,IE+算法優(yōu)于經(jīng)典的影響力最大化算法(CI,CELF++,IRIE),或與其表現(xiàn)出相同的優(yōu)勢(shì).

圖3 比較在相同時(shí)間內(nèi)感染節(jié)點(diǎn)總數(shù)的百分比 (a) NS;(b) EEC;(c) PB;(d) Facebook;(e) WV;(f) Sport;(g) Sex;(h) CondMatFig.3.Compare the percentage of the total number of infected nodes over the same time period: (a) NS;(b) EEC;(c) PB;(d) Facebook;(e) WV;(f) Sport;(g) Sex;(h) CondMat.

在六個(gè)網(wǎng)絡(luò)中,通過(guò)各排序算法計(jì)算后,選擇排在前 10%的節(jié)點(diǎn)作為初始感染節(jié)點(diǎn).在上述相同的感染概率和恢復(fù)率下,記錄不同傳播時(shí)間感染節(jié)點(diǎn)數(shù)與總節(jié)點(diǎn)數(shù)的百分比.從圖4 可以看出,隨著時(shí)間的增加,感染節(jié)點(diǎn)的數(shù)量先增加后趨于穩(wěn)定,該現(xiàn)象是因?yàn)殡S著傳播時(shí)間達(dá)到一定的時(shí)長(zhǎng)時(shí),網(wǎng)絡(luò)處于穩(wěn)定狀態(tài).在NS,Facebook,WV,Sport和CondMat 網(wǎng)絡(luò)中,本文提出的IE+算法具有最廣泛的傳播范圍.

圖4 比較不同傳播時(shí)間 t 中前 10% 種子節(jié)點(diǎn)感染節(jié)點(diǎn)的百分比 (a) NS;(b) Facebook;(c) WV;(d) Sex;(f) Sport;(f) CondMatFig.4.Compare the percentage of nodes infected by the top 10% of seed nodes in different propagation time t: (a) NS;(b) Facebook;(c) WV;(d) Sex;(f) Sport;(f) CondMat.

6.5 時(shí)間復(fù)雜度

在時(shí)間復(fù)雜度方面,由于需要節(jié)點(diǎn)的ks 值來(lái)計(jì)算節(jié)點(diǎn)的信息熵,所以本文所提出的IE+算法的時(shí)間復(fù)雜度主要體現(xiàn)在迭代因子IT 和ks 值的計(jì)算上.計(jì)算節(jié)點(diǎn)迭代因子IT 和節(jié)點(diǎn)的ks 值的時(shí)間復(fù)雜度都是O(n),即本文算法的時(shí)間復(fù)雜度是O(n),IKS,Cnc,Cnc+,DC,ks 的時(shí)間復(fù)雜度都是O(n),CC 的時(shí)間復(fù)雜度為O(mn).因此,就時(shí)間復(fù)雜度而言,我們的算法并不比其他算法具有更高的時(shí)間復(fù)雜度.在相同的時(shí)間復(fù)雜度下,IE+算法在幾個(gè)考察指標(biāo)上都具有良好的表現(xiàn).

7 結(jié)論

在復(fù)雜網(wǎng)絡(luò)分析中,對(duì)節(jié)點(diǎn)的影響力進(jìn)行識(shí)別和排序是一個(gè)基礎(chǔ)性工作.本文的研究目的是將信息熵與迭代因子相結(jié)合,提出一種新的節(jié)點(diǎn)影響力評(píng)價(jià)指標(biāo),通過(guò)排序算法得到的重要節(jié)點(diǎn)即使在受到富人俱樂(lè)部現(xiàn)象的影響下也依然具有很好的傳播效果,基于該指標(biāo),利用迭代因子和改進(jìn)的信息熵,提出了衡量節(jié)點(diǎn)重要性方法IE+.通過(guò)在Kendall Tau 相關(guān)系數(shù)、單調(diào)性、平均最短距離以及節(jié)點(diǎn)性能上的對(duì)比實(shí)驗(yàn),表明本文提出的算法能有效對(duì)節(jié)點(diǎn)的重要性進(jìn)行評(píng)估,并能很好地規(guī)避富俱樂(lè)部現(xiàn)象,對(duì)復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn)識(shí)別工作具有較強(qiáng)的借鑒意義.