基于多關系網絡的邊轉移擴容策略

高峰 孫更新 賓晟

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

關鍵詞：復雜網絡;多子網復合復雜網絡模型;擴容;網絡容量;介數

中圖分類號：TP393.0

文獻標志碼：A

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

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

1 網絡模型

本文基于多子網復合復雜網絡模型（簡稱復合網），定義了復合網上的網絡流量模型。

1.1 多子網復合復雜網絡模型

多子網復合復雜網絡模型是一種能夠描述個體間多種關系的新型網絡模型[18]，該模型將復雜系統中個體間的相互關系映射為向量空間中的多維向量，定義了向量復合網，將組網運算轉化為向量空間的基變化。為復雜系統的描述及其研究提供了新方法。

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

1.2 流量模型

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

2 邊轉移擴容算法

不同于傳統網絡，復合網節點間存在多種關系，因此，對于任意源節點s與目的節點t之間的傳輸路徑l定義為

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

根據復合網中的傳輸路徑，復合網中節點在最短路徑策略下介數為

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

由于每一個時間步復合網絡中都會產生R個信息，此時規模為N的網絡中的某個節點v需要處理信息的平均數量約為

從〈θ〉可知，網絡中介數最大的節點最早發生擁塞。將網絡中節點的最大介數數表示為g，則

網絡中負載系數最大的節點信息數量超出其信息容量C時，網絡發生擁塞。所以網絡發生擁塞的臨界值為

即為當前復合網的網絡容量Rc。

從復合網網絡容量的定義中不難得出，網絡容量Rc與節點的介數呈反比，即降低網絡的最大介數，即可增大網絡容量。由此得出網絡演化過程，如圖1所示。

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

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

Step 1 計算網絡中所有節點的介數存于矩陣Q，計算網絡中任意未直接相連的兩節點之間的最短路徑，存于矩陣P;

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

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

Step 4 重復上述過程，直到轉移邊的數目達到f。

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

3 實驗結果及分析

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

圖2是3種策略對平均路徑長度Lav的影響，可知，TS和DS對減少節點間路徑長度的效果比LS好，并且在改變邊的數量f（TS策略中轉移邊的數量，DS、LS策略中添加邊的數量）較少時，TS與DS的效果相差不多，在改變邊的數量較多時，DS的效果更加顯著。圖3是網絡的拓撲容量與f之間的關系，隨著f的增加，上述3種策略都可以提高網絡容量。相比之下，TS策略對于網絡性能的提升更加顯著。DS策略雖然在減小平均路徑上的表現比TS更好，但是隨著f的增加，網絡中各節點的介數也在不斷的增大。但是TS策略，在減小平均路徑的同時，網絡中節點的介數也在降低，由此可以體現TS策略的優越性。

對比3張圖可以發現，相比于TS，DS和LS策略下網絡中節點的介數相差較大，這使得信息在網絡中傳輸的時候網絡中各節點之間的信息負載不均衡，低介數節點的利用率不高，高介數節點較早的出現擁塞現象。而TS策略下，網絡中節點的介數相差較小，網絡中各節點之間的信息負載比較均衡，低介數節點的利用率較高，延緩了擁塞現象發生的時間，從而提高了整個網絡的信息處理能力。

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

4 結論

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

參考文獻

[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]萬琳， 范秋靈， 胡海榮. 復雜網絡路由策略優化設計[J]. 兵器裝備工程學報， 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] 邵志剛. 人體心律動力學的網絡分析[J]. 應用物理學快報，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] 趙焱鑫， 李黎， 王小明. 復雜網絡加邊擴容策略研究[J]. 計算機應用研究， 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] 隋毅. 多子網復合復雜網絡模型及其相關性質的研究[D]. 青島：青島大學， 2012.