復(fù)雜網(wǎng)絡(luò)中的一種介度熵抗毀性度量方法

張 昕，郭 陽

遼寧大學(xué) 信息學(xué)院，沈陽110036

1 引言

隨著信息技術(shù)的發(fā)展復(fù)雜網(wǎng)絡(luò)已經(jīng)深入到人類社會(huì)的各個(gè)方面，如社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)與互聯(lián)網(wǎng)、物網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、經(jīng)濟(jì)與金融網(wǎng)絡(luò)等。而網(wǎng)絡(luò)時(shí)刻遭受著來自不同方面的、不同程度的、蓄意或無意的攻擊，這就需要對(duì)網(wǎng)絡(luò)進(jìn)行抗毀性分析[1]，合理地衡量整個(gè)網(wǎng)絡(luò)抵御攻擊的能力，從而得到更有針對(duì)性地部署防范策略，有效地減少攻擊損失。所以，復(fù)雜網(wǎng)絡(luò)中的抗毀性[2]研究具有重要的理論價(jià)值和應(yīng)用價(jià)值?，F(xiàn)有的相關(guān)研究主要從三個(gè)方面進(jìn)行[3]：一是基于圖論的抗毀性研究，如粘連度、完整度、膨脹系數(shù)、核度等，考量了整個(gè)網(wǎng)絡(luò)的抗毀性；二是基于解析的抗毀性研究，是采用渝滲理論將隨機(jī)圖中研究的問題滲流變換后進(jìn)行分析研究；三是基于仿真的抗毀性研究，主要是對(duì)隨機(jī)網(wǎng)絡(luò)模型[4]和無標(biāo)度網(wǎng)絡(luò)模型[5-6]采用不同類型的攻擊策略進(jìn)行攻擊后，對(duì)其拓?fù)浣Y(jié)構(gòu)的變化進(jìn)行研究?？紤]到在復(fù)雜網(wǎng)絡(luò)中，核心節(jié)點(diǎn)一旦遭到攻擊，有可能產(chǎn)生嚴(yán)重后果，甚至摧毀整個(gè)網(wǎng)絡(luò)，因此本文從基于節(jié)點(diǎn)重要性[7]方面進(jìn)行考量，研究復(fù)雜網(wǎng)絡(luò)的抗毀性。本文結(jié)合多種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，重新定義了節(jié)點(diǎn)重要性評(píng)估指標(biāo)，提出了基于局部的介-度中心性指標(biāo)，進(jìn)而構(gòu)建出介-度熵測(cè)度模型，提出衡量網(wǎng)絡(luò)抗毀性的介-度熵算法。仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的攻擊策略相比較，本文提出的介-度中心性攻擊策略破壞網(wǎng)絡(luò)的能力更強(qiáng)，由此可知本文提出的基于局部的介-度中心性指標(biāo)及介-度熵度量方法可以更好地衡量和評(píng)估網(wǎng)絡(luò)的抗毀性。

2 相關(guān)工作

在復(fù)雜網(wǎng)絡(luò)中，網(wǎng)絡(luò)的生產(chǎn)性為隨機(jī)性故障發(fā)生后其仍可以正常工作的能力；網(wǎng)絡(luò)的可靠性為網(wǎng)絡(luò)被攻擊后其自身糾錯(cuò)并正常工作的能力。網(wǎng)絡(luò)的隨機(jī)性攻擊會(huì)影響網(wǎng)絡(luò)的生產(chǎn)性，而選擇性攻擊則會(huì)影響網(wǎng)絡(luò)的可靠性。目前，網(wǎng)絡(luò)的抗毀性能研究主要集中在對(duì)已知的確定性的網(wǎng)絡(luò)進(jìn)行選擇性攻擊，從而評(píng)估網(wǎng)絡(luò)的可靠性。但在實(shí)際中對(duì)于網(wǎng)絡(luò)的損害也有可能是其自身因素所造成的。

目前，許多研究人員從不同角度提出了抗毀性測(cè)度模型，確定了網(wǎng)絡(luò)抗毀性度量，并量化分析了網(wǎng)絡(luò)抗毀性。文獻(xiàn)[8]中利用節(jié)點(diǎn)度值的大小對(duì)隨機(jī)網(wǎng)絡(luò)的魯棒性和脆弱性進(jìn)行了評(píng)估和分析；文獻(xiàn)[9]在有權(quán)網(wǎng)絡(luò)中利用邊的數(shù)量及權(quán)值的大小評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度，進(jìn)而構(gòu)建網(wǎng)絡(luò)抗毀模型；文獻(xiàn)[10]中分析了節(jié)點(diǎn)的介數(shù)中心性對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要程度的影響；文獻(xiàn)[11]提出了刪除網(wǎng)絡(luò)中節(jié)點(diǎn)后最短路徑變化的評(píng)估方法；文獻(xiàn)[12]中提出了針對(duì)無標(biāo)度網(wǎng)絡(luò)模型的抗毀性測(cè)度分析；文獻(xiàn)[13]分別從節(jié)點(diǎn)重要性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化方面對(duì)網(wǎng)絡(luò)的抗毀性的影響進(jìn)行了研究；文獻(xiàn)[14]研究了拓?fù)浣Y(jié)構(gòu)確定的加權(quán)復(fù)雜網(wǎng)路的抗毀性；文獻(xiàn)[15]采用基于平均連通度及粘聚度的抗毀性測(cè)度方法評(píng)估了賦權(quán)網(wǎng)絡(luò)的抗毀性。

在基于節(jié)點(diǎn)重要性的抗毀性測(cè)度研究中，文獻(xiàn)[8]雖然是最簡單直接的方式，但該方式并不全面；文獻(xiàn)[9]局限于有權(quán)網(wǎng)絡(luò)；文獻(xiàn)[10]需要考慮網(wǎng)絡(luò)自身的拓?fù)浣Y(jié)構(gòu)；文獻(xiàn)[11]在網(wǎng)絡(luò)遭受選擇性攻擊后分析了網(wǎng)絡(luò)的連通性，但未考慮網(wǎng)絡(luò)中最短路徑的改變對(duì)節(jié)點(diǎn)重要性的影響。在基于鏈路的抗毀性測(cè)度研究中，文獻(xiàn)[12]中當(dāng)隨機(jī)對(duì)網(wǎng)絡(luò)中的鏈路進(jìn)行刪除時(shí)，有可能會(huì)破壞無標(biāo)度網(wǎng)絡(luò)的原有特性。文獻(xiàn)[13]中衡量節(jié)點(diǎn)重要性主要采用節(jié)點(diǎn)的度分布，未結(jié)合節(jié)點(diǎn)其他重要性指標(biāo)來進(jìn)行抗毀性研究；文獻(xiàn)[14]的研究無法適用于拓?fù)浣Y(jié)構(gòu)不確定的網(wǎng)絡(luò)。

目前研究者們對(duì)節(jié)點(diǎn)的重要性評(píng)估主要采用全局中心性度量方法，如度中心性、介數(shù)中心性等。基于局部的節(jié)點(diǎn)重要性度量方法較少，已有的局部介數(shù)中心性[16]度量方法，是將節(jié)點(diǎn)的介數(shù)中心性的求解范圍從全局轉(zhuǎn)變?yōu)榧s束在k步內(nèi)進(jìn)行求解。在現(xiàn)實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性需要從多方面進(jìn)行考量，節(jié)點(diǎn)的度中心性和介數(shù)中心性雖然都可以在某種程度上反映出一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度，而且介數(shù)較高的節(jié)點(diǎn)的度值一般也比較高，但節(jié)點(diǎn)的度值和介數(shù)的關(guān)聯(lián)程度并不高，所以可以對(duì)節(jié)點(diǎn)的度值和介數(shù)進(jìn)行綜合考量，得到節(jié)點(diǎn)重要性的衡量指標(biāo)，可以更好地對(duì)節(jié)點(diǎn)的重要性進(jìn)行評(píng)估。因此，本文對(duì)節(jié)點(diǎn)的局部介數(shù)中心性和度中心性進(jìn)行了綜合考量，提出介-度中心性指標(biāo)（Betweenness-Degree Centrality，K-BDC），用以評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要程度。同時(shí)兼顧聚集系數(shù)對(duì)節(jié)點(diǎn)重要程度的影響，進(jìn)一步給出節(jié)點(diǎn)的抗毀性指標(biāo)，并構(gòu)建介-度熵度量，進(jìn)而提出介-度熵（Betweenness-Degree Entropy，BDE）算法，衡量整個(gè)網(wǎng)絡(luò)的抗攻擊能力。

3 介-度中心性指標(biāo)

在對(duì)計(jì)算機(jī)抗干擾性進(jìn)行分析時(shí)，需要計(jì)算所有節(jié)點(diǎn)對(duì)之間的最短路徑，計(jì)算復(fù)雜度較高，故而本文在Brandes[17]針對(duì)全局介數(shù)中心性算法基礎(chǔ)上，引入最長距離約束k，將全局節(jié)點(diǎn)對(duì)之間的最短路徑求解轉(zhuǎn)化為k步內(nèi)最短路徑求解，縮小了求解最短路徑的規(guī)模，提升了計(jì)算效率。并綜合考慮節(jié)點(diǎn)的介數(shù)中心性與節(jié)點(diǎn)的度中心性，定義了基于局部的介-度中心性指標(biāo)，用來衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性。

3.1 術(shù)語定義

復(fù)雜網(wǎng)絡(luò)可抽象為拓?fù)鋱D表示，記為圖G=(V,E)，其中V表示為節(jié)點(diǎn)的集合，E表示為連邊的集合。

定義1局部度相關(guān)系數(shù)：圖G中節(jié)點(diǎn)v的局部度相關(guān)系數(shù)是指在圖G所有長度不超過k(k＞1)的路徑中，節(jié)點(diǎn)v的度在每條路徑中占比值的總和，記為Tk(v)，其值由式（1）確定。

式中，dv表示節(jié)點(diǎn)v的度值，L(s,t|v)表示以節(jié)點(diǎn)s與節(jié)點(diǎn)t為兩端點(diǎn)并經(jīng)過節(jié)點(diǎn)v的路徑集合，l表示其中一條路徑。

定義2局部介-度中心性指標(biāo)：令p(v)表示圖G中通過節(jié)點(diǎn)v的所有長度不超過k的路徑條數(shù)，σ(s,t)表示從節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑數(shù)量，σ(s,t|v)表示從節(jié)點(diǎn)s通過節(jié)點(diǎn)v后到達(dá)節(jié)點(diǎn)t的最短路徑數(shù)量，則圖G中節(jié)點(diǎn)v的局部介-度中心性指標(biāo)Ck(v)值由式（2）確定。

3.2 合理性分析

對(duì)比節(jié)點(diǎn)的介數(shù)中心性度量方法，K-BDC指標(biāo)對(duì)節(jié)點(diǎn)的度值和介數(shù)進(jìn)行了綜合考量，從不同的角度綜合評(píng)估了節(jié)點(diǎn)的重要性。由于節(jié)點(diǎn)度值僅能體現(xiàn)鄰接節(jié)點(diǎn)數(shù)目，對(duì)節(jié)點(diǎn)重要程度的刻畫不足，因此本文提出局部度相關(guān)系數(shù)概念，考察節(jié)點(diǎn)度在多條路徑中的比重。在此基礎(chǔ)上結(jié)合節(jié)點(diǎn)介數(shù)，進(jìn)一步提出局部介-度中心性指標(biāo)，并考慮到度相關(guān)系數(shù)相比節(jié)點(diǎn)介數(shù)計(jì)算結(jié)果相差一個(gè)量級(jí)，因此引入局部路徑數(shù)目，使二者對(duì)局部介-度中心性指標(biāo)的影響更為均衡。

分別采用介數(shù)中心性及本文提出的介-度中心性指標(biāo)對(duì)圖1所示網(wǎng)絡(luò)中的節(jié)點(diǎn)中心性進(jìn)行求解，所得結(jié)果見表1。

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

表1 不同中心性度量方法求得的節(jié)點(diǎn)中心性對(duì)比

由表1可以看出，圖1中節(jié)點(diǎn)1、2、3的介數(shù)中心性的值相同，表明這3個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度相同，若對(duì)該網(wǎng)絡(luò)進(jìn)行蓄意攻擊[18]，當(dāng)節(jié)點(diǎn)1、2、3失效后，剩余節(jié)點(diǎn)之間不再存在連邊，網(wǎng)絡(luò)完全癱瘓。而圖1中節(jié)點(diǎn)2、3的介-度中心性的值相同，當(dāng)這2個(gè)節(jié)點(diǎn)失效后，即可使整個(gè)網(wǎng)絡(luò)癱瘓。由該對(duì)比操作結(jié)果可知，本文定義的介-度中心性指標(biāo)在網(wǎng)絡(luò)抗毀性上對(duì)節(jié)點(diǎn)重要性的刻畫準(zhǔn)確程度高于介數(shù)中心性度量方法。同時(shí)，也說明本文提出的局部介-度中心性雖然是通過最長距離約束k對(duì)介數(shù)中心性進(jìn)行了近似計(jì)算，但求得的節(jié)點(diǎn)重要性排序結(jié)果依然合理有效。由于在求解時(shí)有效地約束了路徑長度，使得其在大規(guī)模網(wǎng)絡(luò)上的運(yùn)行效率得到了較大的提升。

4 介-度熵度量及算法

在復(fù)雜網(wǎng)絡(luò)中，處于關(guān)鍵位置的核心節(jié)點(diǎn)通常具有信息傳輸量大、信息交換頻繁等特點(diǎn)。所以核心節(jié)點(diǎn)的損壞可能會(huì)影響到整個(gè)網(wǎng)絡(luò)的穩(wěn)定性。故而本文基于節(jié)點(diǎn)重要性相關(guān)研究構(gòu)建網(wǎng)絡(luò)抗毀性測(cè)度模型。結(jié)合已提出的節(jié)點(diǎn)介-度中心性指標(biāo)，提出節(jié)點(diǎn)抗毀性指標(biāo)。進(jìn)而提出介-度熵（BDE）度量方法，并進(jìn)一步給出BDE算法及其時(shí)間復(fù)雜度分析。

4.1 術(shù)語定義

在圖論中，聚集系數(shù)通常用于刻畫圖中節(jié)點(diǎn)聚集成團(tuán)的程度，即衡量圖中一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間相互連接的緊密程度，節(jié)點(diǎn)在網(wǎng)絡(luò)中越靠近核心位置，其鄰居節(jié)點(diǎn)之間存在連邊的可能性就越大，節(jié)點(diǎn)就越可能具有較高的度值和聚集系數(shù)，聚集系數(shù)在一定程度上刻畫出節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置，而核心節(jié)點(diǎn)一般距離網(wǎng)絡(luò)的中心位置較近，其聚集系數(shù)也較高，所以采用聚集系數(shù)可以更全面地描述節(jié)點(diǎn)的重要性。因而可以通過介-度中心性指標(biāo)和聚集系數(shù)對(duì)節(jié)點(diǎn)的重要性進(jìn)行綜合考量，以期得到的更符合現(xiàn)實(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)抗毀性指標(biāo)。

定義3節(jié)點(diǎn)抗毀性：是指網(wǎng)絡(luò)中節(jié)點(diǎn)v的毀壞與整個(gè)網(wǎng)絡(luò)毀壞的關(guān)聯(lián)程度，記為S(v)，其值越大，則該節(jié)點(diǎn)的毀壞越易導(dǎo)致整個(gè)網(wǎng)絡(luò)的毀壞。計(jì)算方法如式（3）所示，其中CLv表示節(jié)點(diǎn)v的聚集系數(shù)，Ck(v)為節(jié)點(diǎn)v的局部介-度中心性指標(biāo)。

節(jié)點(diǎn)的抗毀性指標(biāo)的準(zhǔn)確性與最長距離約束k的取值直接相關(guān)，為了準(zhǔn)確地刻畫出節(jié)點(diǎn)v在局部范圍內(nèi)的介數(shù)中心性，最大距離約束k隨著網(wǎng)絡(luò)的規(guī)模增加而增大。而現(xiàn)實(shí)網(wǎng)絡(luò)具有小世界性質(zhì)，通過實(shí)驗(yàn)分析和理論依據(jù)，在網(wǎng)絡(luò)規(guī)模較大時(shí)，取k=6是一個(gè)可以取得較準(zhǔn)確計(jì)算結(jié)果的值。隨著k值的取值增大，由最大距離約束k所確定的局部范圍也會(huì)隨之增加，直到k增大到某一閾值時(shí)，節(jié)點(diǎn)v的局部介數(shù)中心性計(jì)算會(huì)退化為對(duì)全局介數(shù)中心性的計(jì)算。以v為局部中心點(diǎn)的局部最短路徑求解范圍也會(huì)轉(zhuǎn)化為對(duì)網(wǎng)絡(luò)全局最短路徑的計(jì)算。節(jié)點(diǎn)抗毀性指標(biāo)體現(xiàn)出網(wǎng)絡(luò)中的單個(gè)節(jié)點(diǎn)抵御攻擊能力的強(qiáng)弱，在此基礎(chǔ)上可以定義網(wǎng)絡(luò)抗毀性度量，衡量整個(gè)網(wǎng)絡(luò)的抗打擊能力。

定義4介-度熵度量：通過對(duì)節(jié)點(diǎn)抗毀性分布的差異性進(jìn)行評(píng)估，衡量整個(gè)網(wǎng)絡(luò)的抗打擊能力，記作BDE。介-度熵度量結(jié)果與網(wǎng)絡(luò)的抗毀性能成正比，與節(jié)點(diǎn)間抗毀性分布成反比。即節(jié)點(diǎn)間抗毀性分布差異越小，網(wǎng)絡(luò)抵御選擇性攻擊的能力越強(qiáng)，介-度熵度量值越大。反之亦然。計(jì)算方法如式（4）所示：

該度量表明節(jié)點(diǎn)抗毀性分布情況對(duì)網(wǎng)絡(luò)抵御選擇性攻擊能力強(qiáng)弱的影響。綜合考察了節(jié)點(diǎn)的度、局部介數(shù)中心性、聚集系數(shù)對(duì)網(wǎng)絡(luò)抗毀性能的影響，得到較全面的網(wǎng)絡(luò)的抗毀性度量結(jié)果。

4.2 BDE算法

本節(jié)給出計(jì)算節(jié)點(diǎn)抗毀性指標(biāo)與介-度熵度量的BDE算法，該算法有2個(gè)輸入?yún)?shù)，分別為網(wǎng)絡(luò)G和最長距離約束k。通常來說，最長距離約束k與網(wǎng)絡(luò)G的規(guī)模具有一定相關(guān)性，可根據(jù)具體輸入網(wǎng)絡(luò)酌情定值。在算法形式化描述中，Node[s-t]為從節(jié)點(diǎn)s出發(fā)到節(jié)點(diǎn)t，所經(jīng)過的節(jié)點(diǎn)集合；Degree[s-t]為從節(jié)點(diǎn)s出發(fā)到節(jié)點(diǎn)t，所經(jīng)過節(jié)點(diǎn)的度值總和。

算法形式化描述如下：

步驟1 START

1.FileOpen(G.edges)

2. FileRead(&u,&v)；

3. Matrix[u][v]=Matrix[v][u]=1；

4. Degree[u]++；

5. Degree[v]++；

6.For(i＜G.nodes)

7.If(Degree[i]＞1)

8. 計(jì)算各節(jié)點(diǎn)的聚集系數(shù)CL[s]

步驟1 FINISH

步驟1讀入圖G的數(shù)據(jù)文件，將其存入鄰接矩陣中，并計(jì)算每個(gè)節(jié)點(diǎn)的度值，同時(shí)得到度值大于1的節(jié)點(diǎn)的聚集系數(shù)。其中Matrix[N][N]為鄰接矩陣，用來保存圖G的節(jié)點(diǎn)信息，Degree[N]用來保存節(jié)點(diǎn)的度信息，CL[s]用來保存節(jié)點(diǎn)的聚集系數(shù)。

步驟2 STRAT

9. BFS(s) s∈V

10. Node[s]←s；

11.If dist[t]＜=k

12. Node[s]←t,Q←t

13. If(!Pred Map.containsKey(Node[s-t]))

14. Pred Map.key=Node[s-t]

15. Pred Map.value=Degree[s-t]；

16. σ[s]++；

17. t[s]+=Degree[s]/Degree[s-t]；

步驟2 FINISH

步驟2求解度相關(guān)系數(shù)。采用Map結(jié)構(gòu)存儲(chǔ)節(jié)點(diǎn)的路徑及路徑上節(jié)點(diǎn)的度值總和。其中key為節(jié)點(diǎn)的路徑Node[s-t],value為路徑上的節(jié)點(diǎn)度值總和Degree[s-t]。dist[t]表示從節(jié)點(diǎn)s到節(jié)點(diǎn)t之間的最短路徑；Q為滿足最長距離約束k的隊(duì)列；σ[s]表示記錄從節(jié)點(diǎn)s開始遍歷的滿足最長距離約束k的路徑條數(shù)；t[s]表示節(jié)點(diǎn)s在整條路徑中節(jié)點(diǎn)度所占比值。

步驟3 START

18. While(!Q.Empty())

19. 出隊(duì)列w←Q；入棧S←w；

20. GOTO步驟2

21. If Node[w-v]∈Node[s]&&s∈Node[w-v]

22. σ[s]++；

23. t[s]+=Degree[s]/Degree[w-v]；

24. If dist[w]=∞∩Exist(dist[w-v])

25. dist[w]←dist[v]+1；

26. If dist[w]＜k&&(!Q.contains(w))

27. 入隊(duì)列Q←w；

28. If dist[w]=dist[v]+1

29. σ[w]←σ[w]+ω(s,w)?σ[v]；

30. Pred[w]←v；

31.For v∈V

32. δ[v]←0；

33.While(!S.Empty())

34. 出棧w←S；

35. For v∈Pred[w]

36. δ[v]←σ[v]/σ[w]?((1+δ[w])；

37. If w≠s Then

38. C(w)+=δ[w]；

39. Ck(s)=t[s]/σ[s]?C(s)；

40. Ck+=Ck(s)；

步驟3 FINISH

步驟3利用網(wǎng)絡(luò)中前置節(jié)點(diǎn)的點(diǎn)對(duì)依賴求解節(jié)點(diǎn)的介-度中心性。其中ω(s,w)表示從節(jié)點(diǎn)s到節(jié)點(diǎn)w之間的路徑的條數(shù)。其中序號(hào)18～20為初始化Q中節(jié)點(diǎn)信息；序號(hào)21～23為計(jì)算節(jié)點(diǎn)s在整條路徑中節(jié)點(diǎn)度所占比值；序號(hào)24～30為求得s和w的中繼節(jié)點(diǎn)v及從s經(jīng)過v再到w的最短路徑條數(shù)；序號(hào)31～40依據(jù)最短路徑個(gè)數(shù)計(jì)算點(diǎn)對(duì)依賴，進(jìn)而獲得局部介-度中心性的值。

步驟4 START

41. BFS(s) s∈V

42. S(s)=CL[s]*Ck(s)/Ck；

43. E+=(-S(s)ln S(s))；

44. return S,E；

步驟4 FINISH

步驟4計(jì)算整個(gè)網(wǎng)絡(luò)的介-度熵值。由求解得到的節(jié)點(diǎn)的聚集系數(shù)及介-度中心性，推導(dǎo)出節(jié)點(diǎn)的抗毀度，進(jìn)而求得整個(gè)網(wǎng)絡(luò)的介-度熵值。

在BDE算法中，計(jì)算節(jié)點(diǎn)的度相關(guān)系數(shù)由于引入最長距離約束k，使得其計(jì)算的時(shí)間復(fù)雜度近似接近于O(n2)，局部介-度中心性指標(biāo)的時(shí)間復(fù)雜度由于將全局介數(shù)中心性計(jì)算轉(zhuǎn)化為局部介數(shù)中心性計(jì)算，節(jié)點(diǎn)數(shù)量遠(yuǎn)遠(yuǎn)小于整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量，可以快速計(jì)算出局部的介數(shù)中心性。所以，局部介-度中心性指標(biāo)的時(shí)間復(fù)雜度近似接近于O(n2)。從而可以得出BDE算法的時(shí)間復(fù)雜度根據(jù)最長距離約束k的選擇會(huì)有一定的差異，當(dāng)k選擇為常量時(shí)，BDE算法的時(shí)間復(fù)雜度不超過O(n2)。

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

采用具有無標(biāo)度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)特性的生成網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量分別為200和5 000，通過對(duì)節(jié)點(diǎn)攻擊（在網(wǎng)絡(luò)中去除節(jié)點(diǎn)）后網(wǎng)絡(luò)連通程度的變化情況進(jìn)行研究，得到網(wǎng)絡(luò)在不同攻擊策略下的抗毀性能。實(shí)驗(yàn)中采用隨機(jī)攻擊和蓄意攻擊方式去除仿真網(wǎng)絡(luò)中的節(jié)點(diǎn)，其中蓄意攻擊方式采取基于度中心性優(yōu)先攻擊、基于介數(shù)中心性優(yōu)先攻擊以及基于介-度中心性優(yōu)先攻擊三種攻擊策略。分別對(duì)比不同的網(wǎng)絡(luò)規(guī)模及攻擊策略下仿真網(wǎng)絡(luò)所表現(xiàn)出的抗毀性差異。一般來說，對(duì)于規(guī)模較小的網(wǎng)絡(luò)選擇以去除的節(jié)點(diǎn)個(gè)數(shù)為研究對(duì)象，可采用最大連通子圖；對(duì)于規(guī)模較大的網(wǎng)絡(luò)選擇以去除節(jié)點(diǎn)的比例為研究對(duì)象，可采用平均反測(cè)地線距離。因此，本文采用上述兩種指標(biāo)作為評(píng)估不同規(guī)模網(wǎng)絡(luò)連通程度的度量。

然后生成節(jié)點(diǎn)數(shù)量分別為30和5 000，且連接概率不同的模擬網(wǎng)絡(luò)進(jìn)行抗毀性評(píng)估，通過對(duì)比不同網(wǎng)絡(luò)的介-度熵度量與網(wǎng)絡(luò)的實(shí)際抗毀性，論證該度量的合理性。

5.1 節(jié)點(diǎn)數(shù)為200的網(wǎng)絡(luò)仿真實(shí)驗(yàn)

在網(wǎng)絡(luò)中，連通子圖表示其內(nèi)部任意兩個(gè)節(jié)點(diǎn)之間都存在相連路徑的圖；非連通子圖則表示其內(nèi)部存在兩個(gè)或以上節(jié)點(diǎn)之間無相連路徑的圖。在圖中具有最多節(jié)點(diǎn)的連通子圖稱為最大連通子圖。在一個(gè)連通的網(wǎng)絡(luò)中，網(wǎng)絡(luò)的結(jié)構(gòu)隨著節(jié)點(diǎn)的變化而不斷改變，連通子圖有可能分裂為多個(gè)子圖或者合并成一個(gè)子圖。采用最大連通子圖對(duì)網(wǎng)絡(luò)連通程度的進(jìn)行度量，可以有效說明網(wǎng)絡(luò)受損的程度。

分別生成節(jié)點(diǎn)數(shù)量為200的2個(gè)具有不同網(wǎng)絡(luò)特性仿真網(wǎng)絡(luò)。具有小世界網(wǎng)絡(luò)特性的生成網(wǎng)絡(luò)的節(jié)點(diǎn)度值分布相對(duì)比較均勻，而具有無標(biāo)度特性的生成網(wǎng)絡(luò)的節(jié)點(diǎn)度值隨機(jī)性較大，且網(wǎng)絡(luò)中小部分節(jié)點(diǎn)具有較高的度值。在無標(biāo)度網(wǎng)絡(luò)中度值為1的節(jié)點(diǎn)比重較大，而在小世界網(wǎng)絡(luò)中度值為4的節(jié)點(diǎn)比重較大。實(shí)驗(yàn)中計(jì)算局部介-度中心性指標(biāo)時(shí)，考慮實(shí)驗(yàn)網(wǎng)絡(luò)規(guī)模，令局部性約束k=5。圖2展現(xiàn)了基于隨機(jī)性攻擊、度中心性優(yōu)先攻擊、介數(shù)中心性優(yōu)先攻擊以及介-度中心性優(yōu)先攻擊4種攻擊策略時(shí)網(wǎng)絡(luò)受損情況對(duì)比，并以網(wǎng)絡(luò)最大連通子圖的規(guī)模為衡量標(biāo)準(zhǔn)。

從圖2（a）中可以看出，在隨機(jī)攻擊模式下，無標(biāo)度網(wǎng)絡(luò)中的最大連通子圖中節(jié)點(diǎn)的數(shù)量隨著節(jié)點(diǎn)的不斷移除以線性的方式逐漸遞減，直到移除節(jié)點(diǎn)的個(gè)數(shù)接近節(jié)點(diǎn)總數(shù)時(shí)才降為0；在蓄意攻擊模式下，基于度中心性的攻擊策略在移除大約50個(gè)節(jié)點(diǎn)時(shí)，最大連通子圖中節(jié)點(diǎn)的數(shù)量接近于0，此時(shí)網(wǎng)絡(luò)中只存在孤立節(jié)點(diǎn)；基于介數(shù)中心性的攻擊策略與基于本文介-度中心性的攻擊策略在移除大約40個(gè)節(jié)點(diǎn)時(shí)，最大連通子圖中節(jié)點(diǎn)的數(shù)量即趨向于0。但從兩個(gè)攻擊策略的對(duì)比曲線可以看出，基于本文介-度中心性的攻擊策略下降得略快。圖2（b）所示對(duì)比情況與圖2（a）類似，隨機(jī)攻擊的效果較差，而在蓄意攻擊模式下基于介-度中心性的策略效果最佳。由此可以得到結(jié)論，基于本文介-度中心性的攻擊策略要優(yōu)于基于度中心性和基于介數(shù)中心性的攻擊策略，對(duì)網(wǎng)絡(luò)的破壞性更強(qiáng)。

5.2 節(jié)點(diǎn)數(shù)為5 000的網(wǎng)絡(luò)仿真實(shí)驗(yàn)

節(jié)點(diǎn)之間的最短路徑為從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)經(jīng)過連邊最少的一條路徑，也稱為測(cè)地線。網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間最短距離的均值表明了節(jié)點(diǎn)的分散情況，稱為平均測(cè)地線距離，記作L，其計(jì)算方法如式（5）所示，其中dij表示節(jié)點(diǎn)之間的最短距離。

當(dāng)網(wǎng)絡(luò)不斷遭受選擇性攻擊時(shí)，整個(gè)網(wǎng)絡(luò)被逐步拆分為多個(gè)子網(wǎng)絡(luò)，導(dǎo)致平均路徑長度不斷擴(kuò)大。這時(shí)可以使用反測(cè)地線距離L-1描述網(wǎng)絡(luò)的平均最短路徑，當(dāng)L-1變?yōu)?時(shí)，則表明節(jié)點(diǎn)對(duì)之間不再存在相連路徑，此時(shí)網(wǎng)絡(luò)中的節(jié)點(diǎn)全部成為孤立節(jié)點(diǎn)，其計(jì)算方法如式（6）所示，其中若節(jié)點(diǎn)i和節(jié)點(diǎn)j之間不存在通路時(shí)1/dij=0。

圖2 最大連通度指標(biāo)下4種攻擊策略對(duì)比圖

分別生成節(jié)點(diǎn)數(shù)量均為5 000的無標(biāo)度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)，圖3展現(xiàn)了基于度中心性優(yōu)先攻擊、基于介數(shù)中心性優(yōu)先攻擊以及基于介-度中心性優(yōu)先攻擊三種攻擊策略時(shí)網(wǎng)絡(luò)受損情況對(duì)比，并以網(wǎng)絡(luò)平均反測(cè)地線距離為衡量標(biāo)準(zhǔn)。由于實(shí)驗(yàn)網(wǎng)絡(luò)規(guī)模較大，隨機(jī)攻擊效果極差，不必與其進(jìn)行對(duì)比，并令局部性約束k=6。

由圖3（a）中可知，平均反測(cè)地線距離的變化速率隨著節(jié)點(diǎn)的失效逐漸放緩，在基于度中心性的攻擊策略中，網(wǎng)絡(luò)的平均反測(cè)地線距離在移除大約整個(gè)網(wǎng)絡(luò)中25%的節(jié)點(diǎn)時(shí)變?yōu)?；在基于介數(shù)中心性的攻擊策略和基于本文介-度中心性的攻擊策略中，網(wǎng)絡(luò)的平均反測(cè)地線距離在移除整個(gè)網(wǎng)絡(luò)中20%的節(jié)點(diǎn)時(shí)開始趨向于0，但采用本文介-度中心性策略進(jìn)行攻擊的曲線比采用介數(shù)中心性策略進(jìn)行攻擊的曲線下降得略快，即網(wǎng)絡(luò)中節(jié)點(diǎn)全部成為孤立節(jié)點(diǎn)的速度略快于采用基于介數(shù)中心性的攻擊策略。由此可知，在無標(biāo)度網(wǎng)絡(luò)中，基于介-度中心性的攻擊策略對(duì)網(wǎng)絡(luò)的破壞能力高于基于度中心性及基于介數(shù)中心性的攻擊策略。

由圖3（b）可知，小世界網(wǎng)絡(luò)中的平均反測(cè)地線距離變化速率雖然也隨著節(jié)點(diǎn)的失效逐漸放緩，但其放緩速率要比在無標(biāo)度網(wǎng)絡(luò)中慢得多。采用基于度中心性的攻擊策略時(shí)，平均反測(cè)地線距離在移除整個(gè)網(wǎng)絡(luò)中大約60%的節(jié)點(diǎn)時(shí)變?yōu)?；采用基于介-度中心性的策略攻擊時(shí)，平均反測(cè)地線距離在移除整個(gè)網(wǎng)絡(luò)中大約50%的節(jié)點(diǎn)時(shí)就開始趨近0；而采用基于介數(shù)中心性攻擊策略進(jìn)行攻擊的曲線圖形介于基于度中心性攻擊策略和基于介-度中心性攻擊策略之間，靠近于基于本文提出的介-度中心性策略進(jìn)行攻擊的曲線?？傮w看來，對(duì)網(wǎng)絡(luò)進(jìn)行蓄意攻擊時(shí)，與采用基于度中心性和采用基于介數(shù)中心性的攻擊策略相比，采用本文提出的基于介-度中心性的攻擊策略在去除更少的節(jié)點(diǎn)時(shí)就使得網(wǎng)絡(luò)的平均反測(cè)地線距離趨向于0或成為0，表明其更容易對(duì)網(wǎng)絡(luò)造成損害，攻擊效果更明顯。

5.3 介-度熵度量實(shí)驗(yàn)

構(gòu)造不同規(guī)模以及不同連接概率的模擬網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)抗毀性測(cè)度及網(wǎng)絡(luò)介-度熵度量進(jìn)行分析，根據(jù)構(gòu)造時(shí)選取的隨機(jī)重連概率p不同，構(gòu)造出的網(wǎng)絡(luò)模型也將發(fā)生相應(yīng)的變化。當(dāng)p為0時(shí)，構(gòu)造出的網(wǎng)絡(luò)為規(guī)則網(wǎng)絡(luò)；隨著p值的不斷增大，網(wǎng)絡(luò)向小世界網(wǎng)絡(luò)演化，當(dāng)p增大至1時(shí)，構(gòu)造出的網(wǎng)絡(luò)即為隨機(jī)網(wǎng)絡(luò)。

將網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)分別設(shè)為30與5 000，節(jié)點(diǎn)平均度為6，對(duì)p分別取值為0.1、0.5和0.9，構(gòu)造出的3種仿真網(wǎng)絡(luò)中的節(jié)點(diǎn)的度分布情況如圖4所示。

分別針對(duì)節(jié)點(diǎn)個(gè)數(shù)為30（局部性約束k=4）和節(jié)點(diǎn)個(gè)數(shù)為5 000（局部性約束k=6）2種情況，計(jì)算對(duì)3類網(wǎng)絡(luò)進(jìn)行選擇性攻擊時(shí)網(wǎng)絡(luò)中的節(jié)點(diǎn)抗毀性和介-度熵，計(jì)算結(jié)果如表2所示。

圖3 平均反測(cè)地線距離指標(biāo)下3種攻擊策略對(duì)比圖

圖4 仿真網(wǎng)絡(luò)節(jié)點(diǎn)度分布圖

表2 仿真網(wǎng)絡(luò)節(jié)點(diǎn)抗毀性及介-度熵計(jì)算結(jié)果

由圖4（a）和圖4（b）可以看出，生成網(wǎng)絡(luò)的節(jié)點(diǎn)度值的隨機(jī)性與生成網(wǎng)絡(luò)的隨機(jī)重連概率p正相關(guān)，p值越大，節(jié)點(diǎn)度分布的差異性就越大。由于規(guī)則網(wǎng)絡(luò)中節(jié)點(diǎn)度分布最均勻，因此對(duì)其進(jìn)行選擇性攻擊時(shí)單個(gè)節(jié)點(diǎn)的毀壞對(duì)網(wǎng)絡(luò)的影響最小，抵抗破壞能力最強(qiáng)。而隨機(jī)網(wǎng)絡(luò)中節(jié)點(diǎn)度分布最不均勻，重要性較為突出個(gè)別核心節(jié)點(diǎn)一旦被毀壞將對(duì)網(wǎng)絡(luò)造成較大的影響，因此隨機(jī)網(wǎng)絡(luò)對(duì)選擇性攻擊的抵抗能力最弱。

由表2的對(duì)比結(jié)果可以看出，對(duì)3種網(wǎng)絡(luò)進(jìn)行選擇性攻擊時(shí)，其節(jié)點(diǎn)平均抗毀性關(guān)系：規(guī)則網(wǎng)絡(luò)＞小世界網(wǎng)絡(luò)＞隨機(jī)網(wǎng)絡(luò)，體現(xiàn)了網(wǎng)絡(luò)面對(duì)選擇性打擊時(shí)抗毀性能的強(qiáng)弱排序，而介-度熵度量得到了相同的對(duì)比結(jié)果。該對(duì)比排序結(jié)果符合圖4（a）和圖4（b）的對(duì)比分析，因此說明介-度熵度量是完全合理的。

首先對(duì)仿真生成網(wǎng)絡(luò)進(jìn)行仿真攻擊實(shí)驗(yàn)。通過分別對(duì)比3種不同攻擊策略下的實(shí)驗(yàn)結(jié)果，可以看出在對(duì)網(wǎng)絡(luò)進(jìn)行選擇性攻擊時(shí)，基于本文介-度中心性的攻擊策略大幅優(yōu)于基于度中心性的攻擊策略，且相對(duì)于基于介數(shù)中心性的攻擊策略也具有一定優(yōu)勢(shì)。對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)求取介數(shù)中心性時(shí)通常效率較低，而介-度中心性可以通過限制最長距離約束來進(jìn)行近似計(jì)算，提高了計(jì)算效率，更適合大規(guī)模網(wǎng)絡(luò)中的抗毀性分析。然后對(duì)規(guī)則網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)以及隨機(jī)網(wǎng)絡(luò)進(jìn)行抗毀性評(píng)估計(jì)算，結(jié)果表明本文提出的介-度熵度量能夠準(zhǔn)確評(píng)估大規(guī)模復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)抗毀性。

6 結(jié)束語

本文結(jié)合節(jié)點(diǎn)度值與節(jié)點(diǎn)介數(shù)，并通過限制最長距離約束考察其局部作用，提出了用于度量網(wǎng)絡(luò)中節(jié)點(diǎn)重要程度的局部介-度中心性指標(biāo)。在此基礎(chǔ)上提出了度量網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)對(duì)整體抗毀性影響能力大小的節(jié)點(diǎn)抗毀性指標(biāo)。進(jìn)而提出介-度熵度量，評(píng)估網(wǎng)絡(luò)抗毀性能的強(qiáng)弱，并給出了該度量的計(jì)算方法。仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的攻擊策略相比較，本文提出的介-度中心性的攻擊策略具有明顯優(yōu)勢(shì)，對(duì)網(wǎng)絡(luò)造成的破壞性更強(qiáng)，說明介-度中心性指標(biāo)在衡量節(jié)點(diǎn)重要性方面具有明顯優(yōu)勢(shì)。對(duì)規(guī)則網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)以及隨機(jī)網(wǎng)絡(luò)進(jìn)行抗毀性評(píng)估計(jì)算的結(jié)果表明，介-度熵度量是評(píng)估大規(guī)模復(fù)雜網(wǎng)絡(luò)抗毀性的合理度量。

本文主要基于無權(quán)網(wǎng)絡(luò)進(jìn)行抗毀性研究，而在現(xiàn)實(shí)網(wǎng)絡(luò)中，連邊通常存在多種權(quán)重，需要綜合考慮權(quán)重因素，以便獲得更準(zhǔn)確的網(wǎng)絡(luò)抗毀性度量結(jié)果。在未來的工作中需要依據(jù)實(shí)際應(yīng)用環(huán)境，綜合考慮各方面因素改進(jìn)介-度中心性指標(biāo)與介-度熵度量，使其具有更好的評(píng)估效果。