基于拓?fù)鋭莸木W(wǎng)絡(luò)毀傷最大算法

俞錦濤, 肖 兵, 熊家軍

(1. 空軍預(yù)警學(xué)院信息對(duì)抗系, 湖北 武漢 430019; 2. 空軍預(yù)警學(xué)院預(yù)警情報(bào)系, 湖北 武漢 430019)

0 引 言

隨著復(fù)雜網(wǎng)絡(luò)理論研究的不斷發(fā)展,其在實(shí)際生活中如交通網(wǎng)[1]、電網(wǎng)[2]、通信網(wǎng)[3]、城市綠色設(shè)施網(wǎng)絡(luò)[4]等領(lǐng)域的應(yīng)用也越來越廣泛。對(duì)于軍事作戰(zhàn)體系,也常借助復(fù)雜網(wǎng)絡(luò)這一工具來對(duì)體系中的實(shí)體進(jìn)行結(jié)構(gòu)和功能上的刻畫,描述實(shí)體在現(xiàn)實(shí)世界的具體行為,從而為優(yōu)化指揮控制的結(jié)構(gòu)提供相關(guān)參考[5]。軍事作戰(zhàn)體系包含了情報(bào)搜集處理、支援保障、指揮控制、打擊毀傷等不同功能的裝備,在體系網(wǎng)絡(luò)中具有不同的重要程度。為了更好地評(píng)價(jià)作戰(zhàn)體系的能力,無論從攻擊還是防御的角度來看,挖掘體系網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)都具有重要意義[6]:對(duì)攻擊方而言,知道關(guān)鍵節(jié)點(diǎn)可以實(shí)現(xiàn)毀傷最大化;而對(duì)防御方來說,可以對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行重點(diǎn)保護(hù)。對(duì)于網(wǎng)絡(luò)毀傷問題,在對(duì)每個(gè)節(jié)點(diǎn)的攻擊代價(jià)相等的前提下,目前常用的方法是根據(jù)節(jié)點(diǎn)度值[7]、節(jié)點(diǎn)介數(shù)[8]、接近度[9]、鄰居指數(shù)[10]等節(jié)點(diǎn)重要性指標(biāo)進(jìn)行排序,篩選出排名靠前的關(guān)鍵節(jié)點(diǎn)集合然后進(jìn)行攻擊,但是上述指標(biāo)一方面不能很全面地描述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的演化,另一方面對(duì)用上述方法篩選出的關(guān)鍵節(jié)點(diǎn)集進(jìn)行攻擊也未必能使毀傷最大化[11]。因?yàn)橛蒙鲜龇椒ㄟM(jìn)行排序得到的排序靠前的節(jié)點(diǎn)組成的集合并不一定是所謂的關(guān)鍵節(jié)點(diǎn)集。

事實(shí)上,網(wǎng)絡(luò)毀傷最大問題可以類比社會(huì)網(wǎng)絡(luò)中的影響最大問題,參考社區(qū)網(wǎng)絡(luò)中k個(gè)節(jié)點(diǎn)的影響最大的定義,研究攻擊代價(jià)相等時(shí),對(duì)有限的k個(gè)節(jié)點(diǎn)進(jìn)行打擊,如何使毀傷最大的問題。關(guān)于社會(huì)網(wǎng)絡(luò)影響最大的研究不斷深入,已從同質(zhì)網(wǎng)絡(luò)擴(kuò)展到了異質(zhì)網(wǎng)絡(luò)[12-13];影響力最大化還是一個(gè)NP (non-deterministic polynomial)難的數(shù)學(xué)優(yōu)化問題[14],主要的最優(yōu)化手段或者近似求解算法都有著時(shí)間復(fù)雜度高、不適合大型網(wǎng)絡(luò)等問題,為了克服上述缺陷,學(xué)者們基于啟發(fā)式算法[15]、群智能算法[16]和強(qiáng)化學(xué)習(xí)方法[17]等手段進(jìn)行了一些有益探索。

在本文中,首先類比社會(huì)網(wǎng)絡(luò)影響力最大問題給出網(wǎng)絡(luò)毀傷最大化問題的定義。其次,為了降低算法計(jì)算復(fù)雜度,便于工程實(shí)現(xiàn),考慮啟發(fā)和貪心兩個(gè)階段,提出新的網(wǎng)絡(luò)毀傷最大算法。啟發(fā)階段用一種合理的節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)篩選出備選種子節(jié)點(diǎn)集,由于軍事作戰(zhàn)體系網(wǎng)絡(luò)具有實(shí)體單元模塊化、層次化的特點(diǎn)[18],節(jié)點(diǎn)之間的相互影響具有一定的局域化特征,這種特性可以用有短程場特性的拓?fù)鋭輀19]指標(biāo)描述,而且相對(duì)于常用的節(jié)點(diǎn)重要性指標(biāo)更有優(yōu)勢[18]。貪心階段用CELF (cost-effective lazy-forward)算法[20]來選擇關(guān)鍵節(jié)點(diǎn)。實(shí)驗(yàn)表明,本文的算法相對(duì)于直接通過節(jié)點(diǎn)重要性指標(biāo)排序獲取關(guān)鍵節(jié)點(diǎn)集的方法有較好的效果,相對(duì)于貪心算法有良好的近似并且速度上有顯著的提升。

1 網(wǎng)絡(luò)毀傷最大問題

1.1 問題描述

假設(shè)本文討論的軍事體系網(wǎng)絡(luò)為無自環(huán)簡單網(wǎng)絡(luò),其數(shù)學(xué)表示形式為G=(V,E),其中,V={v1,v2,…,vN}代表節(jié)點(diǎn)的集合,E={e1,e2,…,eM}代表邊的集合。當(dāng)攻擊的資源有限時(shí),只能對(duì)網(wǎng)絡(luò)G中有限的k個(gè)節(jié)點(diǎn)進(jìn)行打擊。在對(duì)每個(gè)節(jié)點(diǎn)攻擊代價(jià)相等的前提下,毀傷最大化問題描述為攻擊網(wǎng)絡(luò)G中由k個(gè)節(jié)點(diǎn)組成的集合S*,使得網(wǎng)絡(luò)毀傷的效果最大,即

R(S*)=max{R(S)|S?V,|S|=k}

(1)

式中:R(·)為目標(biāo)函數(shù),表示攻擊后網(wǎng)絡(luò)能力損失。

1.2 目標(biāo)函數(shù)

目標(biāo)函數(shù)R(·)的選擇有多種方式,但是需要滿足以下幾個(gè)性質(zhì)[20]:

(1)R(?)=0;

(2)R(A)≤R(B),A?B?V;

(3) 對(duì)?A?B?V,v∈VB,有R(A∪{v})-R(A)≥R(B∪{v})-R(B)。

這里采用網(wǎng)絡(luò)效率[21]指標(biāo),考慮到兩個(gè)節(jié)點(diǎn)之間的距離dij越短,傳輸就越高效,可令節(jié)點(diǎn)對(duì)之間的效率為1/dij,則整個(gè)網(wǎng)絡(luò)的效率用所有節(jié)點(diǎn)對(duì)效率平均值表示為

(2)

式中:dij∈[1,+∞),節(jié)點(diǎn)間相鄰時(shí)最短距離為1,不連通時(shí)最遠(yuǎn)距離為無窮。網(wǎng)絡(luò)效率的兩種極端情形為全連通時(shí)的η=1和全是孤立節(jié)點(diǎn)的η=0。

在網(wǎng)絡(luò)毀傷最大化問題中,為了具有可比性,認(rèn)為只刪除被攻擊節(jié)點(diǎn)所連的邊,保留原來的節(jié)點(diǎn)即將其變?yōu)楣铝⒐?jié)點(diǎn),更新后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為G′,則目標(biāo)函數(shù)可定義為網(wǎng)絡(luò)效率下降的百分比,即

(3)

易證式(3)滿足前文的3個(gè)性質(zhì)。

1.3 近似求解算法

因?yàn)榫W(wǎng)絡(luò)毀傷最大問題能夠類比社區(qū)網(wǎng)絡(luò)影響最大問題,所以網(wǎng)絡(luò)毀傷最大化也是一個(gè)NP難的問題。在網(wǎng)絡(luò)規(guī)模很大時(shí),當(dāng)前的計(jì)算能力很難滿足求解最優(yōu)問題的要求,通常采用貪心算法迭代近似求解來獲得關(guān)鍵點(diǎn)集。Nemhauser等[22]證明了基于單位損失的貪心算法能有很好的近似,能夠保證目標(biāo)函數(shù)的值至少可以達(dá)到最優(yōu)值的63%×(1-1/e)。在最優(yōu)值S*無法求解時(shí),可以用近似算法,但是該算法同樣面臨大規(guī)模網(wǎng)絡(luò)難以適用的困境,其復(fù)雜度約為O(kN2(N+M))。

劉鳳增等[23]把節(jié)點(diǎn)度值和節(jié)點(diǎn)介數(shù)相結(jié)合作為節(jié)點(diǎn)重要性指標(biāo),然后在此基礎(chǔ)上用f(V,T)函數(shù)選出T個(gè)重要節(jié)點(diǎn)(其中,T=α(k-i),α為參數(shù),k為打擊節(jié)點(diǎn)數(shù),i為迭代數(shù)),提出了一種基于重要節(jié)點(diǎn)的貪婪算法(greedy algorithm based on important nodes, GABIN),從而提高計(jì)算效率,當(dāng)k?N時(shí),算法復(fù)雜度約為O(k/2(2+(1+k)α)·N(N+M))。

2 基于拓?fù)鋭莸臍畲笏惴?/h2>

受文獻(xiàn)[23]的啟發(fā),為了提高算法的計(jì)算效率,采用啟發(fā)和貪心兩步:啟發(fā)階段利用節(jié)點(diǎn)的拓?fù)鋭菖判颢@得備選種子節(jié)點(diǎn)集,貪心階段在種子節(jié)點(diǎn)集中篩選出使得網(wǎng)絡(luò)毀傷最大的節(jié)點(diǎn),提出一種獲取關(guān)鍵節(jié)點(diǎn)集使毀傷最大的算法。

2.1 拓?fù)鋭?/h3>

拓?fù)鋭菰醋詧隼碚?認(rèn)為網(wǎng)絡(luò)中節(jié)點(diǎn)周圍存在一個(gè)虛擬場,場內(nèi)的節(jié)點(diǎn)會(huì)受到其他節(jié)點(diǎn)共同作用。對(duì)于軍事作戰(zhàn)體系網(wǎng)絡(luò),節(jié)點(diǎn)的作用范圍限制在有限的區(qū)域,可以用拓?fù)鋭輥砻枋?基于類似特性,拓?fù)鋭莸膽?yīng)用還常見于在骨干網(wǎng)絡(luò)提取[24-25]和染色體結(jié)構(gòu)研究[26]等方面。對(duì)于網(wǎng)絡(luò)G,節(jié)點(diǎn)集V中的節(jié)點(diǎn)vi的拓?fù)鋭菘捎妹枋龆坛虉霾⑶矣袃?yōu)良數(shù)學(xué)性質(zhì)的高斯勢函數(shù)表示為

(4)

式中:dji表示節(jié)點(diǎn)之間的距離,這里采用最短路徑來表示;mj表示節(jié)點(diǎn)的質(zhì)量,描述節(jié)點(diǎn)固有屬性;σ表示影響因子。

mj在實(shí)際網(wǎng)絡(luò)中含義十分豐富,要結(jié)合實(shí)際情況具體分析。如果忽略節(jié)點(diǎn)之間固有屬性的差別,將其視為同質(zhì)節(jié)點(diǎn),則式(4)可以化為

(5)

在式(5)中,影響因子σ控制著節(jié)點(diǎn)vi的作用范圍,對(duì)拓?fù)鋭莸姆植季哂泻艽笥绊?其值通常利用數(shù)據(jù)場理論中的拓?fù)鋭蒽豙27]來進(jìn)行優(yōu)化,具體為

(6)

為說明拓?fù)鋭莸目捎眯?基于體系作戰(zhàn)相關(guān)理論[30]設(shè)計(jì)了一個(gè)簡單的軍事作戰(zhàn)體系想定模型,如圖1所示,分別對(duì)應(yīng)實(shí)體的關(guān)系和用Gephi生成的網(wǎng)絡(luò)結(jié)構(gòu)圖。以上級(jí)指揮所(V12)為中心,下轄兩個(gè)戰(zhàn)術(shù)級(jí)指揮所(V8和V9),上級(jí)指揮所與戰(zhàn)術(shù)級(jí)指揮所可分別指揮兩架作戰(zhàn)飛機(jī)(V10和V11),同時(shí)還接收來自雷達(dá)情報(bào)處理節(jié)點(diǎn)(V7和V4)的情報(bào)信息,兩個(gè)雷達(dá)情報(bào)處理節(jié)點(diǎn)分別轄3個(gè)(V1、V2和V3)和2個(gè)(V4和V5)雷達(dá)站,雷達(dá)站2還可以直接和戰(zhàn)術(shù)級(jí)指揮所2進(jìn)行通信。

圖1 軍事作戰(zhàn)體系模型及對(duì)應(yīng)的網(wǎng)絡(luò)拓?fù)鋱DFig.1 Military combat system model and corresponding network topology

從實(shí)際模型分析,V12、V9、V8、V4以及V7為重要實(shí)體集合,用式(5)計(jì)算上述模型的拓?fù)鋭?排名依次為V12、V9、V4、V8、V7、V10、V2、V11、V1、V3、V6和V5,符合實(shí)際的重要性的排名,因此可以作為啟發(fā)階段種子節(jié)點(diǎn)篩選的依據(jù),在此基礎(chǔ)上進(jìn)行網(wǎng)絡(luò)毀傷。

2.2 CELF思想

CELF算法[20]是一種經(jīng)典的社會(huì)網(wǎng)絡(luò)影響力最大化算法,其在貪心算法的基礎(chǔ)上,利用節(jié)點(diǎn)影響力存在次模性對(duì)原算法進(jìn)行改進(jìn),使得效率提升了近700%。對(duì)于毀傷最大問題,考慮當(dāng)前迭代輪次下增益排名前三的節(jié)點(diǎn)v1、v2和v3,將節(jié)點(diǎn)v1加入關(guān)鍵節(jié)點(diǎn)集后,在下一輪選擇節(jié)點(diǎn)時(shí),若v2在此輪的毀傷增益即網(wǎng)絡(luò)效率下降率大于v3在上一輪的毀傷增益,根據(jù)次模性,v3在此輪的毀傷增益必定小于其在上一輪的毀傷增益。所以,v2在此輪的毀傷增益大于v3,可以直接將節(jié)點(diǎn)v2加入關(guān)鍵節(jié)點(diǎn)集,不需要再額外計(jì)算v3的毀傷增益,進(jìn)而提升了計(jì)算效率。

結(jié)合拓?fù)鋭莺虲ELF思想,提出一種基于拓?fù)鋭莸腃ELF (CELF based on topology potential, TPCELF)。

2.3 TPCELF算法

為了方便表述,對(duì)算法先做如下說明:一方面,根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)鋭菖判?用函數(shù)g(VT,T)篩選出節(jié)點(diǎn)集VT中排序靠前的T個(gè)重要節(jié)點(diǎn);另一方面基于CELF思想,計(jì)算某個(gè)節(jié)點(diǎn)后被毀傷的毀傷增益即網(wǎng)絡(luò)效率下降百分比δv=R(S∪{v})-R(S),v∈VT,每次計(jì)算后將其排序,記排前三名的節(jié)點(diǎn)分別為v1、v2和v3,對(duì)應(yīng)的增益分別為δv1、δv2和δv3。具體如算法1所示。

算法1 TPCELF算法輸入 網(wǎng)絡(luò)G,節(jié)點(diǎn)數(shù)k,參數(shù)β輸出 節(jié)點(diǎn)集S1. 初始化S=?,i=1,VT=V2. T=max(k-i+1,β)3. VT=g(VT,T)4. v1=argmaxvj∈VT(R(S∪{vj})-R(S))5. S=S∪{v1},VT=VTvA6. 若iδv3: S=S∪{v2},VT=VTv2,i=i+1,轉(zhuǎn)2 否則轉(zhuǎn)2 否則轉(zhuǎn)77. 輸出S

以鄰接表為存儲(chǔ)結(jié)構(gòu),用廣度優(yōu)先搜索算法計(jì)算網(wǎng)絡(luò)效率的時(shí)間復(fù)雜度O(N(N+M)),計(jì)算拓?fù)鋭莸臅r(shí)間復(fù)雜度同樣為O(N(N+M)),則算法1的復(fù)雜度為O((k/2)·(max(k,β)+1)N(N+M)),一般β要大于k,所以相對(duì)于GABIN算法,理論上時(shí)間能夠減少到β/α(1+k)倍;若種子節(jié)點(diǎn)個(gè)數(shù)選擇方法采用GABIN算法的T=α(k-i+1),效率也至少可以提高一倍。

3 實(shí)驗(yàn)與結(jié)果分析

為了檢驗(yàn)所提方法的可行性和有效性,通過仿真實(shí)驗(yàn)來進(jìn)行驗(yàn)證。實(shí)驗(yàn)硬件環(huán)境為Intel(R) Core(TM) i7-10750H CPU @ 2.60 GHz,16 G內(nèi)存,操作系統(tǒng)為Windows10,軟件環(huán)境為Matlab 2016b;實(shí)驗(yàn)所用網(wǎng)絡(luò)為無標(biāo)度模型生成的仿真網(wǎng)絡(luò)(即度分布p(d)～d-γ,提前在Python環(huán)境下用Stanford-Snap包生成)和基于實(shí)際數(shù)據(jù)的真實(shí)網(wǎng)絡(luò)。具體實(shí)驗(yàn)如下。

3.1 計(jì)算復(fù)雜度仿真實(shí)驗(yàn)

前文通過理論分析了TPCELF算法相比于GABIN算法的速度優(yōu)勢,為了驗(yàn)證理論的正確性,同時(shí)和GREEDY算法一起進(jìn)行比較,分析各種算法的實(shí)際運(yùn)行時(shí)間復(fù)雜度,從而選擇計(jì)算效率最高的方法。數(shù)據(jù)集部分,考慮到無標(biāo)度網(wǎng)絡(luò)模型是網(wǎng)絡(luò)科學(xué)中最常見的網(wǎng)絡(luò)生成模型,且常被用來作為各種評(píng)測的基線數(shù)據(jù),所以選用斯坦福大學(xué)的Snap工具包生成無標(biāo)度模型網(wǎng)絡(luò)的測試集。生成的無標(biāo)度模型網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)變化從50到700不等,網(wǎng)絡(luò)的冪指數(shù)統(tǒng)一為γ=2,毀傷的關(guān)鍵節(jié)點(diǎn)數(shù)為k=8,啟發(fā)階段參數(shù)為α=5,β=10。3種算法的運(yùn)算時(shí)間結(jié)果如表1所示,變化規(guī)律如圖2所示。

表1 算法運(yùn)行時(shí)間比較Table 1 Algorithm run time comparison s

圖2 算法運(yùn)行時(shí)間Fig.2 Algorithm run time

從圖2中可以看出,GREEDY算法的運(yùn)行時(shí)間隨著節(jié)點(diǎn)數(shù)增加呈指數(shù)狀增長,因此在節(jié)點(diǎn)數(shù)量很大的時(shí)候根本無法運(yùn)用,相比之下TPCELF和GABIN算法的運(yùn)算時(shí)間曲線要平緩許多。另外從表1可以看出,TPCELF和GABIN算法的運(yùn)行時(shí)間比GREEDY算法下降一個(gè)數(shù)量級(jí),并且在N=700時(shí),分別約為GREEDY算法的1/115和1/16,其速度要快很多。通過比較不同節(jié)點(diǎn)數(shù)下TPCELF算法與GABIN算法的運(yùn)行時(shí)間,可知前者比后者運(yùn)行時(shí)間至少減少一半以上,符合前文的理論分析。

3.2 無標(biāo)度網(wǎng)絡(luò)仿真實(shí)驗(yàn)

3.2.1 對(duì)不同結(jié)構(gòu)網(wǎng)絡(luò)的毀傷效果比較

表3 不同網(wǎng)絡(luò)結(jié)構(gòu)下各算法效果比較Table 3 Effect comparison of each algorithm under different network structures

圖3 各算法在不同網(wǎng)絡(luò)結(jié)構(gòu)下的平均毀傷效果Fig.3 Average damage effect of each algorithm under different network structures

從圖3中可以看出,當(dāng)γ≤2時(shí),幾種算法的平均毀傷效果差別不大,當(dāng)γ≥2.5時(shí),上述算法間開始表現(xiàn)出較大的差異;TPCELF算方法和GABIN算法的平均毀傷效果在不同網(wǎng)絡(luò)結(jié)構(gòu)下 都要優(yōu)于其他算法,說明這兩種算法找到的關(guān)鍵節(jié)點(diǎn)集更逼近網(wǎng)絡(luò)毀傷最大化的效果,而按照重要性指標(biāo)排序得到的毀傷關(guān)鍵節(jié)點(diǎn)集不一定是最優(yōu)的毀傷關(guān)鍵節(jié)點(diǎn)集。

從表2中可以看出,不同網(wǎng)絡(luò)結(jié)構(gòu)下TPCELF算法和GABIN算法的最大毀傷偏差遠(yuǎn)小于TPCELF算法相對(duì)于其他3種算法的偏差,前兩者平均毀傷偏差更小,并且在γ取1.5～2.5時(shí),TPCELF算法的平均毀傷效果要優(yōu)于GABIN算法的。另外,從表3中可以得出,TPCELF算法不劣于GABIN算法的平均值約為71.3%,而這兩種算法不劣于其他3種算法中的任意一種的數(shù)量分別為96.38%和97%,平均重合比例約為99.1%。綜合以上分析,可以認(rèn)為TPCELF算法在效果上是GABIN算法很好的近似,甚至可能超過后者,而前者的運(yùn)算速度更有優(yōu)勢,因此在處理大型網(wǎng)絡(luò)時(shí),為了進(jìn)一步提高計(jì)算速度,可優(yōu)先采用TPCELF算法。

3.2.2 對(duì)不同規(guī)模網(wǎng)絡(luò)的毀傷效果比較

除了不同網(wǎng)絡(luò)結(jié)構(gòu),還要考慮不同規(guī)模下所提算法的適用性。用100個(gè)節(jié)點(diǎn)數(shù)N取150～500,γ=2.5的無標(biāo)度模型網(wǎng)絡(luò)進(jìn)行仿真,設(shè)定毀傷的關(guān)鍵節(jié)點(diǎn)數(shù)為k=8,啟發(fā)階段的參數(shù)為α=5,β=10。得到不同網(wǎng)絡(luò)規(guī)模下各算法毀傷效果的優(yōu)劣計(jì)數(shù)如表4所示。

表4 不同網(wǎng)絡(luò)規(guī)模下各算法效果比較Table 4 Effect comparison of each algorithm with different network scales

從表4中可以得出:TPCELF算法不劣于GABIN算法的平均值約為71.3%,而這兩種算法不劣于其他3種算法中的任意一種的數(shù)量分別為91.5%和93.13%,平均重合比例約為98%。結(jié)論同第3.2.1節(jié)一樣,可以認(rèn)為TPCELF算法是GABIN算法很好的近似。

3.2.3 參數(shù)β對(duì)算法效果的影響

通過第2.3節(jié)的分析和前面的實(shí)驗(yàn)可知,啟發(fā)階段的參數(shù)α、β對(duì)算法的效果和運(yùn)行時(shí)間都有較大的影響。關(guān)于TPCELF算法如何選擇合理參數(shù)β的問題,基于不同的β進(jìn)行網(wǎng)絡(luò)毀傷實(shí)驗(yàn)。設(shè)定毀傷的關(guān)鍵節(jié)點(diǎn)數(shù)為k=8,啟發(fā)階段的參數(shù)為α=5,β的范圍變化為1～16,共生成100個(gè)節(jié)點(diǎn)數(shù)N=300,γ=3的無標(biāo)度模型網(wǎng)絡(luò),用不同的算法對(duì)網(wǎng)絡(luò)進(jìn)行毀傷實(shí)驗(yàn)。各算法在β值變化時(shí)的網(wǎng)絡(luò)平均下降效率如圖4所示。

從圖4中可以看出,當(dāng)βk時(shí),TPCELF算法平均毀傷效果很接近GABIN算法,隨著β增大,從β=9開始算法比GABIN算法的平均毀傷效果要略優(yōu),表明較大的β值有可能使算法的效果得到提升,可以在大于k的范圍內(nèi)選取β。但隨β增大,TPCELF算法相對(duì)與其他算法的效果提升并不明顯,而且算法的運(yùn)行時(shí)間會(huì)隨之變長。因此,關(guān)于參數(shù)β的選取,首先考慮大于毀傷節(jié)點(diǎn)數(shù)k的范圍,而后結(jié)合運(yùn)行時(shí)間,若要使TPCELF算法相對(duì)于GABIN算法速度至少提升L倍,則β可以在(k,α(1+k)/(L+1))內(nèi)選擇一整數(shù)。而在GABIN算法中,對(duì)于如何選擇啟發(fā)階段的參數(shù)α沒有相應(yīng)的參考指標(biāo),只是隨著網(wǎng)絡(luò)規(guī)模的增大而人為地選取較大的值。

3.3 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

在真實(shí)數(shù)據(jù)集上,選用俄勒岡大學(xué)的Route Views項(xiàng)目數(shù)據(jù)來驗(yàn)證算法的效果。俄勒岡自治系統(tǒng)數(shù)據(jù)集1[31]常被用來研究一個(gè)大型互聯(lián)網(wǎng)絡(luò)形成的自治系統(tǒng)組織狀況,共記錄了2001年3月31日至5月26日期間9個(gè)片段的自治系統(tǒng)網(wǎng)絡(luò)拓?fù)鋱D特征,從中隨機(jī)選擇了4月7日統(tǒng)計(jì)的大學(xué)路由數(shù)據(jù)網(wǎng)絡(luò)作為實(shí)測無向網(wǎng)絡(luò),該網(wǎng)絡(luò)共有10 729個(gè)節(jié)點(diǎn)和20 199條邊,屬于大型網(wǎng)絡(luò)。對(duì)該網(wǎng)絡(luò)進(jìn)行毀傷實(shí)驗(yàn),設(shè)置毀傷的關(guān)鍵節(jié)點(diǎn)數(shù)為k=1～10,啟發(fā)階段的參數(shù)為α=10,β=10。得到各算法的網(wǎng)絡(luò)下降效率如圖5所示。

圖5 實(shí)測數(shù)據(jù)網(wǎng)絡(luò)的下降效率仿真Fig.5 Efficiency decrease simulation for real network data

從圖5中可以看出,在毀傷節(jié)點(diǎn)數(shù)k取1～6時(shí),TPCELF算法、GABIN算法和基于度排序的算法的結(jié)果是一致的,但是隨著k值的增大,基于度排序的結(jié)果出現(xiàn)了偏差且越來越大;對(duì)于不同的毀傷節(jié)點(diǎn)數(shù),TPCELF算法和GABIN算法的結(jié)果除了k=10時(shí)前者更優(yōu)外,其他都是一致的。基于點(diǎn)介數(shù)和接近度排序算法在k較小時(shí)和其他算法的結(jié)果基本相近,但是隨后出現(xiàn)了波動(dòng)和較大的偏差,再一次表明根據(jù)重要性排名得到的網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)集并不一定能使毀傷效果最大化。從計(jì)算時(shí)間上來看,以毀傷10個(gè)節(jié)點(diǎn)為例,各算法的運(yùn)行時(shí)間分別為:143.313 2 s、1 674.107 2 s、24.163 5 s、59.836 4 s和27.018 5 s,TPCELF算法的運(yùn)行時(shí)間約為GABIN算法的1/10,并且效果更優(yōu);其他幾種算法耗時(shí)較少但效果欠佳。綜合毀傷效果和運(yùn)行時(shí)間兩方面來看,在該真實(shí)數(shù)據(jù)集上,TPCELF算法都更有優(yōu)勢。

4 結(jié) 論

為了挖掘網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)集來實(shí)現(xiàn)毀傷最大化,本文提出了一種基于拓?fù)鋭莺虲ELF思想的近似算法,相對(duì)于GREEDY算法和GABIN算法,本文算法在有效降低計(jì)算復(fù)雜度的同時(shí)能夠保持較好的毀傷效果,以便于運(yùn)用到大型網(wǎng)絡(luò)上。相比于根據(jù)常用節(jié)點(diǎn)重要性指標(biāo)進(jìn)行排序的方法,本文方法從網(wǎng)絡(luò)毀傷的角度為尋找關(guān)鍵節(jié)點(diǎn)集提供了的一種參考。