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

俞錦濤, 肖 兵, 熊家軍

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

0 引 言

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

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

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

1 網絡毀傷最大問題

1.1 問題描述

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

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

(1)

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

1.2 目標函數

目標函數R(·)的選擇有多種方式,但是需要滿足以下幾個性質[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)。

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

(2)

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

在網絡毀傷最大化問題中,為了具有可比性,認為只刪除被攻擊節點所連的邊,保留原來的節點即將其變為孤立節點,更新后的網絡拓撲結構為G′,則目標函數可定義為網絡效率下降的百分比,即

(3)

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

1.3 近似求解算法

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

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

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

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

2.1 拓撲勢

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

(4)

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

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

(5)

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

(6)

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

圖1 軍事作戰體系模型及對應的網絡拓撲圖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,符合實際的重要性的排名,因此可以作為啟發階段種子節點篩選的依據,在此基礎上進行網絡毀傷。

2.2 CELF思想

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

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

2.3 TPCELF算法

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

算法1 TPCELF算法輸入 網絡G,節點數k,參數β輸出 節點集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,轉2 否則轉2 否則轉77. 輸出S

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

3 實驗與結果分析

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

3.1 計算復雜度仿真實驗

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

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

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

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

3.2 無標度網絡仿真實驗

3.2.1 對不同結構網絡的毀傷效果比較

表3 不同網絡結構下各算法效果比較Table 3 Effect comparison of each algorithm under different network structures

圖3 各算法在不同網絡結構下的平均毀傷效果Fig.3 Average damage effect of each algorithm under different network structures

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

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

3.2.2 對不同規模網絡的毀傷效果比較

除了不同網絡結構,還要考慮不同規模下所提算法的適用性。用100個節點數N取150～500,γ=2.5的無標度模型網絡進行仿真,設定毀傷的關鍵節點數為k=8,啟發階段的參數為α=5,β=10。得到不同網絡規模下各算法毀傷效果的優劣計數如表4所示。

表4 不同網絡規模下各算法效果比較Table 4 Effect comparison of each algorithm with different network scales

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

3.2.3 參數β對算法效果的影響

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

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

3.3 真實數據集實驗

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

圖5 實測數據網絡的下降效率仿真Fig.5 Efficiency decrease simulation for real network data

從圖5中可以看出,在毀傷節點數k取1～6時,TPCELF算法、GABIN算法和基于度排序的算法的結果是一致的,但是隨著k值的增大,基于度排序的結果出現了偏差且越來越大;對于不同的毀傷節點數,TPCELF算法和GABIN算法的結果除了k=10時前者更優外,其他都是一致的。基于點介數和接近度排序算法在k較小時和其他算法的結果基本相近,但是隨后出現了波動和較大的偏差,再一次表明根據重要性排名得到的網絡關鍵節點集并不一定能使毀傷效果最大化。從計算時間上來看,以毀傷10個節點為例,各算法的運行時間分別為: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,并且效果更優;其他幾種算法耗時較少但效果欠佳。綜合毀傷效果和運行時間兩方面來看,在該真實數據集上,TPCELF算法都更有優勢。

4 結 論

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