基于改進(jìn)融合算法的交通網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估

孫興龍，李亞雄，邱艷粉

（火箭軍工程大學(xué)作戰(zhàn)保障學(xué)院，西安 710025）

0 引言

對于網(wǎng)絡(luò)化目標(biāo)體系，目標(biāo)的價值主要體現(xiàn)在個體目標(biāo)固有價值和作為網(wǎng)絡(luò)節(jié)點(diǎn)的目標(biāo)體系價值。固有價值與目標(biāo)節(jié)點(diǎn)周圍的資源配置有關(guān)，且固有價值與目標(biāo)網(wǎng)絡(luò)體系價值的評價方法不同。本文只對目標(biāo)的網(wǎng)絡(luò)體系價值作出研究。

交通體系網(wǎng)絡(luò)模型包括公路網(wǎng)、鐵路網(wǎng)、航空網(wǎng)組成，是典型的多層復(fù)雜網(wǎng)絡(luò)模型。目前，對于評估多層交通網(wǎng)絡(luò)節(jié)點(diǎn)重要性，很少有考慮邊的權(quán)重，事實(shí)上每條路徑的運(yùn)載能力區(qū)別很大，權(quán)重不可忽略。對于多層復(fù)雜網(wǎng)絡(luò)的研究分為兩個方面。一是分析網(wǎng)絡(luò)的統(tǒng)計(jì)特性，包括聚類系數(shù)、特征向量、度中心性、介數(shù)中心性；二是對復(fù)雜網(wǎng)絡(luò)進(jìn)行建模［1-2］，尋找網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)以及失去關(guān)鍵節(jié)點(diǎn)產(chǎn)生的連鎖反應(yīng)或者網(wǎng)絡(luò)損失［3］。

由于對多層復(fù)雜網(wǎng)絡(luò)的研究剛剛興起，因此，對于多層復(fù)雜網(wǎng)絡(luò)評估方法較少，目前比較成熟的是隨機(jī)游走介數(shù)評估和鄰接中心性評估［4-5］。但是這兩種方法在評估的過程中忽略了節(jié)點(diǎn)對網(wǎng)絡(luò)全局的影響，很難準(zhǔn)確反映不同節(jié)點(diǎn)之間的連接價值，導(dǎo)致最終評估結(jié)果的偏差，而且對于節(jié)點(diǎn)數(shù)和層數(shù)較多的網(wǎng)絡(luò)，難以反映節(jié)點(diǎn)間的細(xì)小差距，節(jié)點(diǎn)評估準(zhǔn)確性難以保證。此外，還有人提出余弦相似度的評估方法［6］，然而這種方法忽略了復(fù)雜網(wǎng)絡(luò)中不同節(jié)點(diǎn)之間的權(quán)重信息，導(dǎo)致評估模型與實(shí)際網(wǎng)絡(luò)符合度相距甚遠(yuǎn)。

2）構(gòu)建距離矩陣。在拆解過程中，逐一計(jì)算每個單層網(wǎng)絡(luò)的距離矩陣。

3）構(gòu)建關(guān)聯(lián)矩陣。根據(jù)兩兩節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系和路徑權(quán)重系數(shù)按照一定算法得到關(guān)聯(lián)矩陣。

4）構(gòu)建基本概率分配矩陣。根據(jù)計(jì)算規(guī)則得到任意兩個節(jié)點(diǎn)的基本概率分配函數(shù)（Basic Probability Assignment Functions 簡稱BPA）。

5）融合各層基本概率分配函數(shù)。將各層BPA矩陣?yán)肈-S 證據(jù)理論（不確定性證據(jù)理論）進(jìn)行數(shù)據(jù)融合。

6）BPA 概率轉(zhuǎn)換。運(yùn)用賭博概率轉(zhuǎn)換算法（Pignistic Probability Ttansformation，簡稱PPT 算法）最終得到節(jié)點(diǎn)重要度指標(biāo)。

該算法框架如圖1 所示。

1 基于融合算法的網(wǎng)絡(luò)節(jié)點(diǎn)評估方法

1.1 模型建立的步驟

針對以上問題，本文提出一種考慮權(quán)重和網(wǎng)絡(luò)整體影響融合算法對加權(quán)多層交通網(wǎng)絡(luò)節(jié)點(diǎn)重要性進(jìn)行評估，該方法步驟如下：

1）將多層網(wǎng)絡(luò)拆解為多個單層網(wǎng)絡(luò)。根據(jù)多層復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)組成關(guān)系將其拆解為多個單層網(wǎng)絡(luò)。

圖1 融合算法流程圖

交通網(wǎng)絡(luò)包含公路網(wǎng)、鐵路網(wǎng)、航空網(wǎng)，是一類典型的各層節(jié)點(diǎn)相同，每層節(jié)點(diǎn)的連接關(guān)系不同的多層網(wǎng)絡(luò)，是NON 網(wǎng)絡(luò)（Network of Networks）的一種。

圖2 交通網(wǎng)絡(luò)拆解過程

圖2 中所示的即為多層交通網(wǎng)絡(luò)的示意圖。圖（a）所示的局部交通網(wǎng)絡(luò)拆解結(jié)構(gòu)圖，不同網(wǎng)絡(luò)層的相同節(jié)點(diǎn)互相連接，圖（b）是整個多層網(wǎng)絡(luò)示意圖，圖（c）、圖（d）、圖（e）是拆解后的單層復(fù)雜網(wǎng)絡(luò)。

1.2 構(gòu)建距離矩陣

對于一個具有n 個節(jié)點(diǎn)的多層網(wǎng)絡(luò)，可得一個多層網(wǎng)絡(luò)拆解后的每個單層網(wǎng)絡(luò)的距離矩陣D 具體如下：

其中，dij表示節(jié)點(diǎn)i 與節(jié)點(diǎn)j 的最短路徑長度。對于現(xiàn)實(shí)交通網(wǎng)絡(luò)，其網(wǎng)絡(luò)結(jié)構(gòu)十分復(fù)雜，一般不存在不相連的兩個節(jié)點(diǎn)。

1.3 構(gòu)建關(guān)聯(lián)度矩陣

關(guān)聯(lián)度矩陣的構(gòu)建是節(jié)點(diǎn)評估準(zhǔn)確性的關(guān)鍵。本文提出了一種基于關(guān)聯(lián)度矩陣的基本概率分配構(gòu)建方法。網(wǎng)絡(luò)中節(jié)點(diǎn)間的關(guān)聯(lián)度矩陣S 定義如下：

定義節(jié)點(diǎn)i 與節(jié)點(diǎn)j 的直接關(guān)聯(lián)度sij為節(jié)點(diǎn)i與節(jié)點(diǎn)j 之間的最短路徑dij在整個網(wǎng)絡(luò)的價值。而網(wǎng)絡(luò)中節(jié)點(diǎn)i 與節(jié)點(diǎn)j 之間的關(guān)聯(lián)度sij不僅與兩個節(jié)點(diǎn)之間的最短路徑dij相關(guān)，還與網(wǎng)絡(luò)中其他節(jié)點(diǎn)相關(guān)。例如，當(dāng)dij的某一部分是節(jié)點(diǎn)m 和n 的最短路徑dmn的子集，失去節(jié)點(diǎn)i 與節(jié)點(diǎn)j 之間最短路徑dij后，會對網(wǎng)絡(luò)中節(jié)點(diǎn)m 和n 的最短路徑產(chǎn)生影響，可能會導(dǎo)致最短路徑變大或者不存在連通路徑。

此外，關(guān)聯(lián)度還與節(jié)點(diǎn)之間的信息傳遞能力有關(guān)，對于公路網(wǎng)絡(luò)信息傳遞能力就是運(yùn)載能力。例如，高速公路和普通路的運(yùn)載能力是不同的，路寬車道也是不同的，這些因素對于連通價值影響很大。

根據(jù)復(fù)雜網(wǎng)絡(luò)鄰接矩陣的定義，在一個具有n個節(jié)點(diǎn)的加權(quán)網(wǎng)絡(luò)中，鄰接矩陣權(quán)重wij為：

對于不同的交通網(wǎng)絡(luò)其網(wǎng)絡(luò)中節(jié)點(diǎn)之間的運(yùn)送效率有著顯著的區(qū)別，在多層交通網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)i 與j 之間運(yùn)輸效率由每層節(jié)點(diǎn)i 與j 之間邊共同決定，運(yùn)輸效率主要由時間成本、經(jīng)濟(jì)成本、運(yùn)載能力等因素構(gòu)成。考慮到這些因素在交通網(wǎng)絡(luò)中定義鄰接連通矩陣權(quán)重為：

其中，運(yùn)載能力定義為pij是根據(jù)鄰接節(jié)點(diǎn)的交通情況而定，相關(guān)數(shù)據(jù)可根據(jù)交通網(wǎng)站查詢得到。pmax為單層網(wǎng)絡(luò)中運(yùn)載能力的最大值。特別地，當(dāng)節(jié)點(diǎn)i 與j 在網(wǎng)絡(luò)中不相連時，wij為0。

節(jié)點(diǎn)i 與節(jié)點(diǎn)j 在最短路徑上的關(guān)聯(lián)度sij為：

其中，N 是最短路徑數(shù)量。

以上分析是基于分解后的單層網(wǎng)絡(luò)，對于實(shí)際多層網(wǎng)絡(luò)，不同層級之間的交叉影響也不可忽略，這也是目前對多層網(wǎng)絡(luò)分析被忽略的敵方。本文考慮了不同單層網(wǎng)絡(luò)之間的交叉影響，更符合實(shí)際網(wǎng)絡(luò)特點(diǎn)。

在單層網(wǎng)絡(luò)不連通的節(jié)點(diǎn)可以通過多層網(wǎng)絡(luò)轉(zhuǎn)換線路得到連通路徑或者縮短路徑距離。因此，在圖2 網(wǎng)絡(luò)（b）中，任意兩個節(jié)點(diǎn)之間有至少一條路徑連通，則合并成一條通路，如（f）所示，然后只把合并后的網(wǎng)絡(luò)中兩個節(jié)點(diǎn)路徑距離比任意單層網(wǎng)絡(luò)（c）（d）（e）中距離都近的路徑保留，得到網(wǎng)絡(luò)（g）。例如，對于圖2 中，在任意一個單層網(wǎng)絡(luò)中節(jié)點(diǎn)1和8 的最短路徑都不小于3，但在多層網(wǎng)絡(luò)中可以在（c）中經(jīng)節(jié)點(diǎn)2 在通過（d）到達(dá)節(jié)點(diǎn)8，其距離比單層網(wǎng)絡(luò)小得多，尤其對于路徑很長的網(wǎng)絡(luò)，多層網(wǎng)絡(luò)之間的轉(zhuǎn)換有利于提高運(yùn)輸效率。但是對于不同交通方式的轉(zhuǎn)換同樣會消耗時間和成本，路徑距離越長這種轉(zhuǎn)換的影響會越低。本文假設(shè)轉(zhuǎn)換一次運(yùn)輸效率減少為合并路徑效率的一半。

1.4 基本概率分配的構(gòu)建

在融合算法計(jì)算的過程中，基本概率分配矩陣的構(gòu)建十分關(guān)鍵。目前主要有基于模糊集合［7-8］的方法，基于K-NN 分類器［9］的方法，基于神經(jīng)網(wǎng)絡(luò)的方法等。針對交通系統(tǒng)多層網(wǎng)絡(luò)評估的模型，本文運(yùn)用了一種基于關(guān)聯(lián)度矩陣的基本概率分配構(gòu)建方法［10］，構(gòu)建方法定義如下：

對于一個n×n 的關(guān)聯(lián)度矩陣S，n 是網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量，該研究背景下命題的辨識框架為：

在該命題上的辨識框架的冪集為：

其中，Y 代表兩節(jié)點(diǎn)相關(guān)，N 代表兩節(jié)點(diǎn)無關(guān)，Y，N代表著不確定相關(guān)性。

其中，Sij代表節(jié)點(diǎn)i 與j 的關(guān)聯(lián)度，min（S）是最小值。

由此得到整個網(wǎng)絡(luò)的基本概率分配矩陣MBPA：

其中，

其中，

1.5 基于BPA 矩陣的數(shù)據(jù)融合

其中，

2）將tij與cij用同樣方法融合，結(jié)果為lij：

將3 個矩陣中的所有元素按照上述方法融合得到最終BPA 矩陣MNON如下：

其中，

1.6 概率轉(zhuǎn)換算法

為了對多層交通網(wǎng)絡(luò)體系進(jìn)行準(zhǔn)備評估，需要將最終的BPA 矩陣MNON轉(zhuǎn)換為關(guān)聯(lián)度矩陣。這里運(yùn)用上述PPT 算法，該算法計(jì)算過程如下：

轉(zhuǎn)化后的關(guān)聯(lián)度矩陣RNON為：

其中，rij的轉(zhuǎn)換如下：

最終計(jì)算每個節(jié)點(diǎn)與其他各節(jié)點(diǎn)的關(guān)聯(lián)度Si：

2 實(shí)例分析

下面通過對局部多層交通網(wǎng)絡(luò)模型圖2 中的節(jié)點(diǎn)評估過程進(jìn)行實(shí)例分析。

根據(jù)D-S 證據(jù)理論的組合規(guī)則，得到融合后的基本概率分配矩陣，利用PPT 算法，將融合后所得到的BPA 矩陣進(jìn)行概率轉(zhuǎn)換，最終得到多層交通網(wǎng)絡(luò)的關(guān)聯(lián)度矩陣RNON：

最后計(jì)算關(guān)聯(lián)度矩陣RNON每一行的元素之和，即為該節(jié)點(diǎn)在多層交通網(wǎng)絡(luò)的關(guān)聯(lián)度Ic：

圖4 是4 種不同方法得到的該交通網(wǎng)絡(luò)節(jié)點(diǎn)重要度的柱狀圖，可以看出度中心性算法、臨近中心性算法、隨機(jī)游走介數(shù)算法得出的節(jié)點(diǎn)重要度區(qū)間范圍很小，而改進(jìn)的融合算法相對區(qū)間范圍較大。

表1 4 種方法重要度評估結(jié)果

表2 4 種方法評估節(jié)點(diǎn)重要度排序

圖4 4 種方法節(jié)點(diǎn)評估重要度

從圖4 中4 種算法所得節(jié)點(diǎn)重要度的柱狀圖可以看出，臨近中心算法和度中心性算法的結(jié)果極差較小，對節(jié)點(diǎn)重要性評估結(jié)果不敏感，誤差較大。通過圖4 對比可以看出，隨機(jī)游走介數(shù)算法與改進(jìn)的融合算法結(jié)果各節(jié)點(diǎn)總體相對重要程度相似，但如表2 所示，隨機(jī)游走算法同樣極差區(qū)間過小，對節(jié)點(diǎn)的相對重要性體現(xiàn)不明顯，隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增加，隨機(jī)游走介數(shù)算法評估準(zhǔn)確性也會不斷降低，而本文改進(jìn)的融合算法能夠體現(xiàn)節(jié)點(diǎn)之間的差別，區(qū)分精度更高。

對比其他算法，本文的融合算法將節(jié)點(diǎn)8 和3的價值評價較高，而節(jié)點(diǎn)6 和7 的價值較低，與其他算法區(qū)別較大。為了驗(yàn)證本文算法的有效性，引入網(wǎng)絡(luò)效率的概念。

在實(shí)際網(wǎng)絡(luò)中，信息以網(wǎng)絡(luò)的邊為載體進(jìn)行節(jié)點(diǎn)之間的信息交換。對于交通網(wǎng)絡(luò)，信息代表著運(yùn)輸?shù)呢浳铮瑐鬏數(shù)男手饕c節(jié)點(diǎn)之間距離和運(yùn)載能力有關(guān)，滿足關(guān)系可以表示如下：

其中，eij是節(jié)點(diǎn)i 和j 之間的傳輸效率，取值范圍是［0，1］，dij是節(jié)點(diǎn)i 和j 的距離，pij是兩點(diǎn)之間運(yùn)載能力，k 是常數(shù)系數(shù)。根據(jù)此式可以定義網(wǎng)絡(luò)的全局效率是網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間傳輸效率的平均值：

多層網(wǎng)絡(luò)的全局效率可理解為網(wǎng)絡(luò)中所有節(jié)點(diǎn)貨物運(yùn)輸效率的平均值，如果移除網(wǎng)絡(luò)中的某個節(jié)點(diǎn)會導(dǎo)致全局網(wǎng)絡(luò)效率的變化，而且節(jié)點(diǎn)的重要度越高，對網(wǎng)絡(luò)全局效率的影響越大，因此，可以通過逐個移除網(wǎng)絡(luò)中某個節(jié)點(diǎn)，計(jì)算網(wǎng)絡(luò)全局效率的變化來驗(yàn)證算法的有效性，具體結(jié)果如表3 所示。

表3 節(jié)點(diǎn)對網(wǎng)絡(luò)效率的影響排序

如表3 所示，Ec、Ed、Ee、Eg分別是單層網(wǎng)絡(luò)（c）（d）（e）（g）的效率，Eb是多層網(wǎng)路（b）的效率。節(jié)點(diǎn)對網(wǎng)絡(luò)全局影響度排序與表2 中不同方法節(jié)點(diǎn)重要度排序結(jié)果相比可以發(fā)現(xiàn)，影響度排序結(jié)果與本文的基于信息融合算法節(jié)點(diǎn)重要度非常相似，其中節(jié)點(diǎn)4、5、3、2、6、7 的順序與本文價值排序的方法一致，而與其他算法差別比較明顯。通過網(wǎng)絡(luò)全局效率的計(jì)算再次說明本文算法的有效性。

3 結(jié)論

本文考慮了多層交通網(wǎng)絡(luò)的路徑權(quán)重和節(jié)點(diǎn)之間的連接關(guān)系對多層網(wǎng)絡(luò)整體影響，并運(yùn)用數(shù)據(jù)融合算法對多層交通網(wǎng)絡(luò)的關(guān)聯(lián)矩陣進(jìn)行融合，最終得到多層網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)聯(lián)度，通過對局部多層交通網(wǎng)絡(luò)實(shí)例的建模計(jì)算，并與已有的其他3 種方法進(jìn)行對比。結(jié)果顯示，本文所建立的多層交通網(wǎng)絡(luò)模型符合實(shí)際，并且運(yùn)用改進(jìn)的融合算法，能夠有效對多層交通網(wǎng)絡(luò)目標(biāo)體系的節(jié)點(diǎn)網(wǎng)絡(luò)價值進(jìn)行準(zhǔn)確評估，對于下一步目標(biāo)選擇具有一定借鑒意義。