一種基于局部特征的節(jié)點重要性排序方法

朱敬成，王倫文，吳 濤

(國防科技大學(xué)電子對抗學(xué)院，安徽 合肥 230037)

1 引言

隨著網(wǎng)絡(luò)科學(xué)的快速發(fā)展，復(fù)雜網(wǎng)絡(luò)在國民經(jīng)濟、輿情引導(dǎo)、軍事斗爭等不同領(lǐng)域得到廣泛的應(yīng)用和發(fā)展。復(fù)雜網(wǎng)絡(luò)的研究由來已久，早在1998年，Duncan J.Watts和Steven HStrogatz就提出了小世界特性[1]。隨后Barabási與Albert在描繪萬維網(wǎng)時又提出了無標(biāo)度特性[2]。自從復(fù)雜網(wǎng)絡(luò)成為科研領(lǐng)域的研究熱點以來，研究表明網(wǎng)絡(luò)的結(jié)構(gòu)和機能主要受某些重要節(jié)點的影響，移除這些重要節(jié)點時會最大程度地毀壞網(wǎng)絡(luò)結(jié)構(gòu)，使得網(wǎng)絡(luò)喪失運轉(zhuǎn)機能。例如，蛋白質(zhì)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點識別可以探索蛋白質(zhì)之間的信息傳遞，進而揭示疾病的發(fā)病機理；輿情傳播網(wǎng)絡(luò)中可以通過對關(guān)鍵節(jié)點進行監(jiān)控從而掌握社會輿論動態(tài)，避免謠言的傳播；在道路網(wǎng)絡(luò)中，對關(guān)鍵節(jié)點采取一定的預(yù)防措施可以使得交通擁堵狀況得以改善，同時也可以減少交通事故的發(fā)生?？梢?，節(jié)點重要性分析有很高的應(yīng)用價值。

目前眾多科研人員已提出了許多關(guān)于節(jié)點重要性排序的經(jīng)典方法，常用方法有度中心性排序[3]、介數(shù)中心性排序[4]、接近中心性排序[5]等。其中度中心性是節(jié)點重要性排序最簡單的方法，而介數(shù)中心性和接近中心性因為其計算復(fù)雜度高而應(yīng)用受限。文獻[6]提出了一種涉及節(jié)點四階鄰居信息的半局部中心性(semi-local centrality，SLC)，在重要節(jié)點識別精度和耗時之間取得了一個平衡。文獻[7]提出了一種基于節(jié)點和節(jié)點鄰居度的方法(WL centrality)，認(rèn)為節(jié)點的度和節(jié)點的鄰居節(jié)點的度越大，節(jié)點就越重要，在復(fù)雜度和有效性方面都得到了提升。文獻[8]提出了一種基于度中心性的粗粒化關(guān)鍵點排序方法，稱為K-shell分解方法，然而K-shell方法存在很多節(jié)點分有相同值的問題，無法很好區(qū)分重要性。文獻[9]綜合了鄰居節(jié)點數(shù)和鄰居連接緊密程度提出了一種基于度和集聚系數(shù)的重要性排序方法，該方法可適用于大規(guī)模網(wǎng)絡(luò)。文獻[10]考慮了標(biāo)準(zhǔn)化后的節(jié)點自身度、節(jié)點鄰居度之和以及節(jié)點K-shell值提出了一種被稱為DKN的方法，考慮了不同方法的綜合效果。文獻[11]考慮到鄰居及次鄰居節(jié)點的個數(shù)和邊對節(jié)點重要性的影響，提出了基于節(jié)點和邊的NL中心性方法，進一步區(qū)分了節(jié)點的位置信息帶來的影響。文獻[12]將信息熵引入到節(jié)點重要性排序中，考慮了節(jié)點所有鄰居的相關(guān)性。文獻[13]定義了節(jié)點領(lǐng)域相似度，利用節(jié)點兩跳內(nèi)鄰居信息表征了節(jié)點的重要性。文獻[14]在電力網(wǎng)絡(luò)上采用了一種改進的泰爾熵的方法提出了一種節(jié)點綜合評估指標(biāo)，彌補了信息熵考慮因素單一的缺陷。文獻[15]將介數(shù)中心性和鄰居節(jié)點的度中心性結(jié)合提出了介度熵概念，獲取了更高了效率。文獻[16]研究了節(jié)點與直接鄰居節(jié)點及間接鄰居節(jié)點的關(guān)系，通過信息熵的方法定義了一種基于鄰接信息熵的節(jié)點重要性排序方法，該方法適用于多種類型網(wǎng)絡(luò)。

上述方法從不同方面評估了節(jié)點的重要性程度，考慮到度中心性計算復(fù)雜度低且適用于大規(guī)模網(wǎng)絡(luò)[17]，本文針對節(jié)點自身及其鄰居的度中心性提出一種重要性排序方法，該方法以節(jié)點自身以及節(jié)點一階鄰居的度值信息來衡量重要性。以網(wǎng)絡(luò)魯棒性和脆弱性為評價方法[18]，在不同網(wǎng)絡(luò)上將本文所提方法與度中心性DC、半局部中心性SLC、基于節(jié)點及其鄰居度的WL方法、K-shell分解方法、DKN方法以及基于節(jié)點和邊的NL方法進行比較，發(fā)現(xiàn)本文所提方法更能區(qū)分節(jié)點的重要性。

2 基于局部特征的節(jié)點重要性排序方法

2.1 網(wǎng)絡(luò)表示

假設(shè)網(wǎng)絡(luò)G=(V，E)，其中V和E分別表示網(wǎng)絡(luò)的節(jié)點集合和邊集合，對于含有n個節(jié)點和m條邊的網(wǎng)絡(luò)而言，網(wǎng)絡(luò)的鄰接矩陣A可以表示為

矩陣中元素aij表示節(jié)點i和節(jié)點j的連邊信息，如果aij=1，表示兩個節(jié)點相連，否則aij=0，則表示兩節(jié)點不直接相連。

2.2 局部特征排序方法

本文研究的對象是無權(quán)無向網(wǎng)絡(luò)，在研究中，節(jié)點的度中心性實質(zhì)上就是與節(jié)點直接相連的節(jié)點的數(shù)量，通過鄰接矩陣元素的值就可以得到節(jié)點的度值以及鄰居節(jié)點集合。度值可以用下面的式子表示

(1)

歸一化的度中心性方法可以表示為

(2)

由上式可知，度中心性方法可以直接用連邊信息反映了節(jié)點的影響度，從式(1)的計算過程中也可以看出度中心性方法擁有著簡單、直觀的特點。但是由于度中心性方法僅僅考慮自身信息無法全面反映節(jié)點的重要性，會出現(xiàn)大量節(jié)點重要性排序結(jié)果一致，從而應(yīng)用受限，不能精準(zhǔn)的對節(jié)點重要性進行排序，因而引入了鄰居信息更加全面的反映節(jié)點的重要性。

圖1 示例網(wǎng)絡(luò)

以圖1的示例網(wǎng)絡(luò)進行說明，使用度中心性計算示例的網(wǎng)絡(luò)的重要性時得到下面結(jié)果：kv1=kv7=kv8，kv2=kv4，kv3=kv6，從計算結(jié)果來看度中心性由于只考慮自身信息而導(dǎo)致許多節(jié)點重要性無法識別，識別的區(qū)分度和準(zhǔn)確率低。

從上述分析結(jié)果來看僅從自身去分析節(jié)點的重要性有很大的局限性，考慮到節(jié)點的鄰居對節(jié)點重要性也有一定的影響，本文針對度中心性方法這一局限性對節(jié)點及其一階鄰居進行研究，提出了一種新的局部特征的DND方法，該方法定義為

(3)

式(3)中Γi表示節(jié)點i的一階鄰居節(jié)點的集合。DND方法越大，說明節(jié)點的重要性越高，排序越靠前。

以圖1的示例網(wǎng)絡(luò)中節(jié)點v2為例，節(jié)點v2的鄰居集為{v1，v3}，由于kv1=1，則αv1=-1，而kv3=4，則αv3=1，又kv2=2，故

在研究中如果僅按照度中心性區(qū)分重要性會存在多個節(jié)點度值相同的情形，進而模糊了部分節(jié)點的重要性排序。而使用DND方法計算節(jié)點重要性時得到的區(qū)分結(jié)果為DNDv3>DNDv6，DNDv2=DNDv4，DNDv1>DNDv8>DNDv7。從計算結(jié)果可以得到DND方法相比度中心性方法在節(jié)點重要性排序上更有準(zhǔn)確的結(jié)論。

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

本文基于網(wǎng)絡(luò)的魯棒性和脆弱性對節(jié)點的重要性進行研究，這種研究方法主要考察的是移除節(jié)點對網(wǎng)絡(luò)的結(jié)構(gòu)和功能造成的影響，節(jié)點移除對網(wǎng)絡(luò)結(jié)構(gòu)影響越大，說明該節(jié)點越重要[19]，可以以此來評估節(jié)點重要性排序方法的準(zhǔn)確性。在這里采用獨立部分比例[20]和最大連通子圖[21]相對大小來評估節(jié)點對網(wǎng)絡(luò)結(jié)構(gòu)和功能的影響，可以通過變化趨勢圖直觀地得到方法排序結(jié)果的準(zhǔn)確性。

3.1 獨立部分比例

獨立部分比例指的是移除節(jié)點的邊后網(wǎng)絡(luò)的連通子圖數(shù)量比例，可以反映節(jié)點被摧毀成獨立部分的程度。將節(jié)點按照方法評估的重要性順序從大到小排序，觀察移除節(jié)點邊后對網(wǎng)絡(luò)節(jié)點獨立化的影響，獨立部分比例計算公式可以表示為

(4)

式中，R表示獨立子圖數(shù)量，n表示網(wǎng)絡(luò)的節(jié)點總數(shù)。若按照排序結(jié)果蓄意攻擊使得獨立部分?jǐn)?shù)目更多且最快達到完全獨立，說明該種方法的節(jié)點重要性排序更有效。

3.2 最大連通子圖比例

按照節(jié)點重要性挖掘的方法得到節(jié)點重要性排序后，按照重要性排序結(jié)果移除節(jié)點，移除節(jié)點將會對網(wǎng)絡(luò)結(jié)構(gòu)造成一定影響，產(chǎn)生的網(wǎng)絡(luò)巨片[22]的節(jié)點數(shù)目與網(wǎng)絡(luò)節(jié)點總數(shù)之比稱之為最大連通子圖比例。計算公式為

(5)

式中S為按照排序結(jié)果移除一定比例的節(jié)點后網(wǎng)絡(luò)巨片中包含的節(jié)點數(shù)，n則為網(wǎng)絡(luò)節(jié)點總數(shù)，最大連通子圖可以很好地反映網(wǎng)絡(luò)的結(jié)構(gòu)變化，可以通過觀察移除節(jié)點后網(wǎng)絡(luò)巨片的變化趨勢來衡量排序性結(jié)果的有效性，隨著節(jié)點的移除網(wǎng)絡(luò)巨片的規(guī)模下降的越快，說明該方法對網(wǎng)絡(luò)的結(jié)構(gòu)性破壞效果更加明顯，節(jié)點就越重要。

4 實驗分析

4.1 實驗環(huán)境及數(shù)據(jù)集

本文中實驗所用的電腦配置為Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz的處理器，內(nèi)存為12GB。軟件環(huán)境為Matlab R2018b。為了評估本文提出的節(jié)點重要性排序方法的有效性，選取六個不同結(jié)構(gòu)的真實網(wǎng)絡(luò)和三個人工生成的網(wǎng)絡(luò)進行實驗。六個真實網(wǎng)絡(luò)分別為USAir美國航空網(wǎng)絡(luò)[23]，Slavko在Facebook上的朋友圈關(guān)系網(wǎng)絡(luò)[24]，Infectious人群感染網(wǎng)絡(luò)[25]，蛋白質(zhì)間相互作用的Yeast網(wǎng)絡(luò)[23]，Email郵件網(wǎng)絡(luò)[25]，Power美國西部國家電力網(wǎng)絡(luò)[23]。三個人工網(wǎng)絡(luò)分別為ER隨機網(wǎng)絡(luò)、WS小世界網(wǎng)絡(luò)以及BA無標(biāo)度網(wǎng)絡(luò)，參數(shù)設(shè)置如下所示：

ER隨機網(wǎng)絡(luò)：節(jié)點總數(shù)n=5000，節(jié)點連邊概率p=0.0012；

WS小世界網(wǎng)絡(luò)：節(jié)點總數(shù)n=5000，領(lǐng)域節(jié)點個數(shù)K=6，重連概率p=0.1；

BA無標(biāo)度網(wǎng)絡(luò)：節(jié)點總數(shù)n=5000，初始連通節(jié)點個數(shù)m0=13，每次引入新節(jié)點時新生成的邊數(shù)ml=6。

實驗網(wǎng)絡(luò)數(shù)據(jù)集的詳細信息如表1所示，其中n和m分別表示網(wǎng)絡(luò)的節(jié)點數(shù)量以及網(wǎng)絡(luò)的連邊數(shù)目，表示網(wǎng)絡(luò)中節(jié)點的平均度大小，D為網(wǎng)絡(luò)直徑，L則為網(wǎng)絡(luò)的平均路徑長度[26]。

表1 網(wǎng)絡(luò)拓?fù)鋮?shù)

4.2 實驗結(jié)果分析

在多個網(wǎng)絡(luò)數(shù)據(jù)集上，將本文提出的DND方法同都由局部信息進行排序的度中心性方法、半局部中心性方法、WL方法、K-shell方法、DKN方法以及基于節(jié)點和邊的NL方法進行比較和分析。以各方法從大到小結(jié)果進行排序，按照各方法排序順序?qū)ο鄳?yīng)節(jié)點進行蓄意攻擊，攻擊的形式為按重要性順序移除節(jié)點或者移除節(jié)點連邊，實驗結(jié)果如圖2和圖3所示。

圖2(a)-(i)展現(xiàn)的是移除節(jié)點邊后網(wǎng)絡(luò)的獨立部分比例，獨立部分越多，說明網(wǎng)絡(luò)被化整為零的更徹底，在不同網(wǎng)絡(luò)中，DND方法相比其它幾個方法在相同條件下更能使得網(wǎng)絡(luò)分成更多的組成部分，且相比其它方法能夠使得網(wǎng)絡(luò)節(jié)點最快達到完全獨立，即網(wǎng)絡(luò)節(jié)點不存在連邊。原因在于要想使得獨立部分越多，對于連邊多的節(jié)點破壞起來就比連邊少的節(jié)點更有可能分解成更多部分，而度中心性由于區(qū)分度不夠，無法區(qū)分出相同連邊的節(jié)點，本文提出的DND方法相比度中心性不光考慮自身同時也考慮一階鄰居的影響，使得度值相同的點也能區(qū)分出重要性，以本文提出的DND方法對節(jié)點重要性更有分辨能力，對網(wǎng)絡(luò)的分解能力更強。

圖2 不同方法對網(wǎng)絡(luò)重要性排序后移除一定比例節(jié)點連邊產(chǎn)生的獨立部分比例

圖3反映的是各方法蓄意攻擊所造成的網(wǎng)絡(luò)最大連通子圖變化趨勢，是各方法對節(jié)點重要性排序后，按照節(jié)點重要性程度以一定比例移除節(jié)點，所展現(xiàn)的是最大連通子圖中的節(jié)點數(shù)所占總數(shù)比例。從圖中可以看出對于所有網(wǎng)絡(luò)而言，本文提出DND方法相比度中心性方法、半局部中心性方法、WL方法、K-shell方法、DKN方法以及NL方法變化趨勢更明顯，可以觀察到Email網(wǎng)絡(luò)和Yeast網(wǎng)絡(luò)從一開始就表現(xiàn)出比其它方法更好的效果。由于ER和WS網(wǎng)絡(luò)是隨機網(wǎng)絡(luò)，節(jié)點度值較為均勻，圖3(g)(h)在移除小部分節(jié)點后各方法之間效果相差不大，而WS網(wǎng)絡(luò)的度值相對ER網(wǎng)絡(luò)更加集中，故就度中心性方法而言ER網(wǎng)絡(luò)在后期破壞效果比WS網(wǎng)絡(luò)好，而在兩個網(wǎng)絡(luò)中都是K-shell方法破壞網(wǎng)絡(luò)結(jié)構(gòu)的效果最差，對節(jié)點重要性無法做到有效區(qū)分，原因在于賦予許多節(jié)點相同值。圖3(i)展現(xiàn)了BA網(wǎng)絡(luò)的優(yōu)先連接特性，即新節(jié)點優(yōu)先與強連接度的節(jié)點相連，導(dǎo)致少數(shù)關(guān)鍵節(jié)點連接了大部分的節(jié)點[27]。正是由于優(yōu)先連接特性，度中心性方法在BA網(wǎng)絡(luò)中破壞效果相比其它方法優(yōu)勢很大。

總的來說，本文提出的DND方法在獨立部分比例實驗相比其它方法可以更快將網(wǎng)絡(luò)分解成一個個獨立的部分。在最大連通子圖比例實驗中可以得到本文所提方法在節(jié)點重要性排序上準(zhǔn)確性更高，更易摧毀網(wǎng)絡(luò)。

5 結(jié)束語

復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點的識別是復(fù)雜網(wǎng)絡(luò)理論研究的重要一部分，隨著網(wǎng)絡(luò)化的迅猛發(fā)展，生活中伴隨著各種各樣的網(wǎng)絡(luò)，識別出其中的關(guān)鍵節(jié)點有助于提高網(wǎng)絡(luò)的抗毀性，維持住網(wǎng)絡(luò)的穩(wěn)定性[28]，具有重要的理論和現(xiàn)實意義。本文基于節(jié)點及其一階鄰居節(jié)的點度中心性提出了一種局部特征的重要性排序方法，此方法只需要考慮節(jié)點和一階鄰居節(jié)點的度中心性方法，容易獲得計算參數(shù)且適用于大規(guī)模網(wǎng)絡(luò)。本文在六個真實網(wǎng)絡(luò)和三個人工網(wǎng)絡(luò)上利用獨立部分比例和最大連通子圖對提出的方法進行了驗證，最終結(jié)果表明本文所提的DND方法相比度中心性方法、半局部中心性方法、WL方法、K-shell方法、DKN方法以及NL方法在節(jié)點重要性排序上結(jié)果更加精準(zhǔn)。由于網(wǎng)絡(luò)的復(fù)雜性，結(jié)構(gòu)的多樣性，現(xiàn)如今還是沒有一個方法可以適用于所有的網(wǎng)絡(luò)，但本文所提的方法簡單且適用網(wǎng)絡(luò)范圍廣，為鄰居節(jié)點對節(jié)點重要性影響的研究提供了一個新方法。

圖3 不同方法對網(wǎng)絡(luò)重要性排序后移除一定比例節(jié)點后產(chǎn)生的最大連通子圖比例