基于TOPSIS的裝備保障網絡節(jié)點重要性綜合評價方法

邢 彪， 曹軍海， 宋太亮， 陳守華， 董原生

(1. 裝甲兵工程學院技術保障工程系， 北京 100072； 2. 中國國防科技信息中心， 北京 102205)

?

基于TOPSIS的裝備保障網絡節(jié)點重要性綜合評價方法

邢 彪1， 曹軍海1， 宋太亮2， 陳守華1， 董原生1

(1. 裝甲兵工程學院技術保障工程系， 北京 100072； 2. 中國國防科技信息中心， 北京 102205)

針對復雜網絡拓撲結構分布的不均勻性導致單一指標難以準確反映網絡中節(jié)點重要程度的問題，將網絡的每個節(jié)點作為1個方案，將節(jié)點重要性評價指標作為描述方案的屬性，從節(jié)點度指標、介數指標、刪除指標、接近中心性指標和子圖指標5個方面，采用改進的逼近理想解排序法(Technique for Order Preference by Similarity to an Ideal Solution, TOPSIS)對網絡節(jié)點的重要性進行綜合評價，計算每個方案到理想方案的接近度，并按由大到小的順序進行排序，得出節(jié)點重要性綜合評價結果。最后,以某裝備保障網絡實例對該方法的可行性和有效性進行了驗證。

復雜網絡； 裝備保障； 節(jié)點重要性； 多屬性決策； 逼近理想解排序法(TOPSIS)

復雜網絡均具有非均勻性，其核心節(jié)點的確定對于分析復雜網絡的性質具有非常重要的現實意義[1]。近年來，有關尋找復雜網絡中重要節(jié)點和節(jié)點重要性評價的研究，一直都是復雜網絡研究的熱點和難點問題之一[2-3]。

從算法上看，從復雜網絡中抽取重要節(jié)點，采用定性與定量相結合的分析方法確定網絡中的重要節(jié)點，實質上是對有關節(jié)點重要性評價標準和依據問題的研究。節(jié)點中心化指標[4]作為刻畫節(jié)點重要程度的關鍵指標大致可分為2類： 1)認為節(jié)點在網絡中的重要度取決于該節(jié)點與其他節(jié)點的鄰近程度，如度、中心性等；2)認為節(jié)點的重要度依賴于該節(jié)點所處的位置對其他節(jié)點之間信息聯絡的影響程度，如介數等。此外，Everett等[5]將度、緊密度和介數3種指標推廣為群組中心化指標，以適應社團的重要性評價。

在節(jié)點重要性評價方法方面，主要有基于節(jié)點刪除方法[6]、基于節(jié)點之間直接連接狀態(tài)[7]、網絡結構和傳播動力學[8]、節(jié)點收縮法[9]、信息指標[10]、PageRank算法[11]和HITS算法[12]等。以上方法均是針對不同網絡的實際問題，分別從不同角度刻畫節(jié)點在網絡中的重要性，并提出解決方法，因此，均有其自身的優(yōu)點和局限性。1)基于度的節(jié)點重要性評價方法依據節(jié)點與其相鄰節(jié)點相連的邊數來評價節(jié)點的重要性。但對于以下2種情況該方法并不適用：一是網絡中度值相同的節(jié)點其重要度不一定相同；二是雖然網絡中某一節(jié)點度值不高但是卻很重要，如連接不同局域網絡的唯一節(jié)點就屬于這類節(jié)點。2)基于介數的節(jié)點重要性評價方法強調節(jié)點或邊對網絡信息的控制能力，一般采用最短路徑來定義節(jié)點的重要度，但不適用于解決一些實際網絡中信息不一定按照最短路徑來流動的網絡節(jié)點重要性評價問題。3)PageRank算法強調節(jié)點被連接的次數，尤其是被重要節(jié)點連接的次數，但無法解決存在源節(jié)點和終端節(jié)點的網絡節(jié)點重要性評價問題。

針對單一指標在評價網絡節(jié)點重要性中存在的局限性問題，筆者將網絡中的每個節(jié)點作為1個方案，應用節(jié)點重要性評價指標來描述方案的屬性，從多個角度考慮多重因素，采用相似距離改進的逼近理想解排序法(Technique for Order Preference by Similarity to an Ideal Solution, TOPSIS)對網絡節(jié)點的重要性進行綜合評價，得出更加符合客觀實際的綜合評價結果，并進行了實例分析及驗證。

1 節(jié)點重要性指標定義與說明

基于復雜網絡理論將各保障實體抽象為節(jié)點，實體間的交互關系抽象為邊。

1.1 節(jié)點及邊

1)定義vi為第i(i=1,2，…，N)個節(jié)點。裝備保障網絡中主要的保障實體有：各級作戰(zhàn)單位相對應的保障指揮機關、各級器材倉庫、各基層修理分隊和運輸分隊等，則V={v1,v2,…,vN}，為節(jié)點集合，其中N為網絡節(jié)點數。

2)定義el為第l(l=1,2,…,M)條邊，表示節(jié)點vi和vj的交互關系，具體為各保障實體間的傳輸路徑和傳輸信息，則E={e1,e2,…,eM}，為邊集合，其中M為網絡邊數。

1.2 節(jié)點重要性指標

1)網絡局部屬性——度指標

度是網絡拓撲結構的基本參數，可表示節(jié)點在網絡中與周圍鄰近節(jié)點建立直接聯系的能力。設ki為節(jié)點i的度，即與節(jié)點vi直接相連的節(jié)點數。若在有N個節(jié)點的網絡中，ki≤N-1，則歸一化的節(jié)點度指標為

(1)

從網絡局部屬性來看，度值越大表示節(jié)點越重要。在裝備保障網絡中指揮子網絡是典型的垂直樹狀網絡，軍、師(旅)、團、營、連各級保障節(jié)點存在嚴格的指揮隸屬關系，每級的保障指揮節(jié)點均需連接本級下屬的所有保障子節(jié)點。因此，節(jié)點度可較好地反映裝備保障網絡中的保障指揮節(jié)點的重要程度，級別越高越重要，節(jié)點度值也越大。

2)網絡傳播屬性——介數指標

介數指標側重于度量網絡中節(jié)點對信息流動的影響力。節(jié)點vi的介數為

(2)

式中：gst(vi)為節(jié)點vs和vt之間最短路徑經過節(jié)點vi的條數；nst為節(jié)點vs和vt之間的最短路徑條數。對于給定節(jié)點vi，若存在maxCb(vi)=(N-1)×(N-2)/2，則歸一化節(jié)點介數指標為

(3)

從網絡傳播屬性來看，若某一節(jié)點為網絡中其他節(jié)點對之間通信的必經之路，則該節(jié)點在網絡中十分重要。在裝備保障網絡中普遍存在用于連接各子網絡(如維修保障子網絡、供應保障子網絡和保障指揮子網絡等)的節(jié)點，其中以各級保障運輸節(jié)點(修理連)為主，負責為各具體基層維修機構提供保障資源，是連接維修子網絡與供應子網絡之間通信的必經之路。有時也稱這類節(jié)點為“橋”節(jié)點，適合采用介數來分析計算。

3)網絡連接屬性——節(jié)點刪除指標

節(jié)點刪除指標是通過網絡的連通性來反映網絡某種功能的完整性。定義節(jié)點vi刪除前后，網絡最大連通分支上節(jié)點數量之比作為衡量節(jié)點vi的重要度指標，即

(4)

當裝備保障網絡為完成規(guī)定的保障任務需要某些保障實體共同協作時，節(jié)點刪除指標是從宏觀角度來分析某一節(jié)點刪除后對網絡整體效能的影響，該類節(jié)點即使只刪除1個，也會影響網絡某種功能的完整性。

4)網絡全局屬性——接近中心性指標

(5)

接近中心性指標可衡量裝備保障網絡不同地理位置上的節(jié)點重要程度，對應節(jié)點在網絡中所在的位置，更能反映網絡的全局結構。

5)網絡耦合關系——子圖指標

子圖指標是對度指標的擴展，在延續(xù)度指標側重節(jié)點直接連接關系的同時，考慮了2次(通過某一節(jié)點連接)及2次以上的連接，保證了直接連接的節(jié)點具有較大權重。具體計算方法為：計算從1個節(jié)點開始到該節(jié)點結束的閉環(huán)回路的數目，1個閉環(huán)表征網絡中的1個子圖。該方法可衡量節(jié)點參與不同子圖的數目，并可通過對子圖賦予不同的權重來表示節(jié)點間重要程度的差異。子圖指標為

(6)

式中：μn(vi)為以節(jié)點vi為起點經n個連接邊重新回到節(jié)點vi的閉環(huán)回路數。定義閉環(huán)回路對節(jié)點重要性的影響隨長度的增加而遞減。

不難看出：以上5個指標均是從某一角度來衡量節(jié)點在網絡中的重要性。對于實際的裝備保障網絡，僅應用某一指標進行節(jié)點重要性評價其結果具有很大的局限性。

2 節(jié)點重要性綜合評價與分析

TOPSIS是通過對評價對象與最優(yōu)目標的接近度的排序，將最接近正理想方案同時遠離負理想方案的解作為最優(yōu)解。基于TOPSIS的多屬性決策方法是將網絡中的每個節(jié)點作為1個方案，采用多個評價指標來描述節(jié)點(方案)的屬性，進而將節(jié)點重要性綜合評價問題轉化為多屬性決策問題。

1)計算歸一化決策矩陣

設A={A1,A2,…,AN}，為方案集合；S={S1,S2,…,Sm}，為方案屬性集合，其中m為評價指標數；Ai(Sj)為第i個節(jié)點的第j(j=1,2,…,m)個指標的評價值，則決策矩陣X為

(7)

對決策矩陣X進行歸一化處理，可得歸一化決策矩陣T為

T=[tij]N×m,tij=Ai(Sj)/Ai(Sj)max，

(8)

2)確定理想方案

設W=[w1w2…wm],為指標權重向量，則加權規(guī)范化矩陣Y為

(9)

根據Y確定正理想方案Y+和負理想方案Y-分別為

(10)

(11)

3)計算接近度

傳統方法采用歐氏距離來計算每個評價方案Ai到正理想方案Y+和負理想方案Y-的距離，即

(12)

(13)

由于這種方法未考慮位于正理想方案與負理想方案垂線上的評價方案，同時為了提高評價方案的靈敏度，筆者引入相對距離對歐氏距離進行改進，即

(14)

(15)

則所評價方案與理想方案的接近度Zi為

(16)

3 實例分析

以典型的基層修理分隊(修理連)為例，驗證筆者所提方法的可行性和有效性。圖1為以修理連為中心的裝備保障網絡拓撲結構，其中：節(jié)點1泛指上級裝備保障指揮機關(軍師、旅、團等)；節(jié)點2為修理營營部；節(jié)點3為修理連連部；節(jié)點4為本級所屬汽車連；節(jié)點5、6分別為本級和上級裝備器材倉庫；節(jié)點7-10為修理連下屬的4個能夠完成規(guī)定保障任務的保障單元，且節(jié)點1、2分別連接2個保障單元，表示團級和營級存在可直接支配該保障單元進行機動保障的連接關系。各節(jié)點的節(jié)點度指標、介數指標、節(jié)點刪除指標、接近中心性指標和子圖指標的計算結果如表1所示。

由圖1和表1可以看出：在該網絡中，節(jié)點3的節(jié)點度和子圖指標最大；節(jié)點4的介數最大；節(jié)點1-3和節(jié)點6-10具有相同的節(jié)點刪除指標；節(jié)點1、2擁有最大的接近中心性指標。

圖1 以修理連為中心的裝備保障網絡拓撲結構示例

表1 以修理連為中心的裝備保障網絡各節(jié)點指標的計算結果

由表1可得決策矩陣X，利用層次分析法(Analytic Hierarchy Process，AHP)確定各指標的權重。首先，依據式(17)對各指標進行兩兩比較，構建比較矩陣B=[bij]5×5，如表2所示，其中

bij=2, 指標i比指標j重要；1, 指標i與指標j相同；0, 指標j比指標i重要。

(17)

表2中各指標重要性比較說明：節(jié)點度指標考慮網絡結構最少，且子圖指標某種程度上可看作是節(jié)點度指標的擴展，因此設定節(jié)點度指標的重要性最低，子圖指標的重要性最高；介數指標是唯一考慮網絡信息影響的指標，適用于度量裝備保障各子網絡的連接關系，可發(fā)現網絡中的橋節(jié)點，因此定義介數指標重要性也為最高；節(jié)點刪除指標和接近中心性指標的重要程度相同，屬于一般重要。

表2 指標重要性比較矩陣

其次，依據比較矩陣B構建判斷矩陣，求解判斷矩陣并經過一致性檢驗得到各指標的權重為wCD=0.057 6，wCR=wCC=0.137 9，wCB=wCS=0.333 3。由式(8)可得歸一化決策矩陣T，由式(9)可得加權規(guī)范化矩陣Y為

(18)

由式(10)、(11)，可得正理想方案Y+和負理想方案Y-分別為

(19)

(20)

表3 以修理連為中心的裝備保障網絡評價結果

由表3可以看出：傳統的TOPSIS法與改進TOPSIS法所得接近度Zi的排序均為

(Z1=Z2)>Z4>Z3>Z5>
(Z8=Z9)>(Z7=Z10)>Z6。

(21)

式(21)表明：1)傳統TOPSIS法與改進TOPSIS法得到的節(jié)點重要性排序結果一致；2)節(jié)點1、2在以修理連為中心的裝備保障網絡中位置相同，具有相同的節(jié)點重要性，且節(jié)點1、2的刪除會直接導致網絡中通信距離的增大，故重要性最高；節(jié)點4的刪除會導致修理子網絡與供應子網絡不再連通，故重要性次之；節(jié)點3是整個修理連的指揮中樞，具有最大的度值，但也應看到由于機動保障單元的存在，節(jié)點3的刪除一定程度上可使網絡通信冗余減少，團、營等上級機關直接指揮機動保障單元增大了網絡的傳輸效率，故節(jié)點3的重要性次于節(jié)點1、2、4；節(jié)點5是介數值最大的點，刪除節(jié)點5會導致上級器材倉庫斷開，重要性再次之；最后，剩余的其他節(jié)點的刪除都不會對網絡的連通性產生影響，其重要性更低。

通過以上分析可知：筆者提出的基于TOPSIS的節(jié)點重要性綜合評價方法，對以修理連為中心的裝備保障網絡進行評價效果良好，能夠較好地區(qū)分不同節(jié)點的重要程度，避免了單一評價指標的不足。為了更好地說明本文所提方法的可行性與有效性，筆者以某集團軍所屬的裝備保障力量為研究對象，分析其與裝備保障有關的各組織機構的運行過程，得出軍級裝備保障體系網絡的運行機制和指揮流程[13]，如圖2所示，對其進行網絡化抽象后建立軍級裝備保障體系結構的復雜網絡模型，如圖3所示。

圖2 軍級裝備保障體系網絡的運行機制和指揮流程

應用本文提出的改進TOPSIS法對軍級裝備保障網絡中各節(jié)點的重要性進行綜合評價，評價結果及排序如表4所示，并對傳統TOPSIS法與改進TOPSIS法計算的節(jié)點重要性綜合評價值進行了比較，結果如圖4所示。

由表4可知：軍級裝備保障網絡中排名在前10%的節(jié)點為：軍級(以及下屬的師旅級)裝備保障指揮機關、軍級(以及下屬的師旅級)器材倉庫、軍級修理營和軍級機動保障分隊等，這符合裝備保障的實際情況。由圖4可知：傳統TOPSIS法與改進TOPSIS法得到的節(jié)點重要性排序結果基本一致，但改進TOPSIS法的整體靈敏性更好，如：對于節(jié)點31-70(31-36，37-41，42-46等)的節(jié)點重要性評價，歐氏距離不能很好地進行區(qū)分，而相似距離可很容易地區(qū)分這類局部相似的節(jié)點重要性，尤其是針對裝備保障網絡中最底層的基本保障單元，其評價優(yōu)勢更為突出。

圖3 軍級裝備保障體系結構的復雜網絡模型

表4 基于改進TOPSIS法的軍級裝備保障網絡節(jié)點重要性綜合評價值及排序

圖4 基于傳統和改進TOPSIS法的軍級裝備保障網絡中各節(jié)點重要性評價值對比

4 結論

目前，復雜網絡理論已成為研究復雜系統和網絡問題的有效方法，復雜網絡中節(jié)點重要性的研究在實際應用中具有重要意義，但現有的評價指標如度、介數等均存在應用范圍的局限性，研究網絡中節(jié)點的重要性必須考慮多重因素的影響。筆者采用改進的TOPSIS方法對網絡節(jié)點的重要性進行綜合評價，并針對傳統的歐氏距離計算方法進行了改進，該方法計算簡單、易于擴展。本文的研究成果也可為進一步分析裝備保障網絡的可靠性和抗毀性提供決策支持。

[1] 中華人民共和國國務院新聞辦公室. 2016年中國國防白皮書[R].北京：新華社,2015：2-4.

[2] ALBERT R,NAKARADO G L.Structural vulnerability of the North American power grid[J].Physical review E,2004,69(2):025103.

[3] ZHANG Y,LIU Y H.Modeling of scale-free network based on pagerank algorithm[C]∥ICFCC 2010.Wuhan,China:IEEE computer society,2010,V3:778-782.

[4] 孫璽菁,司守奎.復雜網絡算法與應用[M].北京:國防工業(yè)出版社,2015:214-219.

[5] EVERETT M,BORGATTI S P.The centrality of groups and class-es[J].Journal of mathematical sociology,1999,23(1):181-201.

[6] 李旭源,羅澤,閻保平.一種基于節(jié)點刪除法的候鳥棲息地重要性評估方法研究與實現[J].計算機應用研究,2015,32(2):409-412.

[7] KITSAK M,GALLOS L K,HAVLIN S,et al.Identification of influential spreaders in complex networks[J].Nat Phys,2010,6(1):888-893.

[8] POULIN R,BOILY M C,MASSE B R.Dynamical systems to define centrality in social networks[J].Social networks,2000,5(22):187-220.

[9] CHEN Y,HUA Q,HU J.A method for finding the most vital node in communication networks[J].High technology letters,2004,15(1):573-575.

[10] ZHAO P,ZHANG Y,QIAN W P.Investigation of geiger-mode detector in multi-hit model for laser ranging[J].Science China(Technological sciences),2015,58(5):943-950.

[11] PAGE L,BRIN S,MOTWANI R,et al.The Pagerank citation ranking: bringing order to the web[R/OL].(1998-01-29)[2016-10-18].http:∥ilpubs.stanford.edu: 8090/422/.

[12] 劉小弟,朱建軍,張世濤,等.考慮屬性權重優(yōu)化的猶豫模糊多屬性決策方法[J].控制與決策,2016,31(2): 297-302.

[13] 邢彪,曹軍海,宋太亮,等.基于復雜網絡的裝備保障體系建模方法[J].裝甲兵工程學院學報,2016,30(2):12-15.

(責任編輯: 王生鳳)

Synthesis Evaluation Method for Network Node Importance in Equipment Support Based on TOPSIS

XING Biao1, CAO Jun-hai1, SONG Tai-liang2, CHEN Shou-hua1, DONG Yuan-sheng1

(1. Department of Technical Support Engineering, Academy of Armored Force Engineering, Beijing 100072, China;2. China National Defense Science and Technology Information Center, Beijing 102205, China)

According to the problem of the inhomogeneity of the complex network topology will lead to a failure that a single index cannot accurately reflect the degree of node importance in the network, each node in the network is taken as one program, the evaluation index of node importance are taken as the program attribute in this paper. The improved method of Technique for Order Preference by Similarity to an Ideal Solution (TOPSIS) is used to evaluate the node importance from five indicators such as node degree, betweenness, deleting index, close to center and sub-graph. The approximate degree of each scheme to the ideal scheme is calculated and sorted according to the order from large to small, and the comprehensive evaluation results of node importance are obtained. Finally, the feasibility and effectiveness of the proposed method are verified by an example of an equipment support network.

complex network; equipment support; node importance; multi-attribute decision; Technique for Order Preference by Similarity to an Ideal Solution(TOPSIS)

1672-1497(2017)03-0028-07

2017-01-10

軍隊科研計劃項目

邢 彪(1988-)，男，博士研究生。

E92; TP393.02

A

10.3969/j.issn.1672-1497.2017.03.006