阮逸潤 老松楊 湯俊 白亮 郭延明

(國防科技大學(xué)系統(tǒng)工程學(xué)院,長沙 410073)

如何用定量分析的方法識別復(fù)雜網(wǎng)絡(luò)中哪些節(jié)點(diǎn)最重要,或評價某個節(jié)點(diǎn)相對于其他一個或多個節(jié)點(diǎn)的重要程度,是復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)問題.目前已有多種有效模型被提出用于識別網(wǎng)絡(luò)重要節(jié)點(diǎn).其中,引力模型將節(jié)點(diǎn)的核數(shù)(網(wǎng)絡(luò)進(jìn)行k-核分解時的ks 值)看作物體的質(zhì)量,將節(jié)點(diǎn)間的最短距離看作物體間距離,綜合考慮了節(jié)點(diǎn)局部信息和路徑信息用于識別網(wǎng)絡(luò)重要節(jié)點(diǎn).然而,僅將節(jié)點(diǎn)核數(shù)表示為物體的質(zhì)量考慮的因素較為單一,同時已有研究表明網(wǎng)絡(luò)在進(jìn)行k-核分解時容易將具有局部高聚簇特征的類核團(tuán)節(jié)點(diǎn)識別為核心節(jié)點(diǎn),導(dǎo)致算法不夠精確.基于引力方法,綜合考慮節(jié)點(diǎn)H 指數(shù)、節(jié)點(diǎn)核數(shù)以及節(jié)點(diǎn)的結(jié)構(gòu)洞位置,本文提出了基于結(jié)構(gòu)洞引力模型的改進(jìn)算法 (improved gravity method based on structure hole method,ISM)及其擴(kuò)展算法ISM+.在多個經(jīng)典的實(shí)際網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上利用SIR (susceptible-infected-recovered)模型對傳播過程進(jìn)行仿真,結(jié)果表明所提算法與其他中心性指標(biāo)相比能夠更好地識別復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn).

1 引言

網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序是網(wǎng)絡(luò)科學(xué)領(lǐng)域研究的重點(diǎn)和熱點(diǎn),是為了挖掘能在更大程度上影響網(wǎng)絡(luò)結(jié)構(gòu)和功能的關(guān)鍵節(jié)點(diǎn)[1].設(shè)計(jì)能夠快速、準(zhǔn)確地識別網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的算法在理論研究和生活實(shí)踐上都具有重要意義.例如對病毒傳播網(wǎng)絡(luò),有選擇性地控制網(wǎng)絡(luò)中的一些重要節(jié)點(diǎn)或改變其結(jié)構(gòu)屬性,如接種疫苗、斷邊重連或漏洞修復(fù)等[2,3],就可以有效降低病毒的傳播速度并減小擴(kuò)散范圍;在軍事供應(yīng)鏈網(wǎng)絡(luò)中,尋找關(guān)鍵節(jié)點(diǎn)并進(jìn)行重點(diǎn)保護(hù),可以提高物資保障的可靠性和效率,有效完成后勤保障任務(wù);在社交網(wǎng)絡(luò)中,通過一定策略選擇有影響力的用戶(如明星、網(wǎng)絡(luò)紅人等)做新產(chǎn)品的推廣和營銷,使產(chǎn)品信息在網(wǎng)絡(luò)中得到大范圍傳播從而增加營收效益[4].

關(guān)于如何挖掘網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn),已經(jīng)有了許多研究成果,典型的指標(biāo)有度中心性(degree)[5]、半局部度(semi-local)[6]、接近中心性(closeness)[7]、介數(shù)中心性(betweenness)[8]、k-核分解方法(k-shell decomposition)[9]和H指數(shù)[10]等,度中心性指標(biāo)考慮了節(jié)點(diǎn)的直接鄰居數(shù)量,雖然簡單直觀,但卻把每一個鄰居節(jié)點(diǎn)看作是同等重要的,而實(shí)際上鄰居節(jié)點(diǎn)間存在差異,不同的鄰居對于目標(biāo)節(jié)點(diǎn)的重要性可能大不相同,因而在很多場景下不夠精確.半局部度指標(biāo)考慮了節(jié)點(diǎn) 4 層鄰居的信息,在提高算法精度的同時還兼顧了算法的效率.接近中心性和介數(shù)中心性都假設(shè)網(wǎng)絡(luò)中的信息是基于最短路徑進(jìn)行傳播,實(shí)際上多數(shù)真實(shí)場景下信息傳播具有隨機(jī)性.k-核分解方法認(rèn)為網(wǎng)絡(luò)節(jié)點(diǎn)的重要性由節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置所決定,節(jié)點(diǎn)越接近核心層重要性越高,邊緣節(jié)點(diǎn)重要性最低.k-核分解方法計(jì)算復(fù)雜度低,適用于大型復(fù)雜網(wǎng)絡(luò),可以很好地應(yīng)用于尋找疾病傳播網(wǎng)絡(luò)中最有影響力的節(jié)點(diǎn),但由于無法區(qū)分處于同一殼層節(jié)點(diǎn)的重要性,因此通常被認(rèn)為是一種粗?；呐判蚍椒?隨后提出了許多改進(jìn)的策略,如領(lǐng)域核數(shù)算法[11]及混合度分解(mixed degree decomposition,MDD)[12]等.H指數(shù)表示一個節(jié)點(diǎn)的H指數(shù)如果是h,就說明這個節(jié)點(diǎn)至少有h個鄰居,且它們的度都不小于h,H指數(shù)在一些場景中的綜合表現(xiàn)要好于度和核數(shù).

最近有學(xué)者指出,通過對不同的排序指標(biāo)或策略進(jìn)行融合可以獲得更好的排序結(jié)果[13].目前大多數(shù)指標(biāo)都是從某一特定角度衡量節(jié)點(diǎn)重要性,有一定適用性的同時也有一定的不足.如果可以將一些從不同角度對節(jié)點(diǎn)重要性進(jìn)行評價的指標(biāo)進(jìn)行融合,則排序結(jié)果將更加全面和可信[14].韓忠民等[15]基于ListNet 的排序?qū)W習(xí)方法融合結(jié)構(gòu)洞、介數(shù)等7 個度量指標(biāo),能夠較為全面地評估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性.Wang 等[16]設(shè)計(jì)了一種基于節(jié)點(diǎn)位置和鄰域信息的多屬性排序方法,該方法利用k-核分解中的迭代信息來進(jìn)一步區(qū)分節(jié)點(diǎn)位置,并充分考慮鄰域?qū)?jié)點(diǎn)影響能力的作用,具有較低的計(jì)算復(fù)雜度.閆光輝等[17]以網(wǎng)絡(luò)模體[18,19]為基本單元研究網(wǎng)絡(luò)高階結(jié)構(gòu),并進(jìn)一步引入證據(jù)理論[20,21]設(shè)計(jì)了一種融合節(jié)點(diǎn)高階信息和低階結(jié)構(gòu)信息的重要節(jié)點(diǎn)挖掘算法.根據(jù)滲流理論[22],去除一個網(wǎng)絡(luò)節(jié)點(diǎn)后,剩余網(wǎng)絡(luò)與原始網(wǎng)絡(luò)之間存在傳播閾值上的差異,Zhong 等[23]認(rèn)為這種傳播閾值差異可以用于表征節(jié)點(diǎn)的全局影響力,通過考慮傳播閾值差異和度中心性,提出了一種融合局部與全局結(jié)構(gòu)的重要節(jié)點(diǎn)識別算法.

受到萬有引力公式啟發(fā),Ma 等[24]提出了一種綜合考慮節(jié)點(diǎn)鄰居信息和路徑信息的引力方法,其中節(jié)點(diǎn)核數(shù)被看作節(jié)點(diǎn)的質(zhì)量,節(jié)點(diǎn)間的最短距離看作物體間距離.然而,僅將核數(shù)表示為物體的質(zhì)量,考慮的因素較為單一.此外,算法利用節(jié)點(diǎn)與鄰域節(jié)點(diǎn)間的相互作用力來量化節(jié)點(diǎn)的影響力,容易將局部呈高聚簇特征的節(jié)點(diǎn)誤判為重要度高的節(jié)點(diǎn),實(shí)際上傳播從這類節(jié)點(diǎn)發(fā)起,容易局限在小團(tuán)體內(nèi)部,不利于傳播快速向外部蔓延.由此,本文將節(jié)點(diǎn)核數(shù)作為度量節(jié)點(diǎn)全局重要性的指標(biāo),融合節(jié)點(diǎn)H指數(shù)重新定義節(jié)點(diǎn)的質(zhì)量,并結(jié)合節(jié)點(diǎn)的結(jié)構(gòu)洞特征,設(shè)計(jì)了引力模型的改進(jìn)算法ISM及ISM+.在多個真實(shí)世界網(wǎng)絡(luò)和人工網(wǎng)絡(luò)中的實(shí)驗(yàn)表明,所提算法在識別節(jié)點(diǎn)影響力方面相比介數(shù)中心性、接近中心性、度中心性,引力模型,MDD,局部引力模型[25]以及基于k-核分解方法的引力模型(KSGC)指標(biāo)[26]等算法更有優(yōu)勢.

2 相關(guān)概念

對于給定的復(fù)雜網(wǎng)絡(luò)G=(N,E),其中N表示節(jié)點(diǎn)集,E表示邊集,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)通常用鄰接矩陣A=(aij)N×N表示.鄰接矩陣中的元素aij可以描述節(jié)點(diǎn)之間的連接關(guān)系,aij=1 表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在連接邊,否則aij=0 .

2.1 度中心性、接近中心性和介數(shù)中心性

度排序方法[5]最為簡單直觀,表示節(jié)點(diǎn)的鄰居數(shù)量,表示為

度指標(biāo)反映了節(jié)點(diǎn)的直接影響力,節(jié)點(diǎn)上的鏈接數(shù)越多,節(jié)點(diǎn)度ki越大,因?yàn)橹豢紤]了節(jié)點(diǎn)局部信息,因而是一種局部中心性指標(biāo).

接近中心性[7]認(rèn)為一個節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的平均距離越小,節(jié)點(diǎn)重要性越高,表示為

其中,dij代表節(jié)點(diǎn)i和j之間的距離,N表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù).

介數(shù)中心性[8]描述了節(jié)點(diǎn)對網(wǎng)絡(luò)中沿最短路徑傳播的信息流的控制力,定義為

其中,gst表示網(wǎng)絡(luò)中除了節(jié)點(diǎn)i以外任意節(jié)點(diǎn)對(如節(jié)點(diǎn)s和節(jié)點(diǎn)t)之間的最短路徑數(shù),表示當(dāng)中經(jīng)過節(jié)點(diǎn)i的最短路徑數(shù).

2.2 H 指數(shù)

H指數(shù)[10]最初用于度量一個科學(xué)家最多有多少篇論文且每篇被引用的次數(shù)都不少于這個篇數(shù),Lü等[10]將其引用到網(wǎng)絡(luò)中,認(rèn)為一個節(jié)點(diǎn)的H指數(shù)如果是h,就說明這個節(jié)點(diǎn)有h個鄰居,它們的度都不小于h,表示為

其中,kjs表示節(jié)點(diǎn)i的第s個鄰居的度數(shù).在(4)式中,算子H返回最大整數(shù)h,使得節(jié)點(diǎn)i至少有h個鄰居的度數(shù)不低于h.

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

結(jié)構(gòu)洞[27]指網(wǎng)絡(luò)結(jié)構(gòu)中不存在冗余聯(lián)系的兩個人之間的缺口,網(wǎng)絡(luò)中占據(jù)結(jié)構(gòu)洞位置的個體相比其鄰居節(jié)點(diǎn)可以獲得更多的競爭優(yōu)勢,包括信息優(yōu)勢和控制優(yōu)勢,從而影響甚至控制社會關(guān)系與信息的傳播.為了量化結(jié)構(gòu)洞節(jié)點(diǎn)對這些關(guān)系的控制,Burt[27]提出網(wǎng)絡(luò)約束系數(shù)這一定量化指標(biāo)來衡量節(jié)點(diǎn)形成結(jié)構(gòu)洞所受到的約束,表示為

其中,節(jié)點(diǎn)q表示i和j之間的共同鄰居,μij表示節(jié)點(diǎn)i為維持與節(jié)點(diǎn)j的關(guān)系而投入的精力占總精力的比例.

式中,Γ(i) 表示節(jié)點(diǎn)i的鄰居集合,當(dāng)i和j之間存在連邊時,zij=1,反之zij=0 .

2.4 引力模型、局部引力模型以及KSGC指標(biāo)模型

Ma 等[22]認(rèn)為如果節(jié)點(diǎn)的鄰域節(jié)點(diǎn)具有更高的ks值,則節(jié)點(diǎn)更有可能是網(wǎng)絡(luò)中的核心節(jié)點(diǎn);另一方面,兩個節(jié)點(diǎn)之間的相互作用效應(yīng)會隨距離的增加而減小.通過將節(jié)點(diǎn)的ks 值看作節(jié)點(diǎn)的質(zhì)量,節(jié)點(diǎn)間的最短距離看作物體間距離,提出了一種綜合考慮節(jié)點(diǎn)鄰居信息和路徑信息的節(jié)點(diǎn)重要性排序指標(biāo),,表示為

其中,φi表示距離節(jié)點(diǎn)i小于或等于給定值r的鄰域節(jié)點(diǎn)集,ksi和ksj分別表示節(jié)點(diǎn)i和j的k-核分解值,dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離.根據(jù)(7)式進(jìn)一步擴(kuò)展得到擴(kuò)展引力中心性指標(biāo)指數(shù)標(biāo)記為(Gravity+),其定義為

Λi表示節(jié)點(diǎn)i的直接鄰居.

類似于引力中心性指標(biāo),Li 等[25]認(rèn)為度大的節(jié)點(diǎn)往往有更大的影響力,同時節(jié)點(diǎn)對其鄰近節(jié)點(diǎn)的影響更大,將節(jié)點(diǎn)的度看作物體的質(zhì)量,由此也提出了一種綜合考慮節(jié)點(diǎn)鄰居信息和路徑信息的局部引力模型來評估網(wǎng)絡(luò)節(jié)點(diǎn)的重要性,定義為

其中,ki和kj分別表示節(jié)點(diǎn)i和j的度,R表示網(wǎng)絡(luò)截?cái)喟霃?是網(wǎng)絡(luò)最短路徑平均值的一半.

Yang 等[26]指出節(jié)點(diǎn)的位置是節(jié)點(diǎn)在網(wǎng)絡(luò)中的一個重要屬性,而多數(shù)節(jié)點(diǎn)重要性評估算法卻很少考慮節(jié)點(diǎn)的位置.由此他們設(shè)計(jì)了一種基于k-核分解方法的引力模型的改進(jìn)方法KSGC,用于識別復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的傳播影響力,表示為

3 算法設(shè)計(jì)與評價標(biāo)準(zhǔn)

3.1 基于引力方法的節(jié)點(diǎn)重要性排序方法

引力模型僅將核數(shù)表示為物體的質(zhì)量,考慮的因素較為單一,節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置,是節(jié)點(diǎn)的重要屬性,這里的位置不僅指節(jié)點(diǎn)基于全局信息的k核中心性,還包括基于局部信息的結(jié)構(gòu)洞位置.此外,H指數(shù)也是一個很好的度量節(jié)點(diǎn)重要性的指標(biāo),當(dāng)一個節(jié)點(diǎn)核數(shù)和H指數(shù)較高,同時還占據(jù)較多的結(jié)構(gòu)洞時,該節(jié)點(diǎn)往往具有更大的影響力.基于以上分析,本文構(gòu)造了基于引力方法的節(jié)點(diǎn)重要度排序方法ISM 及其擴(kuò)展算法ISM+,基本思想是: 綜合考慮節(jié)點(diǎn)局部拓?fù)湫畔?H指數(shù))和全局位置信息(k-核中心性)并將其看作物體質(zhì)量的同時,融合節(jié)點(diǎn)的結(jié)構(gòu)洞特征以此消減網(wǎng)絡(luò)偽核心節(jié)點(diǎn)重要度排序虛高對算法排序準(zhǔn)確性的影響,利用節(jié)點(diǎn)與領(lǐng)域節(jié)點(diǎn)間的相互作用力來描述節(jié)點(diǎn)的傳播影響力.

由于節(jié)點(diǎn)核數(shù)和H指數(shù)不是同一個量綱,二者不能直接融合,為了融合節(jié)點(diǎn)這兩方面的結(jié)構(gòu)特征,引入一個均衡因子γ,定義為網(wǎng)絡(luò)平均核數(shù)值與網(wǎng)絡(luò)平均H指數(shù)之比,表達(dá)式為

其中,〈ks〉表 示網(wǎng)絡(luò)平均核數(shù)值,〈h〉表示網(wǎng)絡(luò)平均H指數(shù).由此,將節(jié)點(diǎn)局部信息和節(jié)點(diǎn)全局位置信息進(jìn)行融合,得到節(jié)點(diǎn)i的質(zhì)量m(i),定義為

Liu 等[28]指出k-核分解方法分解網(wǎng)絡(luò)時容易將類核團(tuán)節(jié)點(diǎn)錯誤識別為網(wǎng)絡(luò)核心,類核團(tuán)內(nèi)節(jié)點(diǎn)彼此緊密相連,與網(wǎng)絡(luò)的其他部分幾乎沒有聯(lián)系.實(shí)際上H指數(shù)在衡量節(jié)點(diǎn)的傳播影響力時也存在類似問題,對于類核團(tuán)節(jié)點(diǎn),H指數(shù)同樣會賦予這個節(jié)點(diǎn)高h(yuǎn)值.而那些不僅彼此之間連接十分緊密,且與核心之外的節(jié)點(diǎn)還存在大量連接的節(jié)點(diǎn),則是網(wǎng)絡(luò)的真核心.綜上,對于一個高ks值或高h(yuǎn)值節(jié)點(diǎn),如果該節(jié)點(diǎn)同時占據(jù)著較多結(jié)構(gòu)洞,那么該節(jié)點(diǎn)很可能是網(wǎng)絡(luò)的重要節(jié)點(diǎn).因此,我們進(jìn)一步引入網(wǎng)絡(luò)約束系數(shù)[27]來度量節(jié)點(diǎn)的結(jié)構(gòu)洞特征,根據(jù)鄰域節(jié)點(diǎn)間的連接情況對節(jié)點(diǎn)重要度排序值進(jìn)行校正,從而消減k-核分解方法和H指數(shù)識別出的類核團(tuán)節(jié)點(diǎn)重要度排序虛高對算法精度的影響,節(jié)點(diǎn)i的重要度校正函數(shù)ω(i) 定義為

e 是自然常數(shù),0＜ω(i) ≤1,Ci表示節(jié)點(diǎn)形成結(jié)構(gòu)洞所受到的約束(見(5)式),當(dāng)節(jié)點(diǎn)i的度越大且占據(jù)的結(jié)構(gòu)洞越多,節(jié)點(diǎn)的網(wǎng)絡(luò)約束系數(shù)Ci值越小,ω(i) 的值越大.反之,節(jié)點(diǎn)i的度越小且鄰居之間的閉合程度越高,節(jié)點(diǎn)網(wǎng)絡(luò)約束系數(shù)Ci值越大,ω(i)的值越小.最后,模擬萬有引力公式的形式,綜合考慮節(jié)點(diǎn)i與領(lǐng)域節(jié)點(diǎn)間的相互作用力,定義節(jié)點(diǎn)i的重要度 I SM(i),

其中,ψi是到節(jié)點(diǎn)i的距離小于或等于給定值r的鄰域節(jié)點(diǎn)集,為了降低算法復(fù)雜度,參照文獻(xiàn)[24]將r值設(shè)為3.進(jìn)一步,本文設(shè)計(jì)了ISM 的擴(kuò)展算法ISM+,定義為

其中,0≤θ≤1,對于較小的θ,ISM+方法會削弱具有較大ISM 值的有影響力鄰居的影響,而較大的θ值則會增強(qiáng)具有較大ISM 值的有影響力鄰居的影響.不失一般性,后續(xù)實(shí)驗(yàn)中θ都取為0.8.

相比引力模型只考慮節(jié)點(diǎn)核數(shù)及節(jié)點(diǎn)的路徑信息,ISM 與ISM+算法在幾乎不增加算法計(jì)算時間的情況下,融合了節(jié)點(diǎn)的多種屬性信息,包括節(jié)點(diǎn)H指數(shù)、節(jié)點(diǎn)位置、節(jié)點(diǎn)結(jié)構(gòu)洞特征和節(jié)點(diǎn)的路徑信息,從而可以更準(zhǔn)確地對節(jié)點(diǎn)重要度進(jìn)行排序.

3.2 評價標(biāo)準(zhǔn)

本文基于經(jīng)典的SIR (susceptible-infectedrecovered)[2,29]傳播動力學(xué)模型模擬網(wǎng)絡(luò)中信息傳播過程.在SIR 模型中,節(jié)點(diǎn)可能處于以下3 種狀態(tài): 1)易受感染(susceptible,S)狀態(tài);2)已被感染(infected,I)狀態(tài);3)恢復(fù)(removed,R)狀態(tài).處于狀態(tài)I 的節(jié)點(diǎn)將以一定的傳播率β將疾病傳播給處于狀態(tài)S 的鄰居節(jié)點(diǎn),節(jié)點(diǎn)被感染后以概率λ被治愈呈恢復(fù)狀態(tài)R,此后不再被感染.當(dāng)網(wǎng)絡(luò)中不再有狀態(tài)I 的節(jié)點(diǎn)出現(xiàn)時傳播過程終止.不失一般性,本文所有實(shí)驗(yàn)均考慮恢復(fù)率λ=1 的情況.節(jié)點(diǎn)經(jīng)過M次SIR 信息傳播實(shí)驗(yàn)后的傳播能力定義為表示其中一次傳播實(shí)驗(yàn)中,節(jié)點(diǎn)i作為起始傳播源傳播過程終止時處于狀態(tài)R 的節(jié)點(diǎn)總數(shù).

為了驗(yàn)證所提算法相比其他指標(biāo)對于節(jié)點(diǎn)重要性排序結(jié)果的準(zhǔn)確性,本文采用Kendall tau 相關(guān)系數(shù)[30,31]來度量不同重要性度量指標(biāo)得到的節(jié)點(diǎn)重要性排序列表與基于SIR 模型得到的節(jié)點(diǎn)傳播影響力排序列表之間的相關(guān)性,其表達(dá)式為

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

實(shí)驗(yàn)選取了6 個來自不同領(lǐng)域的真實(shí)數(shù)據(jù)集,分別是安然郵件網(wǎng)絡(luò)Enron[32],Slavo Zitnik 的朋友圈關(guān)系網(wǎng)絡(luò)Facebook[33],科學(xué)家合作網(wǎng)絡(luò)Netscience[34],美國航空網(wǎng)絡(luò)USAir[35],人群感染網(wǎng)絡(luò)Infectious[36]以及網(wǎng)頁網(wǎng)絡(luò)EPA[34].表1 列出這些網(wǎng)絡(luò)的統(tǒng)計(jì)特征,包括網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)N,網(wǎng)絡(luò)連邊數(shù)E,節(jié)點(diǎn)間平均最短距離〈d〉,節(jié)點(diǎn)平均度〈k〉,網(wǎng)絡(luò)集聚系數(shù)C,網(wǎng)絡(luò)直徑D,網(wǎng)絡(luò)最大ks值ksmax,信息傳播閥值βth=〈k〉/〈k2〉以及信息傳播率β,其中〈k2〉表示節(jié)點(diǎn)二階平均度.

4.1 真實(shí)網(wǎng)絡(luò)

首先使用第3 節(jié)中介紹的SIR 模型分析不同算法排序結(jié)果與節(jié)點(diǎn)真實(shí)傳播能力之間的相關(guān)性,按表1 中的β值設(shè)置6 個網(wǎng)絡(luò)的感染概率,獨(dú)立運(yùn)行1000 次取平均結(jié)果,相關(guān)程度越高,表明相應(yīng)算法得到的節(jié)點(diǎn)重要性排序結(jié)果越準(zhǔn)確.

表1 6 個真實(shí)網(wǎng)絡(luò)的拓?fù)浣y(tǒng)計(jì)參數(shù)Table 1. Topological parameters of six real networks.

從圖1 可以觀察到,本文所提的ISM 與ISM+方法與SIR 傳播過程中感染數(shù)量Φ的大小高度相關(guān),尤其是ISM+方法在大多數(shù)情況下都優(yōu)于其他算法,說明所提算法相比其他指標(biāo)能夠較為準(zhǔn)確地識別節(jié)點(diǎn)的傳播影響力.傳統(tǒng)的度量方法如接近中心性和介數(shù)中心性指標(biāo)與實(shí)際影響力之間相關(guān)性較弱,結(jié)果較為發(fā)散,尤其是介數(shù)中心性與SIR 影響節(jié)點(diǎn)數(shù)的相關(guān)性最弱,其原因與網(wǎng)絡(luò)的社區(qū)化有關(guān),因?yàn)樯鐓^(qū)化的情況下節(jié)點(diǎn)間聚集程度高,節(jié)點(diǎn)介數(shù)普遍很小,導(dǎo)致利用介數(shù)進(jìn)行傳播影響力排序時節(jié)點(diǎn)間區(qū)分度不大.造成這一結(jié)果的還可能是因?yàn)榕琶壳暗墓?jié)點(diǎn)集中在同一個社區(qū),導(dǎo)致了信息傳播的局部性.KSGC 方法是針對LGM 做的改進(jìn),但在相關(guān)性實(shí)驗(yàn)中,兩種算法的結(jié)果較為接近.

圖1 十種不同排序方法得到的排序結(jié)果與SIR 傳播過程感染節(jié)點(diǎn)數(shù)的相關(guān)性 (a) Enron;(b) Facebook;(c) Netscience;(d) Infectious;(e) USAir;(f) EPAFig.1.The correlation between the ranking results obtained by ten different ranking methods and the number of infected nodes in the SIR propagation process: (a) Enron;(b) Facebook;(c) Netscience;(d) Infectious;(e) USAir;(f) EPA.

在相關(guān)性實(shí)驗(yàn)中,實(shí)驗(yàn)設(shè)置的傳播率是固定的,實(shí)驗(yàn)結(jié)果只反映了特定傳播率下的靜態(tài)狀態(tài).為了更全面評價各個算法的節(jié)點(diǎn)重要性排序精度,我們將τ值作為準(zhǔn)確性度量值,設(shè)置傳播率區(qū)間為[|βth|-7%,|βth|+7%] (若βth≤0.07,傳播率區(qū)間設(shè)置為 [ 0.01,0.15]).結(jié)果如圖2 所示,縱軸表示節(jié)點(diǎn)實(shí)際傳播能力排序結(jié)果與不同中心性算法得到的節(jié)點(diǎn)重要性排序結(jié)果間的相關(guān)系數(shù)值,該值越大表示對應(yīng)排序算法越準(zhǔn)確.可以看出,當(dāng)傳播率超過傳播閾值βth(虛線表示不同網(wǎng)絡(luò)的βth值)時,ISM與ISM+方法表現(xiàn)一般都要優(yōu)于多數(shù)算法,尤其是ISM+方法表現(xiàn)更加突出,同 SIR 模型模擬傳播過程得到的節(jié)點(diǎn)傳播能力有顯著的相關(guān)性.然而,從圖2 可以清楚地看到,盡管介數(shù)中心性和接近中心性方法是基于網(wǎng)絡(luò)全局信息計(jì)算得到的,但在識別這些網(wǎng)絡(luò)中重要節(jié)點(diǎn)方面并不具有優(yōu)勢.同時,度中心性,MDD,LGM 和KSGC 這類基于度的方法在傳播率較小的情況下表現(xiàn)較好,是因?yàn)楫?dāng)傳播率較小時,信息從節(jié)點(diǎn)發(fā)起容易局限于局部,此時影響傳播結(jié)果的主要因素是鄰居節(jié)點(diǎn)數(shù)量,即節(jié)點(diǎn)度越大感染到的節(jié)點(diǎn)也越多,度中心性,MDD,LGM和KSGC 方法正好適合這一情況.

圖2 6 個真實(shí) 網(wǎng)絡(luò)數(shù) 據(jù)集上 十種不 同排序 方法排 序準(zhǔn)確 性對比 (a) Enron;(b) Facebook;(c) Netscience;(d) Infectious;(e) USAir;(f) EPAFig.2.Comparison of sorting accuracy of ten different sorting methods on six real network datasets: (a) Enron;(b) Facebook;(c) Netscience;(d) Infectious;(e) USAir;(f) EPA.

調(diào)整考察的節(jié)點(diǎn)范圍進(jìn)一步對Kendall 相關(guān)系數(shù)的結(jié)果進(jìn)行觀察,設(shè)置節(jié)點(diǎn)比例L的變化范圍為0.05—1.00,圖3 給出了不同算法得到的不同比例排名靠前的節(jié)點(diǎn)與節(jié)點(diǎn)實(shí)際傳播影響力排序之間的相關(guān)性結(jié)果.不難看出當(dāng)L較小時,除了在Enron 網(wǎng)絡(luò)中MDD,LGM 和KSGM 表現(xiàn)要好于ISM 與ISM+以外,其他5 個網(wǎng)絡(luò)中,本文提出的ISM+算法在不同比例節(jié)點(diǎn)時都可以獲得較好的節(jié)點(diǎn)重要性排序結(jié)果,并且能夠在更大范圍的L值下取得更好的評價結(jié)果.

圖3 不同比 例節(jié)點(diǎn) 下十種 評估算法的Kendall 相關(guān)系 數(shù)對比 (a) Enron;(b) Facebook;(c) Netscience;(d) Infectious;(e) USAir;(f) EPAFig.3.Comparison of Kendall correlation coefficients of ten node influence evaluation algorithms under different scale nodes:(a) Enron;(b) Facebook;(c) Netscience;(d) Infectious;(e) USAir;(f) EPA.

4.2 模擬數(shù)據(jù)集

除了6 個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)外,還在Lancichinetii-Fortunato-Radicchi (LFR)[35]模型生成的人工網(wǎng)絡(luò)數(shù)據(jù)集上比較了不同傳播率下SIR 和不同評估算法間的Kendall 相關(guān)系數(shù).通過設(shè)置不同的LFR參數(shù),生成拓?fù)涮卣鞑煌木W(wǎng)絡(luò)結(jié)構(gòu),設(shè)置LFR模型參數(shù)為: 節(jié)點(diǎn)數(shù)N=2000,社區(qū)的最小規(guī)模cmin=20,社區(qū)的最大規(guī)模cmax=50,網(wǎng)絡(luò)的最大度kmax=30,混合參數(shù)μ=0.1.調(diào)整網(wǎng)絡(luò)平均度〈k〉來調(diào)節(jié)網(wǎng)絡(luò)的連接緊密程度,分別生成〈k〉=5,10,15 的三個網(wǎng)絡(luò)數(shù)據(jù)集.設(shè)置傳播率區(qū)間為[0.01,0.15],實(shí)驗(yàn)結(jié)果如圖4 所示,當(dāng)傳播率超過傳播閾值時,ISM+實(shí)驗(yàn)結(jié)果明顯優(yōu)于其他9 種算法,尤其在集聚程度高的網(wǎng)絡(luò)中,如圖4(b),(c),相比其他9 種指標(biāo),ISM+指標(biāo)在更大范圍的傳播率下具有優(yōu)勢.當(dāng)傳播率較小時,度中心性,MDD,LGM 與KSGC 算法表現(xiàn)相對較好,這與真實(shí)數(shù)據(jù)集上的結(jié)果類似,其原因也是因?yàn)閭鞑ヂ势r,節(jié)點(diǎn)的真實(shí)影響力主要由節(jié)點(diǎn)度大小決定.

圖4 LFR 模擬數(shù)據(jù)集上十種評估算法的Kendall 相關(guān)系數(shù)對比,黑色虛線為三個網(wǎng)絡(luò)的傳播閾值βth (a) 〈 k〉 =5,βth=0.0984;(b) 〈 k〉 =10,βth=0.0723;(c) 〈 k〉 =15,βth=0.0577Fig.4.Comparison of Kendall correlation coefficients of ten evaluation algorithms on the LFR simulation dataset,the black dashed line is the propagation threshold βth of three different network: (a) 〈 k〉 =5,βth=0.0984;(b) 〈 k〉 =10,βth=0.0723;(c) 〈 k〉 =15,βth=0.0577.

4.3 ISM+算法的最優(yōu) θ 值

不同的實(shí)際網(wǎng)絡(luò)可能要求不同的θ值,從而保證ISM+方法可以獲得最佳性能,實(shí)驗(yàn)取間隔為0.02,區(qū)間范圍為0.02—1.00 的多個θ值,采用平均Kendall tau 指標(biāo)〈τ〉[37],系統(tǒng)分析參數(shù)θ對ISM+算法性能的影響:

其中β表示傳播率,βmin和βmax分別表示最小和最大傳播率,M表示考察的傳播率數(shù)量,τ(β)表示當(dāng)傳播率為β時,ISM+方法生成的節(jié)點(diǎn)重要性排序序列與SIR 過程生成節(jié)點(diǎn)傳播影響力排序序列之間的Kendall 相關(guān)性τ值.這里同樣設(shè)置傳播率區(qū)間為 [|βth|-7%,|βth|+7%] (即除了Netscience網(wǎng)絡(luò)傳播率區(qū)間設(shè)置為[0.06,0.20]以外,其他網(wǎng)絡(luò)的傳播率區(qū)間均設(shè)置為[0.01,0.15]).〈τ〉值介于—1—1 之間,值越大意味著對應(yīng)θ值的ISM+方法可以更準(zhǔn)確地識別網(wǎng)絡(luò)中具有傳播影響力的重要節(jié)點(diǎn).實(shí)驗(yàn)結(jié)果如圖5 紅色曲線所示,對于每個網(wǎng)絡(luò),都有一個最佳的θ值,該值對應(yīng)的ISM+方法可獲得最大的〈τ〉值.Enron,Facebook,Netscience,USAir,Infectious,EPA 以及平均〈k〉分別為5,10,15 的LFR 網(wǎng)絡(luò),對應(yīng)的最佳θ值分別為0.60,0.60,0.56,0.38,0.60,0.64,0.46,0.68 及0.72,多數(shù)網(wǎng)絡(luò)中最優(yōu)θ值都超過0.5.由于ISM+算法的設(shè)計(jì)原理決定了其在信息傳播率超過傳播閾值時更具有優(yōu)勢,因此我們進(jìn)一步分析傳播率超過βth時,θ的取值對ISM+算法性能的影響,實(shí)驗(yàn)結(jié)果如圖5 中黑色 曲線所 示,Enron,Facebook,Netscience,USAir,Infectious,EPA 這6 個真實(shí)網(wǎng)絡(luò)傳播率區(qū)間分別取[0.08,0.15],[0.05,0.15],[0.13,0.20],[0.03,0.15],[0.05,0.15]及[0.05,0.15],對應(yīng)的最佳θ值分別為0.70,0.68,0.76,0.38,0.76及0.64,平均〈k〉為5,10,15 的LFR 網(wǎng)絡(luò)的傳播區(qū)間分別取[0.10,0.15],[0.08,0.15],[0.06,0.15],對應(yīng)的最佳θ值分別為0.72,0.96,0.88,可見當(dāng)傳播率超過βth時,強(qiáng)化具有較大ISM 值的有影響力鄰居的影響對于提高ISM+性能具有積極作用.

圖5 當(dāng)β 變化時,不同θ 值所對應(yīng)的ISM+方法生成的節(jié)點(diǎn)重要性排序序列與SIR 傳播擴(kuò)散過程生成的節(jié)點(diǎn)傳播影響力排序序列之間 的平均Kendall 〈 τ〉 值 (a) Enron;(b) Facebook;(c) Netscience;(d) Infectious;(e) USAir;(f) EPA;(g) LFR_k5;(h) LFR_k10;(i) LFR_k15Fig.5.The average Kendall’s 〈 τ〉 obtained by comparing the ranking list generated by SIR spreading process and the ranking list generated by the ISM+ methods with different θ when the β changes: (a) Enron;(b) Facebook;(c) Netscience;(d) Infectious;(e) USAir;(f) EPA;(g) LFR_k5;(h) LFR_k10;(i) LFR_k15.

5 結(jié)論

如何準(zhǔn)確識別網(wǎng)絡(luò)中具有傳播影響力的重要節(jié)點(diǎn),是近年來網(wǎng)絡(luò)科學(xué)研究的熱點(diǎn)問題.本文基于引力模型設(shè)計(jì)了ISM 方法及其擴(kuò)展算法ISM+,可以有效地對復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性進(jìn)行評價和排序.所提算法兼顧局部拓?fù)湫畔⒑腿治恢眯畔?基于牛頓力學(xué)中的引力公式,融合了節(jié)點(diǎn)的多種屬性信息包括節(jié)點(diǎn)H指數(shù)、k核中心性以及節(jié)點(diǎn)的結(jié)構(gòu)洞特征,彌補(bǔ)了現(xiàn)存方法評估角度片面的不足,可以更有效地對節(jié)點(diǎn)重要性進(jìn)行評價.在6 個真實(shí)網(wǎng)絡(luò)和3 個LFR 模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,與其他評估方法(如度中心性,介數(shù)中心性,接近中心性,MDD,LGM,KSGC 與引力模型等)相比,所提方法在識別網(wǎng)絡(luò)節(jié)點(diǎn)重要性方面具有一定優(yōu)勢,當(dāng)傳播率大于傳播閾值時,多數(shù)網(wǎng)絡(luò)中算法在不同比例節(jié)點(diǎn)下都能更準(zhǔn)確地評估節(jié)點(diǎn)的重要性.本文所提算法參照引力模型,僅將最短路徑表示為節(jié)點(diǎn)間的路徑信息,實(shí)際上節(jié)點(diǎn)間除最短路徑以外的其他可達(dá)路徑對于衡量節(jié)點(diǎn)間的相互作用效應(yīng)也有效,未來的工作中我們將從這一角度出發(fā)進(jìn)一步提升算法精度.