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

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

?

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

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

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

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

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

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

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

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

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

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

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

1.1 節(jié)點及邊

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

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

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

1)網(wǎng)絡局部屬性——度指標

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

(1)

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

2)網(wǎng)絡傳播屬性——介數(shù)指標

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

(2)

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

(3)

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

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

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

(4)

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

4)網(wǎng)絡全局屬性——接近中心性指標

(5)

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

5)網(wǎng)絡耦合關(guān)系——子圖指標

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

(6)

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

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

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

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

1)計算歸一化決策矩陣

設A={A1,A2,…,AN}，為方案集合；S={S1,S2,…,Sm}，為方案屬性集合，其中m為評價指標數(shù)；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],為指標權(quán)重向量，則加權(quán)規(guī)范化矩陣Y為

(9)

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

(10)

(11)

3)計算接近度

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

(12)

(13)

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

(14)

(15)

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

(16)

3 實例分析

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

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

圖1 以修理連為中心的裝備保障網(wǎng)絡拓撲結(jié)構(gòu)示例

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

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

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

(17)

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

表2 指標重要性比較矩陣

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

(18)

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

(19)

(20)

表3 以修理連為中心的裝備保障網(wǎng)絡評價結(jié)果

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

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

(21)

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

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

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

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

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

圖3 軍級裝備保障體系結(jié)構(gòu)的復雜網(wǎng)絡模型

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

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

4 結(jié)論

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

[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] 孫璽菁,司守奎.復雜網(wǎng)絡算法與應用[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é)點刪除法的候鳥棲息地重要性評估方法研究與實現(xiàn)[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] 劉小弟,朱建軍,張世濤,等.考慮屬性權(quán)重優(yōu)化的猶豫模糊多屬性決策方法[J].控制與決策,2016,31(2): 297-302.

[13] 邢彪,曹軍海,宋太亮,等.基于復雜網(wǎng)絡的裝備保障體系建模方法[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