俞錦濤, 肖 兵, 熊家軍

(1. 空軍預警學院信息對抗系, 湖北 武漢 430019; 2. 空軍預警學院預警情報系, 湖北 武漢 430019)

0 引 言

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

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

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

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

1.1 問題描述

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

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

(1)

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

1.2 目標函數(shù)

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

(1)R(?)=0;

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

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

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

(2)

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

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

(3)

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

1.3 近似求解算法

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

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

2 基于拓撲勢的毀傷最大算法

受文獻[23]的啟發(fā),為了提高算法的計算效率,采用啟發(fā)和貪心兩步:啟發(fā)階段利用節(jié)點的拓撲勢排序獲得備選種子節(jié)點集,貪心階段在種子節(jié)點集中篩選出使得網(wǎng)絡毀傷最大的節(jié)點,提出一種獲取關(guān)鍵節(jié)點集使毀傷最大的算法。

2.1 拓撲勢

拓撲勢源自場理論,認為網(wǎng)絡中節(jié)點周圍存在一個虛擬場,場內(nèi)的節(jié)點會受到其他節(jié)點共同作用。對于軍事作戰(zhàn)體系網(wǎng)絡,節(jié)點的作用范圍限制在有限的區(qū)域,可以用拓撲勢來描述;基于類似特性,拓撲勢的應用還常見于在骨干網(wǎng)絡提取[24-25]和染色體結(jié)構(gòu)研究[26]等方面。對于網(wǎng)絡G,節(jié)點集V中的節(jié)點vi的拓撲勢可用描述短程場并且有優(yōu)良數(shù)學性質(zhì)的高斯勢函數(shù)表示為

(4)

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

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

(5)

在式(5)中,影響因子σ控制著節(jié)點vi的作用范圍,對拓撲勢的分布具有很大影響,其值通常利用數(shù)據(jù)場理論中的拓撲勢熵[27]來進行優(yōu)化,具體為

(6)

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

圖1 軍事作戰(zhàn)體系模型及對應的網(wǎng)絡拓撲圖Fig.1 Military combat system model and corresponding network topology

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

2.2 CELF思想

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

結(jié)合拓撲勢和CELF思想,提出一種基于拓撲勢的CELF (CELF based on topology potential, TPCELF)。

2.3 TPCELF算法

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

算法1 TPCELF算法輸入 網(wǎng)絡G,節(jié)點數(shù)k,參數(shù)β輸出 節(jié)點集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

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

3 實驗與結(jié)果分析

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

3.1 計算復雜度仿真實驗

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

表1 算法運行時間比較Table 1 Algorithm run time comparison s

圖2 算法運行時間Fig.2 Algorithm run time

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

3.2 無標度網(wǎng)絡仿真實驗

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

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

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

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

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

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

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

表4 不同網(wǎng)絡規(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é)一樣,可以認為TPCELF算法是GABIN算法很好的近似。

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

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

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

3.3 真實數(shù)據(jù)集實驗

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

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

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

4 結(jié) 論

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