基于三元閉包模體的關鍵節點識別方法

徐 越,劉雪明

(華中科技大學人工智能與自動化學院,武漢 430074)

0 引言

復雜網絡能夠描述許多真實系統,如社交網絡、貿易網絡和交通運輸網絡等,網絡中的關鍵節點與其結構穩定性和系統功能緊密相關[1]。對于關鍵節點的識別,能夠為提高系統的魯棒性和效率提供針對性建議[2]。例如,在社交網絡中,識別出關鍵用戶,能夠控制社交信息的交互和傳遞,從而有效控制網絡輿情。在貿易網絡中,關鍵節點的識別能夠確定貿易樞紐,對于維持貿易網絡的穩定性以及提高貿易效率具有重要意義。在交通運輸網絡中,關鍵節點能夠影響網絡的整體連通性。在經受自然災害等破壞時,對于關鍵節點的維護,能夠有效保障交通運輸網絡的順暢運行。

現階段有多種關鍵節點的識別方法。節點的中心性指標,例如度中心性[3]、介數中心性[4]等,是識別關鍵節點的經典方法。K-shell[5]方法采用逐層分離節點的方式,獲取網絡中的關鍵節點。WL[6]方法考慮了節點自身的度和鄰居節點的度,認為鄰居節點的度越大,節點越重要。映射熵ME[7]方法進一步考慮了鄰居節點的影響,通過節點與所有鄰居節點的連接情況來評估其重要度。

模體作為一種局部統計顯著的特征子圖,存在于許多真實網絡中,能夠有效反映網絡的整體功能[8-9]。在大腸桿菌轉錄調控網絡中,每種類型的模體都與特定的基因表達功能緊密相關[10]。在動物社交網絡中,模體能夠反映動物群體的支配層次結構模式,從而揭示社會秩序的形成過程[11]。在有向生物網絡中,能夠根據節點在不同類型的模體中出現的次數,來衡量該節點的重要度[12]。

進一步的研究表明,三元閉包模體與網絡的異質性以及社團的形成緊密相關[13-15]。許多真實網絡中的三元閉包模體數目具有顯著性[16]。現有研究還未能考慮三元閉包模體的存在與節點重要度間的關系。本文引入了三元閉包模體權重的概念,以此來衡量該模體在網絡中的重要度,并提出了一種結合節點度中心性及其所在三元閉包模體權重的關鍵節點識別方法。以網絡最大連通子圖的比例以及全局效率作為評價指標,在6個真實網絡中進行了魯棒性實驗。同時,利用傳播模型SIR對多種節點排序結果進行評價。實驗結果表明,本文提出的方法相比于度中心性DC、K-shell分解、WL中心性、映射熵ME方法,能夠更加準確地識別出關鍵節點。

1 基于三元閉包模體的算法

定義無向無權網絡G=(V,E),其中V為網絡的節點集,E為網絡的邊集。圖1a展示了網絡中三元閉包模體的示意圖,該結構具有3個節點,節點之間具有強聯系,彼此之間有邊直接相連。三元閉包模體中的任意兩節點間,都有兩條較短的獨立路徑,兼具魯棒性和高效性。如圖1b所示,在相同節點數和邊數情況下,相比于四元閉包模體,三元閉包模體結構異質性更強,對該結構中關鍵節點的破壞,能夠對網絡的連通性和效率產生較大影響。

圖1 三元閉包模體示例

各個三元閉包模體對網絡拓撲連通性的影響不同。節點的重要度不僅與本身的度中心性有關,同時還與其所在的三元閉包模體有關。如圖1c所示,節點3和節點5具有相同的度中心性,所屬三元閉包模體的數目都為1,但對應三元閉包模體的拓撲位置不同。按度選擇節點來對網絡進行攻擊時,4個節點沒有區分度。若刪除節點3及其連邊,網絡中剩余最大連通子圖的大小為6。若刪除節點5及其連邊,網絡中剩余最大連通子圖的大小為5。類似節點度的定義,本文提出了三元閉包模體權重T(j)的概念,即取模體中所有節點度的均值,具體表示為

(1)

其中,n為屬于該三元閉包模體T的節點,kn為節點n的度中心性。

結合節點的度和其所在的三元閉包模體權重T(j),本文提出了一種基于三元閉包模體的節點重要度評估方法NT,可以表示為

(2)

其中,ki為節點i的度中心性,T(j)為節點i所在的三元閉包模體的權重,且節點i是該模體中度最大的節點。以圖1c為例,節點3的重要度為NT(3)=3+1/3×(2+2+3)=5.33,節點5的重要度為NT(5)=3+1/3×(2+3+3)=5.67,因此節點5比節點3更重要,這與移除節點5對網絡造成的破壞性更大的事實一致。

2 對比算法及評價指標

2.1 對比算法

1)度中心性。度中心性通過統計節點的連接數來衡量節點的重要度。在無權無向網絡中,可以表示為

(3)

其中,N為網絡的節點數,eij為節點i和節點j之間的連接關系,若有連接則eij為1,否則為0。

2)K-shell分解法。K-shell采用逐層分離節點的方式,對節點進行粗粒化分類。該算法首先迭代刪除最外層度為1的節點和它的連邊,包括新產生的度為1的節點,直到剩余節點的度都大于1。這些被刪去的節點和它們的連邊是網絡的1-shell,即k=1。利用同樣的方式,依次刪除度為2,3,…的節點,對網絡中的節點進行分類,所在K殼越大的節點越重要。

3)WL中心性。WL中心性方法認為節點所連邊越重要,則該節點越重要。首先定義了邊的權重,表示為

wij=ki×kj

(4)

其中,wij為節點i和節點j之間連邊的權重,ki為節點i的度。節點i的重要度取決于其所有連邊的權重,可以定義為

(5)

其中,Γi為節點i的鄰居節點集。

4)映射熵ME。映射熵方法考慮了該節點所有鄰居節點的度,采用類似信息熵的方式來衡量節點的重要度,具體表示為

(6)

其中,DCi為節點i的度中心性,Γi為節點i的鄰居節點集,DCj為鄰居節點j的度中心性。映射熵值越大的節點越不重要。

2.2 評價標準

目前評價關鍵節點識別方法的標準主要有兩類:一種是根據節點排序結果,依次攻擊網絡中的節點,評估節點對網絡結構和功能魯棒性的影響[17]。節點移除后對網絡造成的破壞程度越大,則該節點越重要。具體來說,可以通過衡量剩余網絡中最大連通子圖的比例[18],或者網絡的全局效率變化[19]來衡量節點對網絡魯棒性的影響。另一種是基于傳播模型SIR,選取不同排序結果的關鍵節點,通過信息傳播的方式,來衡量節點集合對網絡的影響程度[20],并以此驗證關鍵節點識別方法的有效性[21]。

2.2.1 魯棒性分析

1)最大連通子圖比例。網絡中的最大連通子圖與網絡功能緊密相關[22],連通子圖中任意兩節點間至少有一條路徑。對網絡中的關鍵節點進行蓄意攻擊后,會使得網絡碎片化,其最大連通子圖的大小也會發生變化[23]。最大連通子圖比例定義為

(7)

其中,S為刪除一定比例節點后,剩余網絡中最大連通子圖的大小,N為原始網絡的節點個數。依次移除節點,最大連通子圖比例下降越快,說明關鍵節點識別方法越有效。通常用最大連通子圖比例變化曲線下的面積,來量化關鍵節點識別方法的有效性。曲線下的面積越小,對應的關鍵節點識別方法越有效。

2)網絡全局效率。網絡的全局效率能夠衡量節點間信息交換的情況[24],與節點間的最短路徑長度有關。移除網絡中的關鍵節點,會造成節點間最短路徑長度增加,使網絡的全局效率下降[25]。網絡全局效率定義為

(8)

其中,N為網絡的節點數,dij為節點i和節點j之間最短路徑的長度,V為網絡的節點集。依次移除節點,網絡全局效率變化越快,說明關鍵節點識別方法越有效。

2.2.2 傳播效果分析

SIR是經典的傳染病模型,將節點分為易感染節點S、已感染節點I、免疫節點R[26]。已感染節點I會以β的概率感染易感染節點S,同時以γ的概率恢復為免疫節點R。免疫節點R不會再次被感染。網絡的傳播率閾值[27]可以表示為

(9)

其中,〈k〉為網絡的平均度,〈k2〉為網絡的二階平均度。

通過SIR模型可以衡量關鍵節點的傳播影響。選擇top-k節點集合,經過t次迭代實驗后,通過統計網絡中所有感染節點I以及免疫節點R的數量來衡量該集合的傳播影響力[28],影響力越大說明這些節點越重要,具體表示為

(10)

其中,t為迭代次數,k為所選擇的初始感染節點數目,NI,NR,N分別為t次迭代后網絡中已感染節點I、免疫節點R和整個網絡的數目。

3 實驗結果

3.1 實驗數據集

為了驗證NT方法的有效性,在6個真實網絡數據集上進行了相關實驗。6個真實網絡的數據集分別為海豚網絡Dolphins、爵士音樂家合作網絡Jazz、野鳥網絡Wildbird、加州理工網絡Caltech、社交網絡Reed和友誼網絡Friendships,這些數據集都來源于公開的網絡數據庫[29]。

本文驗證了真實網絡中三元閉包模體數目的顯著性。首先計算了統計量指標z,再通過p值檢驗了其顯著性水平。指標z衡量了該模體在隨機網絡和真實網絡上出現數目的差異情況,計算公式:

(11)

其中,|Treal|和|Trandom|分別為真實網絡和隨機網絡中三元閉包模體的數目,后者取100個具有相同節點數和平均度的隨機小世界網絡的平均值。std(|Trandom|)為三元閉包模體在所有隨機網絡出現數目的標準差。通過假設檢驗的方式,定義原假設為:真實網絡所對應的統計量z小于或等于隨機網絡所對應的統計量z′。總體分布視為正態分布,計算得到p值。若概率較小(p?0.001),則說明該事件具有統計顯著性。

表1展示了6個真實網絡的拓撲特征。其中N,M分別為網絡的節點數和邊數,βth為網絡的傳播率閾值,指標p和z用于評估三元閉包模體數目的統計顯著性[8]。結果表明,在6個真實網絡中,三元閉包模體的數目都具有統計顯著性。

表1 六個真實網絡的拓撲特征

3.2 實驗結果分析

3.2.1 魯棒性分析結果

圖2 不同攻擊條件下,網絡最大連通子圖比例變化情況

相比于其他方法,根據NT方法對節點的排序結果依次刪除節點,能使網絡中最大連通子圖比例更快下降。尤其在Dolphins和Wildbird網絡中,根據NT方法對關鍵節點的攻擊,出現了一階相變現象。這說明NT方法能夠有效評估節點的重要度,并識別出關鍵節點,刪除這些節點能使網絡碎片化,從而造成較大程度的破壞。

為量化關鍵節點識別方法的優劣,計算了網絡中最大連通子圖變化情況曲線下的面積,結果如表2所示。由表2可知,相比于其他方法,本文提出的關鍵節點識別方法,能夠使網絡最大連通子圖變化情況曲線下的面積最小,即能夠有效識別關鍵節點,進而破壞網絡的連通性。

表2 不同攻擊條件下,最大連通子圖變化情況曲線下的面積

網絡結構的破壞會阻礙節點間的通信,即影響網絡的全局效率。在6個真實網絡中,根據不同的節點排序結果,從網絡中依次刪除節點和它的連邊,并計算網絡全局效率的下降情況。考慮到計算效率,這里采用依次刪除1%比例節點的方式進行實驗。

實驗結果如圖3所示,其中橫坐標f表示網絡中移除節點的比例,縱坐標η表示剩余網絡的全局效率。相比于其他方法,根據NT方法對節點的排序結果依次刪除節點,能更快地造成網絡全局效率的下降。這說明NT方法對關鍵節點的識別更有效,對這些關鍵節點的攻擊能有效破壞網絡的整體功能。

圖3 不同攻擊條件下,網絡全局效率變化情況

3.2.2 傳播效果分析結果

為了進一步分析NT方法對網絡中關鍵節點的識別效果,選取了不同排序結果的top-k節點集作為初始感染節點集,在SIR模型上進行了傳播實驗。本文中迭代次數t取25,初始感染節點數目k取5,β取各個網絡的傳播率閾值。為了保證結果的可靠性,傳播結果取100次實驗的均值。實驗結果如圖4所示,其中橫坐標t表示傳播的迭代次數,縱坐標St表示網絡中感染節點的比例。

圖4 不同條件下,網絡中感染節點比例隨迭代次數的變化情況

相比于其他方法,NT方法識別出的關鍵節點集合,能夠更快地感染整個網絡。這種現象在Dolphins網絡中尤其顯著,NT方法選擇的關鍵節點能夠更有效地傳播信息。在其余5種網絡中,NT方法的識別效果沒有明顯優勢,但效果也接近于最優的方法。

實驗結果說明在6個真實網絡中,NT方法對網絡關鍵節點的識別效果優于K-shell方法,這可能與K-shell方法對網絡關鍵節點的識別過于粗粒化有關。整體來說,本文提出的NT方法能夠通過節點所在的三元閉包模體及其本身的度中心性來評估節點的重要度,有效識別出關鍵節點,這些關鍵節點對網絡具有較大的影響力。

4 結論

復雜網絡中關鍵節點的識別,有利于維護網絡結構魯棒性和保障網絡功能。本文提出了一種基于三元閉包模體的關鍵節點識別方法NT,該方法結合了三元閉包模體權重和節點度,來評估節點的重要度,為網絡關鍵節點的識別提供了新思路。在6個真實網絡中,進行了魯棒性實驗和SIR傳播模型實驗。對比于度中心性DC、K-shell分解、WL中心性、映射熵ME方法,NT方法更能有效地識別出關鍵節點,移除這些關鍵節點,對網絡造成的破壞更大。同時,這些關鍵節點具有更大的影響力,能夠更快地將信息傳播到網絡中的其他節點。該算法主要適用于無向無權網絡,在有向、有權網絡上,如何結合網絡中的三元閉包模體,對關鍵節點進行識別,是下一步的研究方向。