基于引力方法的復雜網(wǎng)絡(luò)節(jié)點重要度評估方法*

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

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

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

1 引言

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

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

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

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

2 相關(guān)概念

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

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

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

度指標反映了節(jié)點的直接影響力,節(jié)點上的鏈接數(shù)越多,節(jié)點度ki越大,因為只考慮了節(jié)點局部信息,因而是一種局部中心性指標.

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

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

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

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

2.2 H 指數(shù)

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

其中,kjs表示節(jié)點i的第s個鄰居的度數(shù).在(4)式中,算子H返回最大整數(shù)h,使得節(jié)點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é)點可以獲得更多的競爭優(yōu)勢,包括信息優(yōu)勢和控制優(yōu)勢,從而影響甚至控制社會關(guān)系與信息的傳播.為了量化結(jié)構(gòu)洞節(jié)點對這些關(guān)系的控制,Burt[27]提出網(wǎng)絡(luò)約束系數(shù)這一定量化指標來衡量節(jié)點形成結(jié)構(gòu)洞所受到的約束,表示為

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

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

2.4 引力模型、局部引力模型以及KSGC指標模型

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

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

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

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

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

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

3 算法設(shè)計與評價標準

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

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

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

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

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

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

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

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

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

3.2 評價標準

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

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

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

實驗選取了6 個來自不同領(lǐng)域的真實數(shù)據(jù)集,分別是安然郵件網(wǎng)絡(luò)Enron[32],Slavo Zitnik 的朋友圈關(guān)系網(wǎng)絡(luò)Facebook[33],科學家合作網(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)計特征,包括網(wǎng)絡(luò)節(jié)點總數(shù)N,網(wǎng)絡(luò)連邊數(shù)E,節(jié)點間平均最短距離〈d〉,節(jié)點平均度〈k〉,網(wǎng)絡(luò)集聚系數(shù)C,網(wǎng)絡(luò)直徑D,網(wǎng)絡(luò)最大ks值ksmax,信息傳播閥值βth=〈k〉/〈k2〉以及信息傳播率β,其中〈k2〉表示節(jié)點二階平均度.

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

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

表1 6 個真實網(wǎng)絡(luò)的拓撲統(tǒng)計參數(shù)Table 1. Topological parameters of six real networks.

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

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

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

圖3 不同比 例節(jié)點 下十種 評估算法的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 個真實網(wǎng)絡(luò)數(shù)據(jù)外,還在Lancichinetii-Fortunato-Radicchi (LFR)[35]模型生成的人工網(wǎng)絡(luò)數(shù)據(jù)集上比較了不同傳播率下SIR 和不同評估算法間的Kendall 相關(guān)系數(shù).通過設(shè)置不同的LFR參數(shù),生成拓撲特征不同的網(wǎng)絡(luò)結(jié)構(gòu),設(shè)置LFR模型參數(shù)為: 節(jié)點數(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],實驗結(jié)果如圖4 所示,當傳播率超過傳播閾值時,ISM+實驗結(jié)果明顯優(yōu)于其他9 種算法,尤其在集聚程度高的網(wǎng)絡(luò)中,如圖4(b),(c),相比其他9 種指標,ISM+指標在更大范圍的傳播率下具有優(yōu)勢.當傳播率較小時,度中心性,MDD,LGM 與KSGC 算法表現(xiàn)相對較好,這與真實數(shù)據(jù)集上的結(jié)果類似,其原因也是因為傳播率偏小時,節(jié)點的真實影響力主要由節(jié)點度大小決定.

圖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) θ 值

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

其中β表示傳播率,βmin和βmax分別表示最小和最大傳播率,M表示考察的傳播率數(shù)量,τ(β)表示當傳播率為β時,ISM+方法生成的節(jié)點重要性排序序列與SIR 過程生成節(jié)點傳播影響力排序序列之間的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 之間,值越大意味著對應θ值的ISM+方法可以更準確地識別網(wǎng)絡(luò)中具有傳播影響力的重要節(jié)點.實驗結(jié)果如圖5 紅色曲線所示,對于每個網(wǎng)絡(luò),都有一個最佳的θ值,該值對應的ISM+方法可獲得最大的〈τ〉值.Enron,Facebook,Netscience,USAir,Infectious,EPA 以及平均〈k〉分別為5,10,15 的LFR 網(wǎng)絡(luò),對應的最佳θ值分別為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è)計原理決定了其在信息傳播率超過傳播閾值時更具有優(yōu)勢,因此我們進一步分析傳播率超過βth時,θ的取值對ISM+算法性能的影響,實驗結(jié)果如圖5 中黑色 曲線所 示,Enron,Facebook,Netscience,USAir,Infectious,EPA 這6 個真實網(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],對應的最佳θ值分別為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],對應的最佳θ值分別為0.72,0.96,0.88,可見當傳播率超過βth時,強化具有較大ISM 值的有影響力鄰居的影響對于提高ISM+性能具有積極作用.

圖5 當β 變化時,不同θ 值所對應的ISM+方法生成的節(jié)點重要性排序序列與SIR 傳播擴散過程生成的節(jié)點傳播影響力排序序列之間 的平均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é)論

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