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

孫興龍，李亞雄，邱艷粉

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

0 引言

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

交通體系網(wǎng)絡(luò)模型包括公路網(wǎng)、鐵路網(wǎng)、航空網(wǎng)組成，是典型的多層復(fù)雜網(wǎng)絡(luò)模型。目前，對(duì)于評(píng)估多層交通網(wǎng)絡(luò)節(jié)點(diǎn)重要性，很少有考慮邊的權(quán)重，事實(shí)上每條路徑的運(yùn)載能力區(qū)別很大，權(quán)重不可忽略。對(duì)于多層復(fù)雜網(wǎng)絡(luò)的研究分為兩個(gè)方面。一是分析網(wǎng)絡(luò)的統(tǒng)計(jì)特性，包括聚類系數(shù)、特征向量、度中心性、介數(shù)中心性；二是對(duì)復(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］。

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

2）構(gòu)建距離矩陣。在拆解過(guò)程中，逐一計(jì)算每個(gè)單層網(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ī)則得到任意兩個(gè)節(jié)點(diǎn)的基本概率分配函數(shù)（Basic Probability Assignment Functions 簡(jiǎn)稱BPA）。

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

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

該算法框架如圖1 所示。

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

1.1 模型建立的步驟

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

1）將多層網(wǎng)絡(luò)拆解為多個(gè)單層網(wǎng)絡(luò)。根據(jù)多層復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)組成關(guān)系將其拆解為多個(gè)單層網(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ò)拆解過(guò)程

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

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

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

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

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

關(guān)聯(lián)度矩陣的構(gòu)建是節(jié)點(diǎn)評(píng)估準(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在整個(gè)網(wǎng)絡(luò)的價(jià)值。而網(wǎng)絡(luò)中節(jié)點(diǎn)i 與節(jié)點(diǎn)j 之間的關(guān)聯(lián)度sij不僅與兩個(gè)節(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后，會(huì)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)m 和n 的最短路徑產(chǎn)生影響，可能會(huì)導(dǎo)致最短路徑變大或者不存在連通路徑。

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

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

對(duì)于不同的交通網(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)輸效率主要由時(shí)間成本、經(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ò)中不相連時(shí)，wij為0。

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

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

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

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

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

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

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

在該命題上的辨識(shí)框架的冪集為：

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

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

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

其中，

其中，

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

其中，

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

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

其中，

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

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

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

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

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

2 實(shí)例分析

下面通過(guò)對(duì)局部多層交通網(wǎng)絡(luò)模型圖2 中的節(jié)點(diǎn)評(píng)估過(guò)程進(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)的融合算法相對(duì)區(qū)間范圍較大。

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

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

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

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

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

在實(shí)際網(wǎng)絡(luò)中，信息以網(wǎng)絡(luò)的邊為載體進(jìn)行節(jié)點(diǎn)之間的信息交換。對(duì)于交通網(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ò)中的某個(gè)節(jié)點(diǎn)會(huì)導(dǎo)致全局網(wǎng)絡(luò)效率的變化，而且節(jié)點(diǎn)的重要度越高，對(duì)網(wǎng)絡(luò)全局效率的影響越大，因此，可以通過(guò)逐個(gè)移除網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)，計(jì)算網(wǎng)絡(luò)全局效率的變化來(lái)驗(yàn)證算法的有效性，具體結(jié)果如表3 所示。

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

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

3 結(jié)論

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