基于多屬性決策的復雜網絡關鍵影響力節點的識別研究

張格豪,劉 偉,王睿鑫垚,厲鑫鵬,龔子忱,陳一源,陳海洋

(無錫學院 物聯網工程學院,江蘇 無錫 214105)

0 引言

復雜網絡的研究已成為現代科學的熱點之一,因為復雜網絡具有高度的動態性、多樣性、非線性和不確定性,對復雜網絡中具有關鍵影響力的節點的研究也成為當下復雜網絡研究的熱點之一[1-4],可以通過找到網絡中最具有關鍵影響力的節點,并預測網絡的演化趨勢和危機事件。關鍵節點是指對網絡結構和功能具有重要影響的節點,研究復雜網絡的關鍵影響力節點對于解決諸如網絡攻擊和崩潰、疾病傳播、社交網絡的社區發現、推薦系統、金融風險管理、軌道交通等現實問題具有重要意義[5-9],在城市公交網絡中通過識別關鍵公交網絡節點可保證城市公交網絡的安全運營。此外,還可以通過識別網絡中的關鍵影響力節點來設計和優化網絡的性能和功能,促進網絡的發展和創新。因此,對復雜網絡中關鍵影響力節點的研究已經成為許多領域的關鍵問題之一,如計算機科學、生物學、社會學等[10]。

在先前的研究中,為了識別復雜網絡中的關鍵影響力節點,提出了許多定量分析方法,主要包括系統科學分析方法[11]和社交網絡分析方法。在系統科學分析方法中,節點的重要性等同于節點從網絡中刪除的破壞性。如節點收縮法[12],節點收縮法即是將節點及其鄰居節點進行收縮成一個新的節點,觀察網絡是否能夠非常好地凝聚在一起,是識別重要節點的一個標準,雖然節點收縮方法可以導致網絡拓撲結構的變化,但它們可能會忽略節點之間的關系信息。社交網絡分析方法認為節點的重要性可以通過節點中心性來度量,包括度中心性(Degree Centrality, DC)[13]、緊密度中心性(Closeness Centrality, CC)[14]、介數中心性(Betweenness Centrality, BC)[15]、K-殼分解法(K-shell decomposition)[2]、特征向量中心性(Eigenvector Centrality, EC)[13]、結構洞(Structural Holes, SH)[16]、橋中心性(Bridgeness Centrality, Bri)[17]等。這些中心性度量從不同的方面來描述節點的影響力。DC通過鄰居節點的數量來描述節點的影響力,但它沒有考慮全局網絡結構。BC根據通過節點的最短路徑的數量來識別有影響力的節點,但在真實網絡中信息流可能不會沿著最短路徑流動。CC通過評估訪問其他節點的難易程度來評估節點的影響力,但它不適用于非中心化網絡。K-shell通過確定節點在網絡中的位置來識別節點的影響力,但其忽略了節點在網絡中的全局影響力。EC根據觀察節點鄰居節點的數量及鄰居節點的影響力來確定節點的重要性,但在真實網絡上可能會出現分數局部化現象。SH通過節點與其鄰居節點的約束系數來描述節點的影響力,約束系數越小,就越容易獲取資源,但它只描述了節點局部性質。Bri從全局考慮節點在網絡中的連通性影響力,但它忽略了節點之間的影響力。

目前,已經有許多中心性度量算法來識別網絡中的具有關鍵影響力的節點,其中大多數僅采用單一指標來評估節點的影響力,所有這些單一性方法都有其自身的缺點和局限性。因此,諸多研究者提出了基于多屬性融合的方法,如陳妤等[18]基于排序學習的方法,選擇了度中心性、特征向量中心性、K-shell3個屬性作為節點重要性的特征指標。于會等[19]基于TOPSIS選取了4種指標作為決策評價方案,通過計算各節點方案到最佳理想方案的距離來確定節點的重要性。胡鋼等[20]提出了基于信息熵理論計算各屬性的權重值,并通過計算基于相關系數矩陣的各節點方案與正負理想方案的距離來確定節點的重要性。Yang等[21]提出了基于灰度關聯分析和SIR模型,動態地計算各屬性的權重值。寧陽等[22]基于節點度和改進的K-shell迭代次數指標,計算每個屬性的貢獻權重值。基于多屬性融合的方法可以結合各種中心性算法的優點,并對網絡中的節點進行綜合評估,可以更加準確地識別網絡中的具有關鍵影響力節點。

本文提出了一種新的方法,稱之為多屬性決策得分算法(Multi-attribute Decision-making Score,簡稱MADS),用于識別復雜網絡中具有關鍵影響力的節點。本方法綜合考慮了融合了不同的中心性度量方法作為網絡的多屬性,本文從節點的全局影響力和局部影響力兩個角度,結合了介數中心性(BC)、緊密度中心性(CC)和橋中心性(Bri)3個不同方面的指標作為識別網絡中具有重要影響力節點的3個屬性指標。為了提高本方法的適用性,本文提出了一種基于灰度關聯分析和信息熵加權理論的新的權重計算方法來綜合性地確定每個屬性的權重。本文采用了網絡的脆弱性評價指標在Dolphins、Football、Email、Netscience、Usair、Yeast6個復雜網絡數據集上進行實驗數據對比分析,實驗分析結果證明了本文提出的MADS算法能夠更全面地評估網絡中的節點,能夠有效地識別出具有關鍵影響力的節點。

1 相關概念

1.1 中心性度量

假設一個簡單的有n個節點的網絡G=(V,E) ,其中V表示網絡中所有節點的集合,E表示網絡中所有邊的集合。

定義1.1 介數中心性(Betweenness Centrality)

節點v的BC值就定義為通過節點v的所有節點對之間的最短路徑分數,計算公式如下:

(1)

定義1.2 緊密度中心性(Closeness Centrality)

節點v的 CC 值就定義為到節點v的所有其他節點的最短路徑距離之和的倒數,計算公式如下:

(2)

其中,dav是節點a和v之間最短路徑的距離。

定義1.3 橋中心性(Bridgeness Centrality)

節點v的Bridgeness值就定義公式如下:

(3)

其中,NG(v)表示節點v的鄰居節點,ρab表示節點a和b之間最短路徑的數目,ρab(v) 表示從節點a和b之間通過節點v的最短路徑總條數。

1.2 SIR傳播模型

SIR模型[13]是一個廣泛應用于流行病網絡中的傳播、社交網絡的謠言傳播、城市交通網絡堵車問題等諸多真實網絡中,用于評價網絡節點挖掘算法的指標之一。該模型首先假設網絡具有3種狀態:S(susceptible易感態,表示當前節點容易被感染后的鄰居節點所感染),I(infected感染態,表示當前節點目前處于被感染狀態,一定時間后會轉變為免疫態),R(recovered免疫態,表示當前節點已對病毒免疫,且不會進行傳播)。

本文通過SIR傳播模型來計算各節點的傳播能力,具體而言,把每個節點都作為傳播源(易感態I),每一步都以概率為α感染其鄰居節點(感染態S),并可能有概率β在下一步恢復(免疫態R)。在t時刻,計算時刻t初始感染節點的總感染節點數SIR(t)=S(t)+I(t),以SIR(t)來表示時刻t初始感染節點的傳播能力,最后SIR(t)會達到一個定值,不再增加,本文用SIR來表示最終的定值。SIR的值越大,即表明該節點的傳播能力越強。本文的α設置為0.1,β設置為 0.5 ,本文對每個節點的傳播能力計算都重復100次獨立實驗,對于每個節點的傳播能力計算,本文進行了100次獨立實驗,并取100次實驗結果的平均值作為該節點的SIR值。

1.3 灰度關聯分析

灰度關聯分析主要包括4個部分:確立灰度關系、選取參考序列、計算灰度關聯系數、計算灰度關聯數。本文以表現每個節點的傳播能力的SIR值作為參考序列,即(YSIR)T={y1SIR,y2SIR,…,yNSIR},以每個節點的BC、CC、Bri3個屬性的值分別作為比較序列,即(Yj)T={y1j,y2j,…,ynm},(j=1,2,..,m),n為節點的數目,m為總屬性的數目。

灰度關聯數R的計算方式如下:

(4)

其中:

(5)

α為區分系數,且α∈[0,1],本文α取0.5。

2 MADS算法

2.1 構造規范化決策矩陣

假設某網絡有n個節點,決策得分屬性為BC、CC、Bri3個屬性指標。

構建原始決策屬性矩陣A(n×3):

(6)

對矩陣A進行無量綱化處理,進而得到規范化決策矩陣B(n×3):

(7)

2.2 用灰度關聯和信息熵理論計算屬性權重

第一步,計算每個節點的SIR值SIRi,在原始矩陣A(n×3)上加入一列新列(SIR)T={SIR1,SIR2,…,SIRn},構成矩陣S(n×4):

(8)

第二步,根據式(4)計算出每個節點的每個屬性值與SIR值的灰度關聯系數:

r(yiSIR,yij),i=1,2,…,n;j=1,2,3

(9)

根據式(5)得到每個屬性與SIR值的灰度關聯值:

R(YSIR,Yj),j=1,2,3,

(10)

最后得到灰度關聯向量R:

R=(R(YSIR,Y1),R(YSIR,Y2),R(YSIR,Y3))。

(11)

第三步,計算3個屬性基于灰度分析的權重系數uj:

(12)

灰度關聯加權的屬性權重向量U為:

U=(u1,u2,u3)

(13)

第四步,基于信息熵理論計算各屬性的權重vj,計算公式為:

(14)

信息熵加權的屬性權重向量V為:

V=(v1,v2,v3)

(15)

第五步,計算最終的各屬性權重wj,計算公式如下:

wj=(Uj+Vj)/2,j=1,2,3

(16)

得到最終權重向量W為:

W=(w1,w2,w3)

(17)

2.3 綜合評估節點的影響力

計算每個節點的MADS值:

MADSi=(bci1w1+cci2w2+brii3w3),i=1,2,...,n

(18)

其中,MADSi為每個節點的影響力評估指標,MADS的值越大,表明節點越重要,在網絡中的影響力越大。

2.4 算法過程

MADS算法流程由圖1所示。

圖1 MADS算法流程

3 實驗數據分析

3.1 網絡的魯棒性和脆弱性評價指標

網絡的魯棒性和脆弱性指標用于評價在移除某個節點后,網絡結構和功能的完整性突變越大表明移除的節點越重要。通常會采用某種重要影響力節點識別排序算法對節點進行排名,從排名高的節點開始逐一刪除,用ρ表示已刪除節點的數目占總節點數的比例,用σ表示最大連通片的節點數目的比例[23],網絡的魯棒性(robustness)可用R表示[24]。

(19)

其中,ρ和σ分別代表已刪除節點數目和最大連通片節點數目在節點總數中所占比例。

基于網絡的魯棒性可定義所實施的刪除方法的脆弱性V:

V=1/2-R,R∈(0,1/2)

公安機關、銀行等有關部門應及時開展信息預警，適時以真實案例為宣傳切入點，揭露“套路貸”犯罪的行為特征，倡導民眾通過正規渠道借款，遠離不正規的非法放貸組織、個人，自覺抵制非法放貸行為，嚴防上當受騙。

(20)

在本研究中,采用網絡的脆弱性V指標來評估方法的有效性,并計算其V值,V指標越大,表明根據該方法識別的關鍵節點準確率更高,可以從網絡整體上反應具有關鍵影響力節點挖掘算法的有效性。

3.2 復雜網絡數據集

為驗證本文所提出的MADS算法的適用性和有效性,本文使用了Dolphins、Football、Email、Netscience、Usair、Yeast6個真實復雜網絡數據集。這6個復雜網絡數據集的基本拓撲特征如表1所示。

表1 6個復雜網絡數據集的基本拓撲特征:網絡節點數N和邊數M,平均聚類系數C,網絡節點的平均度k

(1)Dolphins網絡是一個描述海豚之間社交關系的網絡數據集。

(2)Football網絡是一個描述美國橄欖球比賽的社交網絡數據集。

(3)Email網絡是從Rovira I Virgili大學的電子郵件記錄中提取出來的,記錄了一些用戶之間的電子郵件通信,以及他們之間的社交關系。

(4)Netscience網絡指一個記錄了學術界或其他領域合作者之間合作關系的網絡數據集,揭示研究者之間的合作關系。

(6)Yeast網絡數據集是一個描述酵母細胞蛋白質之間相互作用關系的網絡數據集。

為了驗證本文提出的MADS(ours)方法的有效性,本文將MADS(ours)與橋中心性(Bridgeness)、介數中心性(Betweenness)、緊密度中心性(Closeness)、特征向量中心性(Eigenvector)及結構洞(Sh)這5種不同方面的中心性度量方法進行脆弱性評價對比分析,即V-指標越大,則表明該方法識別的關鍵節點越準確。

3.3 實驗數據對比分析

實驗數據對比分析如圖2—7所示。

圖2 MADS(ours)方法與橋中心性(Bridgeness)、介數中心性(Betweenness)、緊密度中心性(Closeness)、特征向量中心性(Eigenvector)及結構洞(Sh)在Dolphins網絡上的網絡脆弱性對比分析

圖3 MADS(ours)方法與橋中心性(Bridgeness)、介數中心性(Betweenness)、緊密度中心性(Closeness)、特征向量中心性(Eigenvector)及結構洞(Sh)在Football網絡上的網絡脆弱性對比分析

圖4 MADS(ours)方法與橋中心性(Bridgeness)、介數中心性(Betweenness)、緊密度中心性(Closeness)、特征向量中心性(Eigenvector)及結構洞(Sh)在Usair網絡上的網絡脆弱性對比分析

圖5 MADS(ours)方法與橋中心性(Bridgeness)、介數中心性(Betweenness)、緊密度中心性(Closeness)、特征向量中心性(Eigenvector)及結構洞(Sh)在Email網絡上的網絡脆弱性對比分析

圖6 MADS(ours)方法與橋中心性(Bridgeness)、介數中心性(Betweenness)、緊密度中心性(Closeness)、特征向量中心性(Eigenvector)及結構洞(Sh)在Netscience網絡上的網絡脆弱性對比分析

從評價排名角度進行分析:由表2可以觀察到,MADS(ours)在Usair、Netscience網絡的脆弱性評價標準中排列第一名,在Dolphins、Football、Email、Yeast網絡中,均排列第二名,綜合排名位列第一名,由表3,通過與Bridgeness、Betweenness等其他方法在每個網絡上的V指標的對比量化分析,可以觀察到MADS(ours)的V指標綜合增長了2.6%。從而可以證明:本文提出的MADS方法在識別網絡具有重要影響力節點上具有非常顯著的有效性和適用性。

表2 每個方法在每個網絡中脆弱性評價排名和綜合排名Rank

表3 MADS(ours)方法與其他方法在每個網絡上的V指標對比分析

同時,由表3可以觀察到,MADS(ours)比Bridgeness提高了2.3%,比Closeness提高了4.0%,雖然比Betweenness降低了0.2%,但由于Betweenness的綜合排名位列第一,可以說明MADS(ours)非常有效地保留了Betweenness的優勢。由此可以證明,本文提出的MADS方法能夠非常有效地融合了各屬性的優勢,展現了本方法具有非常顯著的適用性和穩健性。

從網絡的角度進行分析:由表2可以觀察到,MADS(ours)方法在Dolphins、Football、Usair3個小型網絡和Email、Netscience、Yeast3個較大型網絡中與其他方法相比,V指標都有顯著提高,在Dolphins小網絡中提高了5.6%,在Yeast網絡中提高了3.6%,由此可以證明,MADS(ours)方法的創新性及優越性,能夠很好地識別出網絡中具有關鍵影響力的節點。

綜上所述,本文提出的MADS方法在識別復雜網絡具有關鍵影響力節點方面,具有非常高的有效性和適用性,能夠更加準確地識別出網絡中具有關鍵影響力的節點,克服了傳統單一性中心性度量方法的局限性。

4 結語

本文提出了一種新的復雜網絡中識別具有關鍵影響力節點的方法,采用了多屬性決策將不同方面的中心性度量方法進行融合。該方法綜合考慮了節點與節點之間的局部影響力以及節點在網絡中的全局影響力,同時從節點傳播能力及信息熵方面綜合權衡了不同屬性的權重值。具體而言,本文將節點的介數中心性、緊密度中心性以及橋中心性進行融合,并根據所得到的結果進行網絡的脆弱性對比分析。實驗結果表明,本文提出的MDAS方法更加有效、更具有適用性,不僅在小型網絡,而且在較大型網絡中性能都有所提升。下一步,筆者將進一步研究如何識別網絡中具有強連接性的邊融合到本方法中,以提出新的研究思路并進一步完善該方法。