李 鍇，吳 緯，劉福勝，陳庚申，陳守華

（1.裝甲兵工程學(xué)院，北京 100072；2.后勤學(xué)院，北京 100858）

基于PageRank算法的武器裝備體系重要節(jié)點(diǎn)評(píng)估*

李 鍇1，吳 緯1，劉福勝1，陳庚申2，陳守華1

（1.裝甲兵工程學(xué)院，北京 100072；2.后勤學(xué)院，北京 100858）

將武器裝備系統(tǒng)抽象為網(wǎng)絡(luò)節(jié)點(diǎn)，利用復(fù)雜網(wǎng)絡(luò)理論研究評(píng)估武器裝備體系中的重要節(jié)點(diǎn)。針對(duì)傳統(tǒng)PageRank算法在該應(yīng)用中存在的問(wèn)題，提出一種修正的PageRank算法。該算法對(duì)懸掛節(jié)點(diǎn)及有向環(huán)狀網(wǎng)絡(luò)節(jié)點(diǎn)的重要度評(píng)估具備收斂性。仿真實(shí)例驗(yàn)證了該修正算法對(duì)雙目標(biāo)作戰(zhàn)環(huán)節(jié)點(diǎn)重要度評(píng)估的有效性。為了進(jìn)一步驗(yàn)證所提算法的準(zhǔn)確性，引入特征譜理論和移除節(jié)點(diǎn)法評(píng)估網(wǎng)絡(luò)的抗毀性。

PageRank算法，武器裝備體系，復(fù)雜網(wǎng)絡(luò)，節(jié)點(diǎn)重要度

0 引言

在一體化聯(lián)合作戰(zhàn)背景下，體系作戰(zhàn)的概念在網(wǎng)絡(luò)中心戰(zhàn)的基礎(chǔ)上被提出并被深入研究。在體系作戰(zhàn)的整體進(jìn)程中，各種武器平臺(tái)和武器裝備系統(tǒng)通過(guò)信息系統(tǒng)與技術(shù)構(gòu)成武器裝備體系［1］。武器裝備體系是在一定的戰(zhàn)略指導(dǎo)、軍事指揮以及綜合保障的前提下，為完成一定的使命任務(wù)，按照作戰(zhàn)規(guī)律，將一定數(shù)量、不同種類(lèi)和型號(hào)的主戰(zhàn)裝備、電子信息裝備以及綜合保障裝備等武器裝備系統(tǒng)，通過(guò)信息系統(tǒng)與技術(shù)綜合起來(lái)的功能整體［2-4］。

復(fù)雜網(wǎng)絡(luò)可以看作是對(duì)復(fù)雜系統(tǒng)的抽象數(shù)學(xué)模型，利用復(fù)雜網(wǎng)絡(luò)對(duì)武器裝備體系進(jìn)行研究取得了許多研究成果［5-7］。采用復(fù)雜網(wǎng)絡(luò)理論對(duì)武器裝備體系進(jìn)行研究時(shí)，主要利用數(shù)學(xué)圖論和統(tǒng)計(jì)物理理論展開(kāi)研究，基本方法是：將武器裝備體系抽象為一個(gè)圖 G=（V，E），節(jié)點(diǎn)集 V={v1，v2，…，vn}表示體系中各武器裝備平臺(tái)和武器裝備系統(tǒng)，如指揮控制中心和火力打擊系統(tǒng)；有向邊集 E={e1，e2，…，en}表示體系中的信息流、物質(zhì)流和能量流及各武器裝備節(jié)點(diǎn)間的協(xié)同控制關(guān)系［8］。通過(guò)將武器裝備體系抽象為圖的方式，整個(gè)戰(zhàn)場(chǎng)空間中的裝備實(shí)體及交互關(guān)系構(gòu)成一個(gè)復(fù)雜網(wǎng)絡(luò)，采用統(tǒng)計(jì)物理方法，對(duì)武器裝備體系復(fù)雜網(wǎng)絡(luò)的整體統(tǒng)計(jì)特性進(jìn)行相關(guān)研究［9］。

體系對(duì)抗的本質(zhì)是對(duì)敵方武器裝備體系的重要節(jié)點(diǎn)實(shí)施打擊，通過(guò)體系干擾和體系退化，達(dá)到克敵制勝的作戰(zhàn)目標(biāo)?，F(xiàn)階段對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)重要度的評(píng)估主要有兩種方法［10-11］：一是從復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)出發(fā)，通過(guò)節(jié)點(diǎn)度、介數(shù)和中心性等度量參數(shù)來(lái)評(píng)估節(jié)點(diǎn)的重要性，如跳面節(jié)點(diǎn)法；二是通過(guò)移除節(jié)點(diǎn)和連接邊的方式，考察網(wǎng)絡(luò)的抗毀性變化，以此對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的重要度進(jìn)行評(píng)估，如生成數(shù)目法。研究發(fā)現(xiàn)，以上方法對(duì)不具備連通性的復(fù)雜網(wǎng)絡(luò)不能適用，因此，需要提出新的網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估方法。研究武器裝備體系重要節(jié)點(diǎn)，對(duì)于保己克敵，制定作戰(zhàn)方案具有重要的戰(zhàn)略意義，同時(shí)為武器裝備體系的下一步發(fā)展提供參考。

1 基本PageRank算法

PageRank算法的基本思想是：網(wǎng)絡(luò)中節(jié)點(diǎn)的重要度不僅由節(jié)點(diǎn)的度值決定，還與其鄰居節(jié)點(diǎn)的重要度有關(guān)，該算法的優(yōu)勢(shì)在于將復(fù)雜網(wǎng)絡(luò)作為整體研究，從全局進(jìn)行考慮，不是以孤立的節(jié)點(diǎn)為研究對(duì)象［12］。

基本PageRank算法的主要步驟為：

1）對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)設(shè)定PageRank初值（簡(jiǎn)稱(chēng)PR值），為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目。

2）在k-1步時(shí)，將節(jié)點(diǎn)i的PR值平均分給其指向的鄰居節(jié)點(diǎn)。簡(jiǎn)單來(lái)說(shuō)，若節(jié)點(diǎn)i的出度值為mi，那么節(jié)點(diǎn)i所指向的所有鄰居節(jié)點(diǎn)從節(jié)點(diǎn)i處分配到的PR值為。若節(jié)點(diǎn)i的出度值為0，則節(jié)點(diǎn)i在k-1步時(shí)只能接受其他節(jié)點(diǎn)分配的PR值。

節(jié)點(diǎn)i的PR值結(jié)果為它最終分配得到的PR值之和：

其中：aji為有向網(wǎng)絡(luò)G的鄰接矩陣A（G）中的元素，若存在邊由節(jié)點(diǎn)j指向節(jié)點(diǎn)i，則aji=1，否則aji=0。

需要說(shuō)明的是：網(wǎng)絡(luò)G中的所有節(jié)點(diǎn)的PR值總和是不變的，即對(duì)于k∈Z+，恒成立。

基本PageRank算法可以寫(xiě)成矩陣形式，具體如式（2）所示：

表1 8個(gè)節(jié)點(diǎn)的PR值計(jì)算結(jié)果

在復(fù)雜網(wǎng)絡(luò)研究中，通常將出度值為0的節(jié)點(diǎn)稱(chēng)為懸掛節(jié)點(diǎn)（Dangling Node），通過(guò)研究發(fā)現(xiàn)，基本PageRank算法對(duì)于懸掛節(jié)點(diǎn)是失效的，無(wú)法對(duì)懸掛節(jié)點(diǎn)進(jìn)行PR值計(jì)算。同時(shí)對(duì)于環(huán)狀結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)，基本PageRank算法也可能會(huì)出現(xiàn)無(wú)限循環(huán)而不能收斂的情況。對(duì)于圖2中的有向環(huán)狀網(wǎng)絡(luò)結(jié)構(gòu)，經(jīng)過(guò)5次迭代后，PR值又重新回到初值，因此，需要對(duì)基本PageRank算法進(jìn)行改進(jìn)。

2 修正PageRank算法

修正PageRank算法的基本思想是：從當(dāng)前節(jié)點(diǎn)i出發(fā)，不論節(jié)點(diǎn)i是否為懸掛節(jié)點(diǎn)，都將以一定的概率隨機(jī)選擇網(wǎng)絡(luò)中的任意其他節(jié)點(diǎn)作為節(jié)點(diǎn)i的出度目標(biāo)節(jié)點(diǎn)。

修正PageRank算法的主要步驟為：

1）對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)設(shè)定PageRank初值（簡(jiǎn)稱(chēng)PR值），為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目。

2）給定一個(gè)收縮因子 t∈（0，1），按照基本PageRank算法計(jì)算節(jié)點(diǎn)的PR值，再利用收縮因子t對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的PR值進(jìn)行縮減，此時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的PR值滿(mǎn)足。

3）將1-t的PR值平均分給網(wǎng)絡(luò)中的N個(gè)節(jié)點(diǎn)，則懸掛節(jié)點(diǎn)PR值為，整個(gè)網(wǎng)絡(luò)的PR值總和滿(mǎn)足。

節(jié)點(diǎn)的修正PR值為：

修正PageRank算法可以寫(xiě)成矩陣形式，如式（5）所示：

對(duì)于收縮因子t的取值，需要充分考慮到算法的有效性和收斂性［13］：若 t→1，則收斂速度愈慢，當(dāng)t=1時(shí)，算法則無(wú)法收斂；若t→0，則收斂速度愈快，當(dāng)t=0時(shí)，算法在計(jì)算環(huán)狀網(wǎng)絡(luò)時(shí)可能會(huì)無(wú)限循環(huán)。對(duì)于收縮因子t的取值，建議為t=0.85［12］。

3 實(shí)例應(yīng)用

3.1 實(shí)例分析

從復(fù)雜網(wǎng)絡(luò)理論中節(jié)點(diǎn)和連接邊的分類(lèi)出發(fā)，Cares建立了基于信息網(wǎng)絡(luò)的作戰(zhàn)模型［14］，將武器裝備體系的武器平臺(tái)和武器裝備系統(tǒng)分為4類(lèi)節(jié)點(diǎn)：決策節(jié)點(diǎn)（Decider）、響應(yīng)節(jié)點(diǎn)（Influencer）、傳感器節(jié)點(diǎn)（Sensor）和目標(biāo)節(jié)點(diǎn)（Target）?，F(xiàn)代戰(zhàn)爭(zhēng)的作戰(zhàn)形式是一個(gè)循環(huán)反復(fù)的過(guò)程：傳感系統(tǒng)發(fā)現(xiàn)目標(biāo)后，通過(guò)信息傳輸系統(tǒng)將目標(biāo)信息傳遞給指控系統(tǒng)，指控系統(tǒng)經(jīng)過(guò)分析決策后向火力系統(tǒng)下達(dá)攻擊命令，火力系統(tǒng)接到命令后對(duì)目標(biāo)節(jié)點(diǎn)實(shí)施打擊。圖3為雙目標(biāo)節(jié)點(diǎn)作戰(zhàn)環(huán)結(jié)構(gòu)示意圖，圖中有向邊分別表示信息流、物質(zhì)流和能量流及武器裝備系統(tǒng)間的控制協(xié)同關(guān)系。

利用修正PageRank算法對(duì)圖3作戰(zhàn)環(huán)中武器裝備體系節(jié)點(diǎn)的重要性進(jìn)行評(píng)估，收縮因子t=0.85，計(jì)算結(jié)果如表2所示。圖3所示作戰(zhàn)環(huán)的武器裝備體系中節(jié)點(diǎn)重要度評(píng)估結(jié)果為。

3.2 結(jié)果驗(yàn)證

為驗(yàn)證修正PageRank算法評(píng)估結(jié)果的準(zhǔn)確性，利用特征譜理論和移除節(jié)點(diǎn)法評(píng)估圖3網(wǎng)絡(luò)的抗毀性，基于抗毀性的測(cè)度連通度來(lái)表征節(jié)點(diǎn)的重要性［15］，將兩種評(píng)估結(jié)果進(jìn)行比較分析，證明修正PageRank算法是否具備可行性。

表2 雙目標(biāo)作戰(zhàn)環(huán)節(jié)點(diǎn)PR值結(jié)果

設(shè)網(wǎng)絡(luò)G有N個(gè)節(jié)點(diǎn)，根據(jù)矩陣?yán)碚摚徑泳仃嘇（G）包含有N個(gè)特征值，分別記為由于A（G）不是對(duì)稱(chēng)矩陣，因此中會(huì)存在共軛復(fù)數(shù)。

對(duì)于k階矩Mk而言，臨界矩陣A（G）中的元素為1或 0，若，說(shuō)明存在一條長(zhǎng)度為k的閉合回路，起點(diǎn)和終點(diǎn)均為節(jié)點(diǎn)i1。NMk表示網(wǎng)絡(luò)G中長(zhǎng)度為k的閉合回路的數(shù)目。

復(fù)雜網(wǎng)絡(luò)連通度是抗毀性的重要測(cè)度之一，網(wǎng)絡(luò)中節(jié)點(diǎn)和連接邊的冗余程度決定網(wǎng)絡(luò)連通度的大小。通常采用網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)之間的路徑數(shù)目C來(lái)表征網(wǎng)絡(luò)的連通度：

其中：mk為長(zhǎng)度為k的閉合回路的數(shù)目。

對(duì)于節(jié)點(diǎn)i而言，若存在長(zhǎng)度為k的閉合回路，從理論上來(lái)講，該閉合回路可重復(fù)計(jì)算，故閉合回路的長(zhǎng)度k→+∞，C無(wú)法收斂；同時(shí)網(wǎng)絡(luò)閉合回路越長(zhǎng)，包含的節(jié)點(diǎn)和連接邊的數(shù)目越多，則該路徑的抗毀性越低，因此，對(duì)C引入加權(quán)系數(shù)，得到：

對(duì)于復(fù)雜網(wǎng)絡(luò)G而言，C'值越大，說(shuō)明網(wǎng)絡(luò)G的路徑冗余程度越大，連通度越高，抗毀性越強(qiáng)。圖3雙目標(biāo)作戰(zhàn)環(huán)中C'=1.393 3。采用移除節(jié)點(diǎn)和連接邊的方式，分別計(jì)算移除節(jié)點(diǎn)后其網(wǎng)絡(luò)子圖的C'值。若C'值下降程度較大，則說(shuō)明移除的節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的抗毀性影響較大，該節(jié)點(diǎn)的重要度較高，計(jì)算結(jié)果如表3所示。

表3 移除節(jié)點(diǎn)后網(wǎng)絡(luò)的值

從表3的計(jì)算結(jié)果可以看出，移除節(jié)點(diǎn)S3后網(wǎng)絡(luò)G的C'值最小，說(shuō)明在移除節(jié)點(diǎn)后網(wǎng)絡(luò)的抗毀性下降程度最大，節(jié)點(diǎn)S3是該網(wǎng)絡(luò)中重要度最高的節(jié)點(diǎn)。從網(wǎng)絡(luò)全局來(lái)看，基于譜測(cè)度理論，節(jié)點(diǎn)重要性的順序?yàn)椋?，該結(jié)果與修正PageRank算法的結(jié)果一致，說(shuō)明修正PageRank算法具備可行性。

4 結(jié)論

本文給出修正PageRank算法對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性評(píng)估的理論方法，依據(jù)作戰(zhàn)循環(huán)理論，建立雙目標(biāo)的作戰(zhàn)環(huán)，對(duì)武器裝備體系中的節(jié)點(diǎn)重要性進(jìn)行研究，并通過(guò)特征譜理論對(duì)修正PageRank算法評(píng)估結(jié)果進(jìn)行驗(yàn)證，證明了修正PageRank算法的可行性。在體系對(duì)抗過(guò)程中，可采用修正PageRank算法對(duì)武器裝備體系的裝備節(jié)點(diǎn)進(jìn)行重要性評(píng)估，采取保護(hù)自身重要節(jié)點(diǎn)和打擊敵方重要目標(biāo)的作戰(zhàn)方式，達(dá)到克敵制勝的作戰(zhàn)目標(biāo)。

［1］張強(qiáng)，李建華，沈迪，等.基于復(fù)雜網(wǎng)絡(luò)的作戰(zhàn)網(wǎng)絡(luò)建模與優(yōu)化研究 ［J］.系統(tǒng)工程與電子技術(shù)，2015，37（5）：1066-1071.

［2］倪忠仁.武器裝備體系對(duì)抗的建模與仿真［J］.軍事運(yùn)籌與系統(tǒng)工程，2004，18（1）：2-6.

［3］卜廣志.武器裝備體系的體系結(jié)構(gòu)與體系效能［J］.系統(tǒng)工程與電子技術(shù)，2006，28（10）：1544-1548.

［4］游光榮，初軍田，呂少卿，等.關(guān)于武器裝備體系研究［J］.軍事運(yùn)籌與系統(tǒng)工程，2010，24（4）：15-22.

［5］ALFREDO G，ANDREA T.On the reliability analysis of systems and SoS：the RAMSAS method and related extensions［J］.IEEE Systems Journal，2015，9（1）：232-241.

［6］ENDER T，LEURCK R F，WEAVER B，et al.Systems-of-Systems analysis of ballistic missile defense architecture effectiveness through Surrogate modeling and simulation［J］.IEEE Systems Journal，2010，4（2）：156-165.

［7］吳忠杰，張耀中，杜支強(qiáng)，等.復(fù)雜網(wǎng)絡(luò)理論下軍事體系對(duì)抗的研究進(jìn)展［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2014，11（4）：52-61.

［8］吳金閃，狄增如.從統(tǒng)計(jì)物理學(xué)看復(fù)雜網(wǎng)絡(luò)研究［J］.物理學(xué)進(jìn)展，2004，24（1）：18-46.

［9］劉濤，陳忠，陳曉榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用研究概述［J］.系統(tǒng)工程，2005，23（6）：1-7.

［10］李琳，劉稚奇.通信網(wǎng)節(jié)點(diǎn)重要性的多指標(biāo)評(píng)價(jià)方法［J］.海軍工程大學(xué)學(xué)報(bào)，2010，22（5）：69-73.

［11］李茂林，龍建國(guó)，劉偉濤.信息化條件下作戰(zhàn)體系節(jié)點(diǎn)重要性指標(biāo)的選擇［J］.火力與指揮控制，2011，36（8）：119-121.

［12］汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論［M］.北京：高等教育出版社，2015.

［13］錢(qián)功偉，倪林，MIAO Y，等.基于網(wǎng)頁(yè)鏈接和內(nèi)容分析的改進(jìn)PageRank算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（21）：160-164.

［14］CARES J R.Distributed networked operations the foundations of network centric warfare ［M］.Landeda：Alidade Press，2004：36-59.

［15］齊新社，宋曉峰，楊東升，等.基于譜測(cè)度的地域通信網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估［J］.火力與指揮控制，2012，37（7）：51-53.

［16］趙永毅，史定華.復(fù)雜網(wǎng)絡(luò)的特征譜及其應(yīng)用［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2006，3（1）：1-12.

［17］譚躍進(jìn)，張小可，楊克巍.武器裝備體系網(wǎng)絡(luò)化描述與建模方法［J］.系統(tǒng)管理學(xué)報(bào)，2012，21（6）：781-786.

［18］陸皖麟，何新華，屈強(qiáng)，等.基于SEM的武器裝備體系作戰(zhàn)能力關(guān)聯(lián)關(guān)系判定方法［J］.兵器裝備工程學(xué)報(bào)，2016，36（8）：38-42.

Evaluating Nodes Importance in Equipment System-of-Systems Based on PageRank Algorithm

LI Kai1，WU Wei1，LIU Fu-sheng1，CHEN Geng-shen2，CHEN Shou-hua1
（1.Academy of Armored Force Engineering，Beijing 100072，China；2.Logistics Academy，Beijing 100858，China）

To research the equipment System-of-Systems based on the complex network theory，the equipment systems are regarded as the nodes in the network.In this paper，the nodes importance in equipment System-of-Systems is evaluated based on the amendatory PageRank algorithm to avoid the deficiencies of the basic PageRank algorithm.The amendatory PageRank algorithm possess convergence with dangling node and directed circular network.The simulation results show the amendatory PageRank algorithm could be used to evaluate the nodes importance for two targets combat circle.Finally the results of the nodes importance is conformed based on the spectral measure and node removed process to assess theinvulnerability of the network.

PageRank algorithm，equipment system-of-systems，complex network，nodes importance

E917

A

10.3969/j.issn.1002-0640.2017.11.08

1002-0640（2017）11-0034-04

2016-09-21

2016-11-09

裝備技術(shù)基礎(chǔ)基金資助項(xiàng)目（2015H04）

李 鍇（1990- ），男，山東淄博人，博士研究生。研究方向：武器裝備體系建模仿真及評(píng)估。