基于多關(guān)系網(wǎng)絡(luò)的邊轉(zhuǎn)移擴容策略

高峰 孫更新 賓晟

摘要：為緩解網(wǎng)絡(luò)擁塞、提高網(wǎng)絡(luò)容量，利用真實網(wǎng)絡(luò)中節(jié)點間存在多種關(guān)系的特性，基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型提出了一種適用于多關(guān)系網(wǎng)絡(luò)的邊轉(zhuǎn)移擴容策略。通過改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，刪除高介數(shù)節(jié)點之間的邊，同時，在最短路徑較長的節(jié)點對之間添加邊以此來達(dá)到擴大網(wǎng)絡(luò)容量的目的。研究結(jié)果表明，邊轉(zhuǎn)移策略降低了網(wǎng)絡(luò)中節(jié)點介數(shù)的最大值，有效地縮短了網(wǎng)絡(luò)平均最短路徑，均衡了節(jié)點之間的信息負(fù)載，最大化的提高了網(wǎng)絡(luò)容量。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型;擴容;網(wǎng)絡(luò)容量;介數(shù)

中圖分類號：TP393.0

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-1037（2021）03-0038-05

現(xiàn)實世界中的網(wǎng)絡(luò)往往具有小世界[1]、無標(biāo)度[2]等特征，研究人員基于上述特征建立復(fù)雜網(wǎng)絡(luò)模型，通過對復(fù)雜網(wǎng)絡(luò)模型上的信息傳播特征及其本質(zhì)屬性的研究，為解決真實問題提供參考。近年來，隨著交通網(wǎng)、互聯(lián)網(wǎng)等網(wǎng)絡(luò)規(guī)模的擴大，網(wǎng)絡(luò)擁塞問題愈發(fā)嚴(yán)重，如何有效的緩解網(wǎng)絡(luò)擁塞以及提高網(wǎng)絡(luò)的傳輸性能成為研究熱點。目前，針對上述問題的研究大致分為兩種：研究網(wǎng)絡(luò)動力學(xué)過程[3-5]，通過高效的信息傳輸策略來緩解網(wǎng)絡(luò)的擁塞程度，典型的有最短路徑策略[6-7]、動態(tài)路由策略[8]、度和最小路由策略等[9];研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)[10-12]，通過優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)擴大網(wǎng)絡(luò)的拓?fù)淙萘浚泳従W(wǎng)絡(luò)擁塞的發(fā)生，從而提高網(wǎng)絡(luò)的傳輸性能?？紤]到添加邊的成本，學(xué)者們提出了刪邊擴容策略。比如，Liu等[13]提出了一種高度優(yōu)先策略，關(guān)閉了部分大度節(jié)點之間的鏈路，從而提高網(wǎng)絡(luò)容量。基于上述研究，Huang等[14]對刪邊擴容策略進(jìn)行了優(yōu)化，提出一種更有效的刪邊策略，刪除部分與高介數(shù)節(jié)點相連的邊，從而均衡各節(jié)點之間的負(fù)載。隨著研究的深入，學(xué)者們發(fā)現(xiàn)在網(wǎng)絡(luò)中適當(dāng)加邊的擴容效果更好，Huang等[15]提出一種基于最長最短路徑添加邊的策略。趙焱鑫等[16]考慮到介數(shù)對網(wǎng)絡(luò)容量的影響，對上述加邊策略進(jìn)行了優(yōu)化。上述研究都在傳統(tǒng)網(wǎng)絡(luò)中進(jìn)行，真實網(wǎng)絡(luò)中，節(jié)點之間大多存在多種關(guān)系，以交通網(wǎng)為例，兩地之間存在著飛機、火車、輪船、汽車等多種運輸方式?，F(xiàn)實世界中，類似于交通網(wǎng)，個體之間存在著多種關(guān)系的網(wǎng)絡(luò)可以描述為多關(guān)系網(wǎng)絡(luò)[17]。已有研究與真實網(wǎng)絡(luò)中的信息傳輸存在著較大的差異。本文針對真實網(wǎng)絡(luò)中個體間存在多種關(guān)系的特點，基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型，結(jié)合網(wǎng)絡(luò)拓?fù)淙萘颗c節(jié)點最大介數(shù)成反比的結(jié)論，提出適用于多關(guān)系網(wǎng)絡(luò)的邊轉(zhuǎn)移擴容策略。

1 網(wǎng)絡(luò)模型

本文基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型（簡稱復(fù)合網(wǎng)），定義了復(fù)合網(wǎng)上的網(wǎng)絡(luò)流量模型。

1.1 多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型

多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型是一種能夠描述個體間多種關(guān)系的新型網(wǎng)絡(luò)模型[18]，該模型將復(fù)雜系統(tǒng)中個體間的相互關(guān)系映射為向量空間中的多維向量，定義了向量復(fù)合網(wǎng)，將組網(wǎng)運算轉(zhuǎn)化為向量空間的基變化。為復(fù)雜系統(tǒng)的描述及其研究提供了新方法。

該模型將多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)定義為一個四元組G=（V，E，R，F(xiàn)）：V={v1，v2，…，vm}，表示節(jié)點的集合，m=V是集合V的階;E=<vh，vl>|vh，vl∈V，1≤h，l≤mV×V，表示節(jié)點間連邊的集合;R=R1×…×Ri×…×Rn=（r1，…，ri，…，rn）|ri∈Ri，1≤i≤n，Ri表示節(jié)點間一種相互作用的集合，n是節(jié)點間相互作用關(guān)系的總數(shù)，R可以為空集;映射F：E→R。

1.2 流量模型

在復(fù)合網(wǎng)中，假設(shè)所有節(jié)點都可以產(chǎn)生、接受和傳輸信息，每個節(jié)點都有一個信息等待隊列，用以保存等待處理的信息，容量為C，任意兩節(jié)點之間存在多種關(guān)系，信息隨機選擇任意關(guān)系進(jìn)行傳輸，不同關(guān)系的信息處理能力不同，例如，節(jié)點間的某關(guān)系ri的處理能力為p，即在每個時間步內(nèi)，節(jié)點vh（vh∈V）通過關(guān)系ri最多向其鄰居節(jié)點傳輸p條信息。節(jié)點可以同時通過多種關(guān)系向其鄰居節(jié)點傳輸信息。在每個時間步內(nèi)，系統(tǒng)中產(chǎn)生R條信息，信息的源節(jié)點和目的節(jié)點在復(fù)合網(wǎng)中隨機選擇，并且，源節(jié)點與目的節(jié)點不重合。當(dāng)信息到達(dá)其目的節(jié)點后從系統(tǒng)中刪除。

2 邊轉(zhuǎn)移擴容算法

不同于傳統(tǒng)網(wǎng)絡(luò)，復(fù)合網(wǎng)節(jié)點間存在多種關(guān)系，因此，對于任意源節(jié)點s與目的節(jié)點t之間的傳輸路徑l定義為

其中，sri表示信息通過關(guān)系ri將信息傳輸給其鄰居節(jié)點，vm是此路徑上的第m個中間節(jié)點。

根據(jù)復(fù)合網(wǎng)中的傳輸路徑，復(fù)合網(wǎng)中節(jié)點在最短路徑策略下介數(shù)為

其中，σst表示節(jié)點s和t之間的最短路徑條數(shù)，σst（v） 表示其中經(jīng)過節(jié)點v的最短路徑數(shù)目，經(jīng)過相同節(jié)點，但是傳輸所用的關(guān)系不同，則其路徑不同。σst（v）越大，則有更多的最短路徑經(jīng)過節(jié)點v，所以節(jié)點v發(fā)生擁塞的概率越大。

由于每一個時間步復(fù)合網(wǎng)絡(luò)中都會產(chǎn)生R個信息，此時規(guī)模為N的網(wǎng)絡(luò)中的某個節(jié)點v需要處理信息的平均數(shù)量約為

從〈θ〉可知，網(wǎng)絡(luò)中介數(shù)最大的節(jié)點最早發(fā)生擁塞。將網(wǎng)絡(luò)中節(jié)點的最大介數(shù)數(shù)表示為g，則

網(wǎng)絡(luò)中負(fù)載系數(shù)最大的節(jié)點信息數(shù)量超出其信息容量C時，網(wǎng)絡(luò)發(fā)生擁塞。所以網(wǎng)絡(luò)發(fā)生擁塞的臨界值為

即為當(dāng)前復(fù)合網(wǎng)的網(wǎng)絡(luò)容量Rc。

從復(fù)合網(wǎng)網(wǎng)絡(luò)容量的定義中不難得出，網(wǎng)絡(luò)容量Rc與節(jié)點的介數(shù)呈反比，即降低網(wǎng)絡(luò)的最大介數(shù)，即可增大網(wǎng)絡(luò)容量。由此得出網(wǎng)絡(luò)演化過程，如圖1所示。

對于網(wǎng)絡(luò)圖1 （a），不難得出節(jié)點v1介數(shù)最大，則其網(wǎng)絡(luò)容量取決于v1，gv1的值越大，網(wǎng)絡(luò)容量越小。在v1的鄰居節(jié)點中v4的介數(shù)較大，刪除v1和v4之間信息處理能力最小的關(guān)系r1，對節(jié)點v1和v4的影響最小，但gv1的值變小，網(wǎng)絡(luò)容量得到提高。在最短路徑最長的節(jié)點對v2和v5之間添加ri關(guān)系，得到網(wǎng)絡(luò)圖1 （b）。此時，縮短了網(wǎng)絡(luò)中的平均路徑長度，相比網(wǎng)絡(luò)圖1 （a），網(wǎng)絡(luò)圖1 （b）的信息處理能力更優(yōu)秀。

基于上述演化過程，提出邊轉(zhuǎn)移擴容策略。首先，刪除與高介數(shù)節(jié)點與其鄰居節(jié)點中介數(shù)最大的節(jié)點之間的信息處理能力最小的關(guān)系ri;其次，將刪除的關(guān)系添加到最短路徑最長的兩節(jié)點之間（該算法默認(rèn)所有節(jié)點可達(dá)）。具體步驟如下：

Step 1 計算網(wǎng)絡(luò)中所有節(jié)點的介數(shù)存于矩陣Q，計算網(wǎng)絡(luò)中任意未直接相連的兩節(jié)點之間的最短路徑，存于矩陣P;

Step 2 在矩陣Q中尋找介數(shù)最大的節(jié)點，并尋找其鄰居節(jié)點中介數(shù)最大的節(jié)點，刪除兩節(jié)點之間信息處理能力最小的邊ri，若該節(jié)點對之間只存在一種關(guān)系，則刪除其他符合條件的關(guān)系。在矩陣P中尋找最長的最短路徑，并將其節(jié)點對存入集合E;

Step 3 在E中尋找介數(shù)最小的節(jié)點對（u，v），并在（u，v）之間添加ri;

Step 4 重復(fù)上述過程，直到轉(zhuǎn)移邊的數(shù)目達(dá)到f。

在該算法中，計算最短路徑時用到了Dijkstra算法。該算法的實質(zhì)是刪除大介數(shù)節(jié)點之間的連邊，使得最大介數(shù)減小，從而使網(wǎng)絡(luò)容量增大。同時，將刪除的邊加入到最短路徑最長的節(jié)點對之間，從而降低了平均傳輸路徑，提升了整個網(wǎng)絡(luò)的信息處理能力。通過邊的轉(zhuǎn)移，在不增加整體網(wǎng)絡(luò)資源的情況下，最大化地提高網(wǎng)絡(luò)容量。

3 實驗結(jié)果及分析

在實驗中，針對網(wǎng)絡(luò)容量Rc、平均最短路徑Lav和節(jié)點的介數(shù)3個指標(biāo)，將本文策略（記為TS）和最低度添加邊策略（LS）與最長最短路徑添加邊策略（DS）進(jìn)行比較。復(fù)合網(wǎng)規(guī)模設(shè)置為N=1 000，節(jié)點間最大關(guān)系數(shù)為4，關(guān)系的信息處理能力分別為1、2、3、4（即每個時間步內(nèi)，節(jié)點v只能通過某關(guān)系i向其鄰居節(jié)點傳輸1、2、3、4條信息），節(jié)點的信息容量C=10。在最短路徑傳輸策略下，對3種擴容策略進(jìn)行10次實驗，取其平均值。

圖2是3種策略對平均路徑長度Lav的影響，可知，TS和DS對減少節(jié)點間路徑長度的效果比LS好，并且在改變邊的數(shù)量f（TS策略中轉(zhuǎn)移邊的數(shù)量，DS、LS策略中添加邊的數(shù)量）較少時，TS與DS的效果相差不多，在改變邊的數(shù)量較多時，DS的效果更加顯著。圖3是網(wǎng)絡(luò)的拓?fù)淙萘颗cf之間的關(guān)系，隨著f的增加，上述3種策略都可以提高網(wǎng)絡(luò)容量。相比之下，TS策略對于網(wǎng)絡(luò)性能的提升更加顯著。DS策略雖然在減小平均路徑上的表現(xiàn)比TS更好，但是隨著f的增加，網(wǎng)絡(luò)中各節(jié)點的介數(shù)也在不斷的增大。但是TS策略，在減小平均路徑的同時，網(wǎng)絡(luò)中節(jié)點的介數(shù)也在降低，由此可以體現(xiàn)TS策略的優(yōu)越性。

對比3張圖可以發(fā)現(xiàn)，相比于TS，DS和LS策略下網(wǎng)絡(luò)中節(jié)點的介數(shù)相差較大，這使得信息在網(wǎng)絡(luò)中傳輸?shù)臅r候網(wǎng)絡(luò)中各節(jié)點之間的信息負(fù)載不均衡，低介數(shù)節(jié)點的利用率不高，高介數(shù)節(jié)點較早的出現(xiàn)擁塞現(xiàn)象。而TS策略下，網(wǎng)絡(luò)中節(jié)點的介數(shù)相差較小，網(wǎng)絡(luò)中各節(jié)點之間的信息負(fù)載比較均衡，低介數(shù)節(jié)點的利用率較高，延緩了擁塞現(xiàn)象發(fā)生的時間，從而提高了整個網(wǎng)絡(luò)的信息處理能力。

通過上述仿真實驗可以發(fā)現(xiàn)，雖然在改變邊數(shù)量較大時，在縮短最短路徑長度的效果上，本文策略不如最長最短路徑添加邊策略，但是邊轉(zhuǎn)移策略與最低度添加邊策略和最長最短路徑添加邊策略相比，在網(wǎng)絡(luò)整體的性能提升上的表現(xiàn)更加優(yōu)秀。邊轉(zhuǎn)移策略不僅能夠有效地縮短最短路徑，并且可以均衡各節(jié)點之間的信息負(fù)載，較大程度地提高網(wǎng)絡(luò)容量。

4 結(jié)論

本文提出了一種基于多關(guān)系網(wǎng)絡(luò)的邊轉(zhuǎn)移擴容策略，刪除高介數(shù)節(jié)點對之間的邊，同時在最短路徑較長的節(jié)點的節(jié)點對之間添加邊，以此來降低網(wǎng)絡(luò)中節(jié)點的介數(shù)，同時縮短最短路徑長度。并在多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型上進(jìn)行仿真實驗，對網(wǎng)絡(luò)中節(jié)點的介數(shù)、平均最短路徑長度和網(wǎng)絡(luò)容量進(jìn)行了分析，與其他擴容策略相比，本文提出的策略能夠更好地提高網(wǎng)絡(luò)性能，對提高真實網(wǎng)絡(luò)的網(wǎng)絡(luò)性能提供了參考。

參考文獻(xiàn)

[1]WATTS D， STROGATZ S. Collective dynamics of 'small-world networks[J]. Nature，1998，393（6684）：440-442.

[2]BARABASI A， BONABEAU E. Scale-free networks[J]. Scientific American. 2003， 288（5）：60-69.

[3]ZAGER L， VERGHESE G. Epidemic thresholds for infection in uncertain networks[J]. Complexity， 2009， 14（4）：12-25.

[4]TNJES R， MASUDA N， KORI H. Synchronization transition of identical phase oscillators in a directed small-world network[J]. Chaos. 2010， 20（3）：033108. doi： 10.1063/1.3476316. PMID： 20887048.

[5]LEYVA I， NAVAS A， SENDIA-NADAL I， et al. Synchronization waves in geometric networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2011， 84（6 Pt 2）：065101.

[6]GOH K I， KAHNG B， KIM D. Universal behavior of load distribution in scale-free networks[J]. PhRvL， 2001， 87（27）：278701.

[7]ZHAO L， LAI Y C， PARK K， et al. Onset of traffic congestion in complex networks[J]. Physical Review E， 2005， 71（2）：026125.

[8]萬琳， 范秋靈， 胡海榮. 復(fù)雜網(wǎng)絡(luò)路由策略優(yōu)化設(shè)計[J]. 兵器裝備工程學(xué)報， 2013， 34（11）：103-105.

[9]TANG M， ZHOU T. Efficient routing strategies in scale-free networks with limited bandwidth[J]. Physical Review E， 2011， 84（2）：026116.

[10] WU J， BARAHONA M， TAN Y J， et al. Natural connectivity of complex networks[J]. Chinese Physics Letters， 2010， 27（7）：078902.

[11] 邵志剛. 人體心律動力學(xué)的網(wǎng)絡(luò)分析[J]. 應(yīng)用物理學(xué)快報，2010，96（7）：4972.

[12] TODA A A. Income dynamics with a stationary double pareto distribution[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2011， 83（4）：046122.

[13] LIU Z， HU M B， JIANG R， et al. Method to enhance traffic capacity for scale-free networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2007， 76（3）：037101.

[14] HUANG W， CHOW T W S. An efficient strategy for enhancing traffic capacity by removing links in scale-free networks[J]. Journal of Statistical Mechanics Theory and Experiment， 2010， 2010（1）：P01016.

[15] HUANG W， CHOW T W S. Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network[J]. Chaos An Interdisciplinary Journal of Nonlinear Science， 2010， 20（3）：509.

[16] 趙焱鑫， 李黎， 王小明. 復(fù)雜網(wǎng)絡(luò)加邊擴容策略研究[J]. 計算機應(yīng)用研究， 2015， 32（6）：1839-1841.

[17] BERLINGERIO M， COSCIA M， GIANNOTTI F， et al. Multidimensional networks： foundations of structural analysis[J]. World Wide Web-internet & Web Information Systems， 2013， 16（5-6）：567-593.

[18] 隋毅. 多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型及其相關(guān)性質(zhì)的研究[D]. 青島：青島大學(xué)， 2012.