基于三元閉包模體的關(guān)鍵節(jié)點(diǎn)識別方法

徐 越,劉雪明

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

0 引言

復(fù)雜網(wǎng)絡(luò)能夠描述許多真實(shí)系統(tǒng),如社交網(wǎng)絡(luò)、貿(mào)易網(wǎng)絡(luò)和交通運(yùn)輸網(wǎng)絡(luò)等,網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)與其結(jié)構(gòu)穩(wěn)定性和系統(tǒng)功能緊密相關(guān)[1]。對于關(guān)鍵節(jié)點(diǎn)的識別,能夠為提高系統(tǒng)的魯棒性和效率提供針對性建議[2]。例如,在社交網(wǎng)絡(luò)中,識別出關(guān)鍵用戶,能夠控制社交信息的交互和傳遞,從而有效控制網(wǎng)絡(luò)輿情。在貿(mào)易網(wǎng)絡(luò)中,關(guān)鍵節(jié)點(diǎn)的識別能夠確定貿(mào)易樞紐,對于維持貿(mào)易網(wǎng)絡(luò)的穩(wěn)定性以及提高貿(mào)易效率具有重要意義。在交通運(yùn)輸網(wǎng)絡(luò)中,關(guān)鍵節(jié)點(diǎn)能夠影響網(wǎng)絡(luò)的整體連通性。在經(jīng)受自然災(zāi)害等破壞時,對于關(guān)鍵節(jié)點(diǎn)的維護(hù),能夠有效保障交通運(yùn)輸網(wǎng)絡(luò)的順暢運(yùn)行。

現(xiàn)階段有多種關(guān)鍵節(jié)點(diǎn)的識別方法。節(jié)點(diǎn)的中心性指標(biāo),例如度中心性[3]、介數(shù)中心性[4]等,是識別關(guān)鍵節(jié)點(diǎn)的經(jīng)典方法。K-shell[5]方法采用逐層分離節(jié)點(diǎn)的方式,獲取網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。WL[6]方法考慮了節(jié)點(diǎn)自身的度和鄰居節(jié)點(diǎn)的度,認(rèn)為鄰居節(jié)點(diǎn)的度越大,節(jié)點(diǎn)越重要。映射熵ME[7]方法進(jìn)一步考慮了鄰居節(jié)點(diǎn)的影響,通過節(jié)點(diǎn)與所有鄰居節(jié)點(diǎn)的連接情況來評估其重要度。

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

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

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

定義無向無權(quán)網(wǎng)絡(luò)G=(V,E),其中V為網(wǎng)絡(luò)的節(jié)點(diǎn)集,E為網(wǎng)絡(luò)的邊集。圖1a展示了網(wǎng)絡(luò)中三元閉包模體的示意圖,該結(jié)構(gòu)具有3個節(jié)點(diǎn),節(jié)點(diǎn)之間具有強(qiáng)聯(lián)系,彼此之間有邊直接相連。三元閉包模體中的任意兩節(jié)點(diǎn)間,都有兩條較短的獨(dú)立路徑,兼具魯棒性和高效性。如圖1b所示,在相同節(jié)點(diǎn)數(shù)和邊數(shù)情況下,相比于四元閉包模體,三元閉包模體結(jié)構(gòu)異質(zhì)性更強(qiáng),對該結(jié)構(gòu)中關(guān)鍵節(jié)點(diǎn)的破壞,能夠?qū)W(wǎng)絡(luò)的連通性和效率產(chǎn)生較大影響。

圖1 三元閉包模體示例

各個三元閉包模體對網(wǎng)絡(luò)拓?fù)溥B通性的影響不同。節(jié)點(diǎn)的重要度不僅與本身的度中心性有關(guān),同時還與其所在的三元閉包模體有關(guān)。如圖1c所示,節(jié)點(diǎn)3和節(jié)點(diǎn)5具有相同的度中心性,所屬三元閉包模體的數(shù)目都為1,但對應(yīng)三元閉包模體的拓?fù)湮恢貌煌?。按度選擇節(jié)點(diǎn)來對網(wǎng)絡(luò)進(jìn)行攻擊時,4個節(jié)點(diǎn)沒有區(qū)分度。若刪除節(jié)點(diǎn)3及其連邊,網(wǎng)絡(luò)中剩余最大連通子圖的大小為6。若刪除節(jié)點(diǎn)5及其連邊,網(wǎng)絡(luò)中剩余最大連通子圖的大小為5。類似節(jié)點(diǎn)度的定義,本文提出了三元閉包模體權(quán)重T(j)的概念,即取模體中所有節(jié)點(diǎn)度的均值,具體表示為

(1)

其中,n為屬于該三元閉包模體T的節(jié)點(diǎn),kn為節(jié)點(diǎn)n的度中心性。

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

(2)

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

2 對比算法及評價指標(biāo)

2.1 對比算法

1)度中心性。度中心性通過統(tǒng)計節(jié)點(diǎn)的連接數(shù)來衡量節(jié)點(diǎn)的重要度。在無權(quán)無向網(wǎng)絡(luò)中,可以表示為

(3)

其中,N為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù),eij為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的連接關(guān)系,若有連接則eij為1,否則為0。

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

3)WL中心性。WL中心性方法認(rèn)為節(jié)點(diǎn)所連邊越重要,則該節(jié)點(diǎn)越重要。首先定義了邊的權(quán)重,表示為

wij=ki×kj

(4)

其中,wij為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間連邊的權(quán)重,ki為節(jié)點(diǎn)i的度。節(jié)點(diǎn)i的重要度取決于其所有連邊的權(quán)重,可以定義為

(5)

其中,Γi為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集。

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

(6)

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

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

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

2.2.1 魯棒性分析

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

(7)

其中,S為刪除一定比例節(jié)點(diǎn)后,剩余網(wǎng)絡(luò)中最大連通子圖的大小,N為原始網(wǎng)絡(luò)的節(jié)點(diǎn)個數(shù)。依次移除節(jié)點(diǎn),最大連通子圖比例下降越快,說明關(guān)鍵節(jié)點(diǎn)識別方法越有效。通常用最大連通子圖比例變化曲線下的面積,來量化關(guān)鍵節(jié)點(diǎn)識別方法的有效性。曲線下的面積越小,對應(yīng)的關(guān)鍵節(jié)點(diǎn)識別方法越有效。

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

(8)

其中,N為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù),dij為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間最短路徑的長度,V為網(wǎng)絡(luò)的節(jié)點(diǎn)集。依次移除節(jié)點(diǎn),網(wǎng)絡(luò)全局效率變化越快,說明關(guān)鍵節(jié)點(diǎn)識別方法越有效。

2.2.2 傳播效果分析

SIR是經(jīng)典的傳染病模型,將節(jié)點(diǎn)分為易感染節(jié)點(diǎn)S、已感染節(jié)點(diǎn)I、免疫節(jié)點(diǎn)R[26]。已感染節(jié)點(diǎn)I會以β的概率感染易感染節(jié)點(diǎn)S,同時以γ的概率恢復(fù)為免疫節(jié)點(diǎn)R。免疫節(jié)點(diǎn)R不會再次被感染。網(wǎng)絡(luò)的傳播率閾值[27]可以表示為

(9)

其中,〈k〉為網(wǎng)絡(luò)的平均度,〈k2〉為網(wǎng)絡(luò)的二階平均度。

通過SIR模型可以衡量關(guān)鍵節(jié)點(diǎn)的傳播影響。選擇top-k節(jié)點(diǎn)集合,經(jīng)過t次迭代實(shí)驗后,通過統(tǒng)計網(wǎng)絡(luò)中所有感染節(jié)點(diǎn)I以及免疫節(jié)點(diǎn)R的數(shù)量來衡量該集合的傳播影響力[28],影響力越大說明這些節(jié)點(diǎn)越重要,具體表示為

(10)

其中,t為迭代次數(shù),k為所選擇的初始感染節(jié)點(diǎn)數(shù)目,NI,NR,N分別為t次迭代后網(wǎng)絡(luò)中已感染節(jié)點(diǎn)I、免疫節(jié)點(diǎn)R和整個網(wǎng)絡(luò)的數(shù)目。

3 實(shí)驗結(jié)果

3.1 實(shí)驗數(shù)據(jù)集

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

本文驗證了真實(shí)網(wǎng)絡(luò)中三元閉包模體數(shù)目的顯著性。首先計算了統(tǒng)計量指標(biāo)z,再通過p值檢驗了其顯著性水平。指標(biāo)z衡量了該模體在隨機(jī)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上出現(xiàn)數(shù)目的差異情況,計算公式:

(11)

其中,|Treal|和|Trandom|分別為真實(shí)網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)中三元閉包模體的數(shù)目,后者取100個具有相同節(jié)點(diǎn)數(shù)和平均度的隨機(jī)小世界網(wǎng)絡(luò)的平均值。std(|Trandom|)為三元閉包模體在所有隨機(jī)網(wǎng)絡(luò)出現(xiàn)數(shù)目的標(biāo)準(zhǔn)差。通過假設(shè)檢驗的方式,定義原假設(shè)為:真實(shí)網(wǎng)絡(luò)所對應(yīng)的統(tǒng)計量z小于或等于隨機(jī)網(wǎng)絡(luò)所對應(yīng)的統(tǒng)計量z′?？傮w分布視為正態(tài)分布,計算得到p值。若概率較小(p?0.001),則說明該事件具有統(tǒng)計顯著性。

表1展示了6個真實(shí)網(wǎng)絡(luò)的拓?fù)涮卣?。其中N,M分別為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和邊數(shù),βth為網(wǎng)絡(luò)的傳播率閾值,指標(biāo)p和z用于評估三元閉包模體數(shù)目的統(tǒng)計顯著性[8]。結(jié)果表明,在6個真實(shí)網(wǎng)絡(luò)中,三元閉包模體的數(shù)目都具有統(tǒng)計顯著性。

表1 六個真實(shí)網(wǎng)絡(luò)的拓?fù)涮卣?/p>

3.2 實(shí)驗結(jié)果分析

3.2.1 魯棒性分析結(jié)果

圖2 不同攻擊條件下,網(wǎng)絡(luò)最大連通子圖比例變化情況

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

為量化關(guān)鍵節(jié)點(diǎn)識別方法的優(yōu)劣,計算了網(wǎng)絡(luò)中最大連通子圖變化情況曲線下的面積,結(jié)果如表2所示。由表2可知,相比于其他方法,本文提出的關(guān)鍵節(jié)點(diǎn)識別方法,能夠使網(wǎng)絡(luò)最大連通子圖變化情況曲線下的面積最小,即能夠有效識別關(guān)鍵節(jié)點(diǎn),進(jìn)而破壞網(wǎng)絡(luò)的連通性。

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

網(wǎng)絡(luò)結(jié)構(gòu)的破壞會阻礙節(jié)點(diǎn)間的通信,即影響網(wǎng)絡(luò)的全局效率。在6個真實(shí)網(wǎng)絡(luò)中,根據(jù)不同的節(jié)點(diǎn)排序結(jié)果,從網(wǎng)絡(luò)中依次刪除節(jié)點(diǎn)和它的連邊,并計算網(wǎng)絡(luò)全局效率的下降情況。考慮到計算效率,這里采用依次刪除1%比例節(jié)點(diǎn)的方式進(jìn)行實(shí)驗。

實(shí)驗結(jié)果如圖3所示,其中橫坐標(biāo)f表示網(wǎng)絡(luò)中移除節(jié)點(diǎn)的比例,縱坐標(biāo)η表示剩余網(wǎng)絡(luò)的全局效率。相比于其他方法,根據(jù)NT方法對節(jié)點(diǎn)的排序結(jié)果依次刪除節(jié)點(diǎn),能更快地造成網(wǎng)絡(luò)全局效率的下降。這說明NT方法對關(guān)鍵節(jié)點(diǎn)的識別更有效,對這些關(guān)鍵節(jié)點(diǎn)的攻擊能有效破壞網(wǎng)絡(luò)的整體功能。

圖3 不同攻擊條件下,網(wǎng)絡(luò)全局效率變化情況

3.2.2 傳播效果分析結(jié)果

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

圖4 不同條件下,網(wǎng)絡(luò)中感染節(jié)點(diǎn)比例隨迭代次數(shù)的變化情況

相比于其他方法,NT方法識別出的關(guān)鍵節(jié)點(diǎn)集合,能夠更快地感染整個網(wǎng)絡(luò)。這種現(xiàn)象在Dolphins網(wǎng)絡(luò)中尤其顯著,NT方法選擇的關(guān)鍵節(jié)點(diǎn)能夠更有效地傳播信息。在其余5種網(wǎng)絡(luò)中,NT方法的識別效果沒有明顯優(yōu)勢,但效果也接近于最優(yōu)的方法。

實(shí)驗結(jié)果說明在6個真實(shí)網(wǎng)絡(luò)中,NT方法對網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的識別效果優(yōu)于K-shell方法,這可能與K-shell方法對網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的識別過于粗?；嘘P(guān)。整體來說,本文提出的NT方法能夠通過節(jié)點(diǎn)所在的三元閉包模體及其本身的度中心性來評估節(jié)點(diǎn)的重要度,有效識別出關(guān)鍵節(jié)點(diǎn),這些關(guān)鍵節(jié)點(diǎn)對網(wǎng)絡(luò)具有較大的影響力。

4 結(jié)論

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