面向復(fù)雜網(wǎng)絡(luò)的多屬性決策關(guān)鍵節(jié)點(diǎn)識別算法研究*

寧 陽 武志峰 張 策

（天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院 天津 300222）

1 引言

網(wǎng)絡(luò)中的關(guān)鍵點(diǎn)識別算法是網(wǎng)絡(luò)科學(xué)的重要研究內(nèi)容之一。關(guān)鍵點(diǎn)識別算法的研究在醫(yī)學(xué)、社會學(xué)、網(wǎng)絡(luò)安全、電力交通、政治與經(jīng)濟(jì)學(xué)領(lǐng)域具有重要意義。在社會網(wǎng)絡(luò)中通過最有影響力的人的查找，可以控制流言的傳播；在疾病爆發(fā)區(qū)域通過易感人群的查找，可以對疾病進(jìn)行有效地預(yù)防和控制；在城市交通系統(tǒng)、電力系統(tǒng)中通過對關(guān)鍵樞紐的識別和重點(diǎn)維護(hù)，可以降低經(jīng)濟(jì)損失風(fēng)險。對復(fù)雜網(wǎng)絡(luò)有效管理的關(guān)鍵是有效識別網(wǎng)絡(luò)中的關(guān)鍵結(jié)點(diǎn)。目前，解決這一問題的算法通常采用基于圖論的概念和術(shù)語，將具體實(shí)際問題抽象為圖，進(jìn)而得到具體實(shí)際網(wǎng)絡(luò)的拓?fù)湫再|(zhì)。相關(guān)研究通常是在常用指標(biāo)進(jìn)行改進(jìn)和將多個指標(biāo)進(jìn)行融合［1～4］，因?yàn)槎戎行男裕?］算法雖然簡單高效，卻沒有考慮網(wǎng)絡(luò)的全局結(jié)構(gòu)；介數(shù)中心性［6］、接近中心性［7～8］考慮了網(wǎng)絡(luò)的全局結(jié)構(gòu)，但算法時間復(fù)雜度高，并不適合在大規(guī)模網(wǎng)絡(luò)中應(yīng)用；Kitsak等考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置，提出k-shell［9］分解方法，能夠適用于大規(guī)模網(wǎng)絡(luò)，由于網(wǎng)絡(luò)中存在大量度值相同的節(jié)點(diǎn)，k-shell排序方法的分辨率不高；為解決k-shell方法劃分結(jié)果粗粒化的問題，鄧凱旋［10］等提出根據(jù)節(jié)點(diǎn)刪除過程中迭代層數(shù)，結(jié)合節(jié)點(diǎn)度和鄰居節(jié)點(diǎn)，改進(jìn)k-shell方法識別關(guān)鍵節(jié)點(diǎn)；李懂［11］等提出融合節(jié)點(diǎn)度和K核迭代次數(shù)的多屬性決策方法，通過熵權(quán)法衡量節(jié)點(diǎn)重要性；Liu［12］等提出結(jié)合當(dāng)前節(jié)點(diǎn)所在ks值及最大ks值，計(jì)算節(jié)點(diǎn)到最大K核節(jié)點(diǎn)集合的最短距離，進(jìn)而區(qū)分ks值相同的節(jié)點(diǎn)；Bae等［13］提出考慮局部范圍內(nèi)節(jié)點(diǎn)的ks值，節(jié)點(diǎn)兩層鄰居節(jié)點(diǎn)的ks值和，借鑒局部中心性思想改進(jìn)k-shell；顧亦然等［14］將k-shell與重要度貢獻(xiàn)矩陣相結(jié)合，引入影響度的概念進(jìn)行關(guān)鍵節(jié)點(diǎn)識別。然而，隨著網(wǎng)絡(luò)規(guī)模的不斷增大，現(xiàn)有算法在衡量節(jié)點(diǎn)影響力的準(zhǔn)確性和效率上，均出現(xiàn)了明顯不足，難以應(yīng)對日益復(fù)雜網(wǎng)絡(luò)的各類新問題。本文基于節(jié)點(diǎn)度、改進(jìn)的K核迭代次數(shù)指標(biāo)，使用熵權(quán)法［15］、灰色關(guān)聯(lián)度分析法［16］多屬性決策關(guān)鍵節(jié)點(diǎn)，更有效地進(jìn)行關(guān)鍵節(jié)點(diǎn)識別。

2 相關(guān)概念

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

將一個具體網(wǎng)絡(luò)抽象為一個由點(diǎn)集V和邊集E組成的圖G=（V，E）。頂點(diǎn)數(shù)記為N=|V|，邊數(shù)記為M=|E|。無向無權(quán)圖G的鄰接矩陣A=（aij）N×N是一個N階方陣，第i行第j列上的元素aij定義如下：

2.2 相關(guān)算法

k-殼分解，通過去除網(wǎng)絡(luò)中度值為1的節(jié)點(diǎn)及其連邊，將過程中產(chǎn)生新的度為1的節(jié)點(diǎn)劃分到同一層，直至網(wǎng)絡(luò)中每個節(jié)點(diǎn)的度值至少為2。重復(fù)操作，去除網(wǎng)絡(luò)中度值為2的節(jié)點(diǎn)及其連邊，直至網(wǎng)絡(luò)中不再有度值為2的節(jié)點(diǎn)為止。k=1，2，3…，直至網(wǎng)絡(luò)中的每一個節(jié)點(diǎn)均被劃分到相應(yīng)的k-殼中，每一個節(jié)點(diǎn)對應(yīng)唯一的ks值，且k-殼中所包含的節(jié)點(diǎn)度值滿足ki≥ks。所有ks≥k的k-殼的并集為網(wǎng)絡(luò)的k-核［17］。實(shí)際網(wǎng)絡(luò)中就某些問題而言度大的節(jié)點(diǎn)通過k-殼分解的方法，由于具有較小的ks值不一定是重要節(jié)點(diǎn)［18］。圖1是由17個頂點(diǎn)組成的小網(wǎng)絡(luò)，節(jié)點(diǎn)v6的度大于節(jié)點(diǎn)v11，ks值小于v11。

圖1 示例圖三角形節(jié)點(diǎn)ks=1方形節(jié)點(diǎn)ks=2圓形節(jié)點(diǎn)ks=3

其中公式涉及的k（i）為節(jié)點(diǎn)度，n（i）為節(jié)點(diǎn)迭代次數(shù)，Γ(i)為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合。

文獻(xiàn)［10］通過k-shell分解過程中節(jié)點(diǎn)被刪除的順序定義迭代次數(shù)增加ks值區(qū)分程度，結(jié)合節(jié)點(diǎn)度衡量節(jié)點(diǎn)重要性，該指標(biāo)值越大，節(jié)點(diǎn)越重要，如式（1）所示：

文獻(xiàn)［11］通過熵權(quán)法計(jì)算節(jié)點(diǎn)度值和迭代次數(shù)兩個指標(biāo)的權(quán)重w1、w2，計(jì)算權(quán)重因子Vw，結(jié)合節(jié)點(diǎn)本身及鄰居節(jié)點(diǎn)的權(quán)重因子得到節(jié)點(diǎn)的綜合重要性值DK（i），如式（2）所示：

文獻(xiàn)［13］提出通過鄰居節(jié)點(diǎn)的ks值衡量節(jié)點(diǎn)重要性，通過擴(kuò)展得到Cnc+值，如式（3）所示：

3 k-shell多屬性決策改進(jìn)算法

3.1 改進(jìn)K核迭代次數(shù)指標(biāo)

節(jié)點(diǎn)度是一種局部性指標(biāo)，可以反映節(jié)點(diǎn)的影響能力，K核迭代次數(shù)反映節(jié)點(diǎn)的全局位置，計(jì)算K核迭代次數(shù)時，k-殼分解方法中的節(jié)點(diǎn)刪除順序不再從度值小于k，k=1，2，3…累計(jì)計(jì)算，直到網(wǎng)絡(luò)中每個節(jié)點(diǎn)都對應(yīng)唯一一個ks值。改為按照度值刪除度值最小的節(jié)點(diǎn)，ks值遞增，計(jì)算每個節(jié)點(diǎn)的ks值；K核迭代次數(shù)是在ks值的基礎(chǔ)上計(jì)算得到，剝除網(wǎng)絡(luò)中度值小于等于k的節(jié)點(diǎn)，若產(chǎn)生新的滿足剝除條件的節(jié)點(diǎn)，此時依舊首先去除度值最小的節(jié)點(diǎn)，ks值不變，節(jié)點(diǎn)刪除的迭代次數(shù)累加，節(jié)點(diǎn)的迭代次數(shù)即被刪除的順序。通過計(jì)算節(jié)點(diǎn)到最大核節(jié)點(diǎn)集的平均距離改進(jìn)K核迭代次數(shù)，進(jìn)一步區(qū)分相同K核迭代次數(shù)值，以此劃分節(jié)點(diǎn)重要程度，本質(zhì)為了增加ks值區(qū)分程度，解決粗?；瘎澐謫栴}。節(jié)點(diǎn)度和K核迭代次數(shù)為效益型指標(biāo)［15］。

定義成本型指標(biāo)節(jié)點(diǎn)到最大核節(jié)點(diǎn)的平均距離Ave_d和改進(jìn)后迭代次數(shù)值n′，如式（4）所示：

其中，φ(G)為網(wǎng)絡(luò)中最大核節(jié)點(diǎn)集合。

3.2 構(gòu)造規(guī)范化決策矩陣

通過計(jì)算節(jié)點(diǎn)的上述指標(biāo)，構(gòu)建規(guī)范化決策矩陣RM×N，M=2，N為網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)。Rij分別表示度值、改進(jìn)迭代次數(shù)標(biāo)準(zhǔn)化后值，i=1，2。

規(guī)范化決策矩陣處理方式［15］：

3.3 熵權(quán)法確定權(quán)重

熵權(quán)法根據(jù)各項(xiàng)指標(biāo)所包含的信息量的大小來確定指標(biāo)權(quán)重的客觀賦權(quán)法［15，19］。首先對決策矩陣R進(jìn)行歸一化處理，得到R′，其次計(jì)算第i項(xiàng)指標(biāo)的熵值Evi，如式（8）所示，然后根據(jù)熵值Evi計(jì)算兩個指標(biāo)各自權(quán)重wi：

3.4 灰色關(guān)聯(lián)度分析法確定權(quán)重

3.5 綜合評估節(jié)點(diǎn)重要性

根據(jù)wi綜合評估節(jié)點(diǎn)重要性：

考慮局部信息，結(jié)合鄰居節(jié)點(diǎn)定義重要性評價指標(biāo)：

其中，使用熵權(quán)法確定權(quán)值計(jì)算得到的衡量節(jié)點(diǎn)重要性指標(biāo)記為EDI，使用灰色關(guān)聯(lián)度分析法確定權(quán)重方法得到的指標(biāo)記為GDI。

算法步驟：

1）計(jì)算網(wǎng)絡(luò)中每個節(jié)點(diǎn)的度、改進(jìn)的迭代次數(shù)；

2）分別使用熵權(quán)法、灰色關(guān)聯(lián)度分析法按照式（6）、（7）效益型指標(biāo)規(guī)范化決策矩陣；

3）按照兩種賦權(quán)方法計(jì)算每個指標(biāo)的貢獻(xiàn)權(quán)重；

4）根據(jù)式（14）計(jì)算每個節(jié)點(diǎn)的EDI、GDI值。

4 實(shí)驗(yàn)分析

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

4.1.1 單調(diào)性指標(biāo)

本文算法為了解決k-shell方法劃分結(jié)果粗?；瘑栴}，使網(wǎng)絡(luò)中的節(jié)點(diǎn)盡可能分配單一排序等級，排序相同值的節(jié)點(diǎn)少，單調(diào)性指標(biāo)值越大。采用文獻(xiàn)［11］中方法評價不同排序方法的單調(diào)性。Monotonicity定義如下：

其中Rr為排序等級列表，n為排序結(jié)果中元素?cái)?shù)目，nr為相同等級節(jié)點(diǎn)數(shù)目。為簡化計(jì)算，Rc為劃分到相同等級中節(jié)點(diǎn)個數(shù)非1的列表，該指標(biāo)公式用于衡量排序結(jié)果中相同值所占列表比例。

4.1.2 相關(guān)性指標(biāo)

本文使用SIR傳播模型獲得標(biāo)準(zhǔn)排序結(jié)果，N個節(jié)點(diǎn)的狀態(tài)可分為三類。

1）S：易染狀態(tài)，初始條件下所有節(jié)點(diǎn)均為易染狀態(tài)，該節(jié)點(diǎn)以β的概率被鄰居節(jié)點(diǎn)感染；

2）I：感染狀態(tài)，感染某種病毒作為傳染源的節(jié)點(diǎn)，該個體以β概率感染其鄰居節(jié)點(diǎn)；

3）R：移除狀態(tài)，也成免疫狀態(tài)或恢復(fù)狀態(tài)，感染狀態(tài)節(jié)點(diǎn)以β概率感染鄰居易感節(jié)點(diǎn)后，以γ概率變?yōu)镽移除狀態(tài)，不再具有感染能力和易感特性；

使用Kendall相關(guān)系數(shù)τ計(jì)算兩個排序序列l(wèi)ist1和list2之間的相似性，定義如下：

其中，nc表示兩個序列中同序?qū)Φ膫€數(shù)，nd表示兩個序列中異序?qū)Φ膫€數(shù)，n表示排序序列列表的長度。τ值越大，兩個列表之間相似性越大。

例：list1=｛1，2，3，4｝，list2=｛1，3，2，4｝。

表1 list1與list2二元組集合

4.2 仿真實(shí)驗(yàn)

根據(jù)上述分析，為了驗(yàn)證本文提出方法的有效性及準(zhǔn)確性，設(shè)計(jì)兩組對比實(shí)驗(yàn)，在六個網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，并與Ks、Cnc+、EKsd、DK算法指標(biāo)進(jìn)行對比分析，比較算法排序結(jié)果單調(diào)性；使用SIR傳播模型計(jì)算標(biāo)準(zhǔn)排序結(jié)果，計(jì)算各中心性算法與SIR的Kendallτ相關(guān)系數(shù)；比較熵權(quán)法、灰色關(guān)聯(lián)度分析法確定權(quán)重的計(jì)算方法的差異。具體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)統(tǒng)計(jì)特征如表2所示。

表2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)統(tǒng)計(jì)特征

littlecase為一個案例網(wǎng)絡(luò)，karaze［20］是具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)，由美國一所大學(xué)的空手道俱樂部成員組成的關(guān)系網(wǎng)；911terriset［21］網(wǎng)絡(luò)是恐怖襲擊網(wǎng)絡(luò)，每個節(jié)點(diǎn)代表一名恐怖分子，節(jié)點(diǎn)之間的邊代表恐怖分子之間的聯(lián)系；netScience［22］是科學(xué)家合作網(wǎng)絡(luò)，網(wǎng)絡(luò)代表科學(xué)家之間的合作關(guān)系，本文選取網(wǎng)絡(luò)中的極大連通子圖；Email［23］網(wǎng)絡(luò)是電子郵件收發(fā)網(wǎng)絡(luò)，聯(lián)系人之間發(fā)送過郵件產(chǎn)生一條邊；Blogs［23］網(wǎng)絡(luò)是MSN上的博客網(wǎng)絡(luò)，當(dāng)一個人在另外一個人的博客有評論時，產(chǎn)生一條邊。上述網(wǎng)絡(luò)均按照無向無權(quán)網(wǎng)絡(luò)處理，＜k＞表示網(wǎng)絡(luò)平均度，即網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的平均值，kmax表示節(jié)點(diǎn)最大度，＜d＞表示網(wǎng)絡(luò)節(jié)點(diǎn)間最短路徑平均數(shù)，C表示聚類系數(shù)，用來評估節(jié)點(diǎn)聚集成團(tuán)的集聚程度；R表示同配系數(shù)，用來反映鄰接節(jié)點(diǎn)間的度相關(guān)性；H表示異質(zhì)系數(shù)，衡量網(wǎng)絡(luò)中節(jié)點(diǎn)度分布的異質(zhì)［24～25］。β表示SIR傳播模型中的感染概率。

表3展示了ks、Cnc+、EKsd、DK及本文提出的兩種確定權(quán)重方法GDI和EDI分別在上述六個數(shù)據(jù)集仿真實(shí)驗(yàn)進(jìn)行關(guān)鍵節(jié)點(diǎn)識別，排序結(jié)果的單調(diào)性分析，由表可知，k-shell方法在三個數(shù)據(jù)集上的單調(diào)性驗(yàn)證結(jié)果均是最差，存在粗?；瘎澐謫栴}。本文提出的使用到最大核節(jié)點(diǎn)的距離改進(jìn)迭代次數(shù)，兩種權(quán)重賦予方式提出的GDI、EDI方法單調(diào)性驗(yàn)證結(jié)果排名Top2，且GDI單調(diào)性優(yōu)于EDI。說明兩種賦予權(quán)重的方法均能夠有效地解決k-shell劃分結(jié)果粗?；膯栴}，使得更多的節(jié)點(diǎn)被劃分到不同的等級。

表3 不同度量節(jié)點(diǎn)單調(diào)性分析表

表4展示了ks、Cnc+、EKsd、DK、GDI和EDI算法分別在六個數(shù)據(jù)集的關(guān)鍵節(jié)點(diǎn)識別結(jié)果，與SIR仿真?zhèn)鞑ゴ_定節(jié)點(diǎn)傳播能力的節(jié)點(diǎn)重要性之間的相關(guān)性，通過數(shù)學(xué)計(jì)量Kendall相關(guān)系數(shù)體現(xiàn)相關(guān)性差異，本文算法EDI在六個數(shù)據(jù)集上均與SIR傳播模型相關(guān)系數(shù)值最大，相關(guān)性最強(qiáng)，最貼近標(biāo)準(zhǔn)排序結(jié)果。EDI算法在DK算法基礎(chǔ)上考慮節(jié)點(diǎn)到最大核節(jié)點(diǎn)的平均距離，改進(jìn)K核迭代次數(shù)，使用熵權(quán)法確定權(quán)重，在上述六個數(shù)據(jù)集中，單調(diào)性和有效性均優(yōu)于其他算法。GDI算法使用灰色關(guān)聯(lián)度分析法確定權(quán)重進(jìn)而計(jì)算節(jié)點(diǎn)重要性指標(biāo)，但是從表4算法有效性中看出，該方法在部分?jǐn)?shù)據(jù)集上優(yōu)于相同貢獻(xiàn)度的EKsd算法、熵權(quán)法確定權(quán)重的DK算法，如karate數(shù)據(jù)集、net Science數(shù)據(jù)集，在部分?jǐn)?shù)據(jù)集上與SIR傳播模型標(biāo)準(zhǔn)排序差異很大，如Blogs網(wǎng)絡(luò)。因?yàn)樵谑褂没疑P(guān)聯(lián)度分析法確定權(quán)重時，對于所有網(wǎng)絡(luò)人為主觀決定分辨系數(shù)ρ取定值0.5，取值的不同會最終影響權(quán)重的分配，使得算法可信度降低。所以采用熵權(quán)法確定權(quán)重可以更有效地進(jìn)行關(guān)鍵節(jié)點(diǎn)識別。

表4 不同度量指標(biāo)相關(guān)性分析表

5 結(jié)語

本文算法主要解決復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識別問題中，k-shell識別方法帶來的粗?；瘎澐謫栴}，融合網(wǎng)絡(luò)局部信息和全局信息，更全面地識別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，通過節(jié)點(diǎn)到最大核距離改進(jìn)K核迭代次數(shù)、融合節(jié)點(diǎn)度，使用熵權(quán)法確定權(quán)重，結(jié)合鄰居節(jié)點(diǎn)的貢獻(xiàn)，更有效地識別無向無權(quán)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。實(shí)驗(yàn)證明，GDI算法雖然在單調(diào)性方面明顯優(yōu)于其他方法，但EDI算法在有效性上明顯優(yōu)于其他方法，能夠以較高精度識別出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。下一步計(jì)劃將點(diǎn)權(quán)強(qiáng)度融合到本文算法擴(kuò)展到加權(quán)網(wǎng)絡(luò)，進(jìn)一步對灰色關(guān)聯(lián)度分析方法中的參數(shù)ρ進(jìn)行深入研究。