基于引力方法的復雜網絡節點重要度評估方法*

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

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

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

1 引言

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

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

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

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

2 相關概念

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

2.1 度中心性、接近中心性和介數中心性

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

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

接近中心性[7]認為一個節點與網絡中其他節點的平均距離越小,節點重要性越高,表示為

其中,dij代表節點i和j之間的距離,N表示網絡節點數.

介數中心性[8]描述了節點對網絡中沿最短路徑傳播的信息流的控制力,定義為

其中,gst表示網絡中除了節點i以外任意節點對(如節點s和節點t)之間的最短路徑數,表示當中經過節點i的最短路徑數.

2.2 H 指數

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

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

2.3 結構洞理論

結構洞[27]指網絡結構中不存在冗余聯系的兩個人之間的缺口,網絡中占據結構洞位置的個體相比其鄰居節點可以獲得更多的競爭優勢,包括信息優勢和控制優勢,從而影響甚至控制社會關系與信息的傳播.為了量化結構洞節點對這些關系的控制,Burt[27]提出網絡約束系數這一定量化指標來衡量節點形成結構洞所受到的約束,表示為

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

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

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

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

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

Λi表示節點i的直接鄰居.

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

其中,ki和kj分別表示節點i和j的度,R表示網絡截斷半徑,是網絡最短路徑平均值的一半.

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

3 算法設計與評價標準

3.1 基于引力方法的節點重要性排序方法

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

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

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

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

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

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

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

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

3.2 評價標準

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

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

4 實驗數據集與結果分析

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

4.1 真實網絡

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

表1 6 個真實網絡的拓撲統計參數Table 1. Topological parameters of six real networks.

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

圖1 十種不同排序方法得到的排序結果與SIR 傳播過程感染節點數的相關性 (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.

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

圖2 6 個真實 網絡數 據集上 十種不 同排序 方法排 序準確 性對比 (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.

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

圖3 不同比 例節點 下十種 評估算法的Kendall 相關系 數對比 (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 模擬數據集

除了6 個真實網絡數據外,還在Lancichinetii-Fortunato-Radicchi (LFR)[35]模型生成的人工網絡數據集上比較了不同傳播率下SIR 和不同評估算法間的Kendall 相關系數.通過設置不同的LFR參數,生成拓撲特征不同的網絡結構,設置LFR模型參數為: 節點數N=2000,社區的最小規模cmin=20,社區的最大規模cmax=50,網絡的最大度kmax=30,混合參數μ=0.1.調整網絡平均度〈k〉來調節網絡的連接緊密程度,分別生成〈k〉=5,10,15 的三個網絡數據集.設置傳播率區間為[0.01,0.15],實驗結果如圖4 所示,當傳播率超過傳播閾值時,ISM+實驗結果明顯優于其他9 種算法,尤其在集聚程度高的網絡中,如圖4(b),(c),相比其他9 種指標,ISM+指標在更大范圍的傳播率下具有優勢.當傳播率較小時,度中心性,MDD,LGM 與KSGC 算法表現相對較好,這與真實數據集上的結果類似,其原因也是因為傳播率偏小時,節點的真實影響力主要由節點度大小決定.

圖4 LFR 模擬數據集上十種評估算法的Kendall 相關系數對比,黑色虛線為三個網絡的傳播閾值β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+算法的最優 θ 值

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

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

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

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