基于度序列的復雜網(wǎng)絡模型及其路由策略分析*

熊云艷 肖文俊 毛宜軍 賴正文 韓冬

(1.華南理工大學 計算機科學與工程學院， 廣東 廣州 510640； 2.華南理工大學 軟件學院， 廣東 廣州 510006；3.華南農(nóng)業(yè)大學 數(shù)學與信息學院， 廣東 廣州 510642)

基于度序列的復雜網(wǎng)絡模型及其路由策略分析*

熊云艷1肖文俊2毛宜軍3賴正文1韓冬1

(1.華南理工大學 計算機科學與工程學院， 廣東 廣州 510640； 2.華南理工大學 軟件學院， 廣東 廣州 510006；3.華南農(nóng)業(yè)大學 數(shù)學與信息學院， 廣東 廣州 510642)

通過對復雜網(wǎng)絡一般模型的節(jié)點度序列{k1,k2,…,kl}(1≤k1

復雜網(wǎng)絡；節(jié)點度序列；路由策略

復雜系統(tǒng)主要包括系統(tǒng)單元以及系統(tǒng)單元之間的關聯(lián)關系.以圖論為理論基礎的復雜網(wǎng)絡是刻畫復雜系統(tǒng)的主要工具.復雜網(wǎng)絡不僅可以描述復雜系統(tǒng)的靜態(tài)特性，還可以描述復雜系統(tǒng)的動態(tài)演化行為.目前，復雜網(wǎng)絡的網(wǎng)絡特性、理論證明、實證研究與動態(tài)演化等是復雜網(wǎng)絡研究中的熱點.

從網(wǎng)絡特性的角度，復雜網(wǎng)絡大致可以分為小世界網(wǎng)絡、無標度網(wǎng)絡、可導航網(wǎng)絡3大類.現(xiàn)實生活中的社交網(wǎng)絡、信息網(wǎng)絡、技術網(wǎng)絡、生物網(wǎng)絡都是復雜網(wǎng)絡.典型的復雜網(wǎng)絡模型包括小世界網(wǎng)絡(Small-World Networks)模型[1]、無標度網(wǎng)絡(Scale-Free Networks)模型[2]、可導航網(wǎng)絡(Navigable Networks)模型[3]和以這3種網(wǎng)絡模型為基礎衍生的其他各種模型.小世界網(wǎng)絡模型采用了隨機重連的機制，無標度網(wǎng)絡模型中的BA模型采用了增長和優(yōu)先連接的機制，可導航網(wǎng)絡模型則利用網(wǎng)絡的局部信息實現(xiàn)復雜網(wǎng)絡的可導航功能.文獻[2]中提出，復雜網(wǎng)絡的度分布滿足冪律分布，即P(k)=ck-γ(這里k表示網(wǎng)絡的度，c、γ是常量)；對于現(xiàn)實生活中的大部分復雜網(wǎng)絡，參數(shù)γ需滿足γ≥2.3[4- 7].

網(wǎng)絡的主要性能參數(shù)包括擁塞率、抗攻擊性、路由效率等[4,8- 9]，而路由表的建立效率是衡量網(wǎng)絡路由性能的關鍵參數(shù)之一.路由表的建立依賴于具體的網(wǎng)絡模型，即不同的網(wǎng)絡模型，路由表的建立算法是不同的.復雜網(wǎng)絡中路由表的建立算法包括廣度優(yōu)先搜索(BFS)算法、最大度(MD)算法[10- 12]等.

文中基于復雜網(wǎng)絡度序列長度的理論和復雜網(wǎng)絡模型，提出了一種基于度序列的復雜網(wǎng)絡模型的構建思想.該模型兼顧了小世界網(wǎng)絡和無標度網(wǎng)絡的特點，同時驗證了基于最大度的路由表構建算法比基于廣度優(yōu)先的路由表構建算法具有更好的性能，由此可證明復雜網(wǎng)絡中采用基于最大度算法的路由策略是有效的.

1 相關工作

無權的復雜網(wǎng)絡可以通過有向圖或者無向圖G(V,E)來描述，其中V表示復雜網(wǎng)絡的頂點集合，E表示復雜網(wǎng)絡的邊集合.描述復雜網(wǎng)絡的主要有以下參數(shù)：

M：復雜網(wǎng)絡的邊的數(shù)量，M=|E|；

N：復雜網(wǎng)絡的節(jié)點的數(shù)量，N=|V|；

d(v)：節(jié)點v的度，vV；

nk：度為k的節(jié)點的數(shù)量，nk={v|d(v)=k}；

P(k)：度的分布概率或者度為k的節(jié)點所占總節(jié)點的比例，P(k)=nk/N；

l：節(jié)點度序列{k1,k2,…,kl}的長度，其中1≤k1

在筆者前期的研究中，假定復雜網(wǎng)絡的度序列為1≤k1

(1)

i=1,2,…,l.文獻[13- 15]證明了度序列的長度滿足如下結(jié)論：當γ>1時，l是log2N級別的，即

l≤O(log2N)

(2)

式(2)表明：無標度網(wǎng)絡中度序列的長度l相比節(jié)點數(shù)N是非常小的，基于無標度網(wǎng)絡度序列長度的特征，可以重新構建無標度網(wǎng)絡的模型.

2 復雜網(wǎng)絡度序列的一般特征

2.1 度分布為混合分布的度序列

通過式(2)的推導，對于無標度網(wǎng)絡，相比網(wǎng)絡節(jié)點的數(shù)量，無標度網(wǎng)絡度序列長度非常小.考慮更一般的復雜網(wǎng)絡，假設無權的復雜網(wǎng)絡可以通過有向圖或者無向圖G(V,E)來描述，并假設度分布符合冪律與指數(shù)的混合分布，其分布函數(shù)為

(3)

式中，q為常數(shù).

同理，c是歸一化的常量，當i=1時，由式(3)可得

(4)

把式(4)代入式(3)，可得

(5)

由式(3)和(5)可得

(6)

當i=1時，可得

(7)

對于等式(7)，左右兩邊取以2為底的對數(shù)，可得

(l-1)log2q≥(l-1)log2q

(8)

即

(9)

從式(9)可知：當q=2時，式(9)與式(2)的結(jié)論是一致的；當q>2時，因為q為常數(shù)，log2N/log2q≈(log2N)ε，式(9)可表示為l≤(log2N)ε，可知l與log2N是同級別的.這表明盡管復雜網(wǎng)絡的節(jié)點數(shù)量比較大，但是復雜網(wǎng)絡的網(wǎng)絡直徑是小于(log2N)2的.基于這個特征，如果采用最大度查找算法，則從最小度節(jié)點到最大度節(jié)點的鏈路長度一般是小于(log2N)2級別的.

基于上述推導構建基于度序列長度的復雜網(wǎng)絡模型，具體步驟如下：

步驟1 按照度的分布函數(shù)生成度序列，即{k1,k2,…,kl}.

步驟2 對每一個度序列值ki(ki>3)生成nki個不同的節(jié)點(度為1的節(jié)點除外)，每個節(jié)點創(chuàng)建ki個未連接到其他節(jié)點的連邊(稱為半連接)，把度相同的節(jié)點標識為同一類簇，實現(xiàn)簇內(nèi)及簇間連接的規(guī)則如下：

if(nki>ki){

c=nki/ki；

r=nki%ki；

先構成c個簇，每個簇內(nèi)的所有點兩兩相連，形成一個圈，整個簇對外留下ki個半連接；

剩余r個點兩兩相連，未能連接的半連接待步驟4補充；

}else{

nki個點兩兩相連，未能連接的半連接待步驟4補充；

}

步驟3 簇與簇之間通過半連接相連，保證不同的點之間最多只有一條邊，并且沒有自環(huán)，這樣可能會留下一些半連接還沒有連接.

步驟4 步驟3中沒有連接的半連接與度為1的節(jié)點進行連接，最終形成一個復雜網(wǎng)絡模型.

2.2 數(shù)據(jù)驗證

BA模型[2]是復雜網(wǎng)絡的主要模型，其構建思想如下：

(1)增長：網(wǎng)絡中有m0個節(jié)點，每個步驟t新加入一個節(jié)點，該節(jié)點與網(wǎng)絡中的m個節(jié)點連接,滿足m≤m0；

(2)優(yōu)先連接：新加入的節(jié)點與網(wǎng)絡中節(jié)點按照如下概率連接：

(10)

結(jié)合BA模型與第2.1節(jié)的度序列模型構造思想，分別構造100、1 000、10 000個節(jié)點的BA模型，重復100次試驗，去掉非連通分支后，得到的結(jié)果如表1所示.

表1 BA模型參數(shù)1)

1)BA(1 000,3)表示該BA模型初始有3個節(jié)點，每個步驟優(yōu)先連接已有的3個節(jié)點，經(jīng)過一定的演化步驟后，最終形成具有1 000個節(jié)點的網(wǎng)絡，余類同；ε為公式(9)的參數(shù).

在http:∥snap.stanford.edu/data/index.html下載Wiki-Vote、Cit-HepTh、Email-Enron、facebook_combined數(shù)據(jù)集，在http:∥www.cs.fsu.edu/～lifeifei/SpatialDataset.htm下載TG city和OL city數(shù)據(jù)進行驗證.

通過仿真得到表2所示數(shù)據(jù).

表2 實證結(jié)果

在復雜網(wǎng)絡中，參數(shù)γ滿足γ≥2.3,但是當ε>2時，(log2N)ε隨著N增加較快，因此ε不會很快增加，由表1、2的實驗數(shù)據(jù)，可以得出ε≤2.3，因此ε≤γ，而且，(log2N)ε相比N是非常小的.

利用復雜網(wǎng)絡度序列的這個特點，可以構建基于度序列的復雜網(wǎng)絡模型.該模型中，當度大于3時，把相同的度集中在一個族上，度為1與2的節(jié)點屬于某個節(jié)點族的邊緣，不同的節(jié)點族之間通過族頭連接，從而構成了一個基于度序列的復雜網(wǎng)絡模型.

3 基于度序列的復雜網(wǎng)絡模型路由策略

3.1 路由策略

設圖為G,節(jié)點個數(shù)為N，源節(jié)點和目標節(jié)點分別為i和j，由前面的推導可以得出一般實際網(wǎng)絡的度序列長度l是log2N級別的，從最小度節(jié)點到最大度節(jié)點的鏈路長度是(log2N)2級別的.路由表構建效率是評價大規(guī)模復雜網(wǎng)絡中路由策略的關鍵指標之一，文中通過仿真實驗，對比了BFS算法、MD算法、優(yōu)化的最大度(MD+)算法在構建路由表時的效率.其中BFS算法為傳統(tǒng)的基于廣度優(yōu)先的Dijkstra算法，MD和MD+的算法思想分別如下：

(1)MD算法

從前面的分析可知，如果采用基于最大度的路由算法，可以建立基于最大度的復雜網(wǎng)絡路由表，具體步驟如下：

步驟1 從源節(jié)點i出發(fā)，判別自己鄰居節(jié)點中有無目標節(jié)點j；如無，則將其中度最大的鄰居節(jié)點設為當前的節(jié)點；如有，則停止查找.

步驟2 可以多次訪問同一個節(jié)點，但是同一條邊只能被訪問一次，如果與當前節(jié)點相連的所有邊都被訪問過，則返回上一節(jié)點.

步驟3 重復步驟1和2，直到當前節(jié)點為目標節(jié)點的任一個鄰域節(jié)點，目標節(jié)點即被找到，查找完成.

(2)MD+算法

MD算法中沒有存儲查找的路徑，MD+算法則存儲了每次的查找路徑，即在查找的過程中MD+算法會存儲已經(jīng)查找到的節(jié)點之間的路徑.具體操作時，在MD算法步驟1的基礎上，如果有查到的目標節(jié)點就直接使用，否則按照最大度隨機選擇.

BFS、MD、MD+算法的性能分別利用它們得到任意2個節(jié)點之間最短路徑的查找總次數(shù)來評估.

3.2 仿真結(jié)果

使用Python編程語言，應用Networkx復雜網(wǎng)絡程序包，結(jié)合文中提出的一般復雜網(wǎng)絡模型的度序列特點進行仿真.為了更加符合現(xiàn)實模型，仿真模型采用了擴展的BA模型，即2.2節(jié)中BA模型的參數(shù)m是變化的，其滿足函數(shù)m=mtθ,0≤θ<1.在構造變m的BA模型時，采用了基于度序列的構造思想.

按照2.1節(jié)所述度序列模型生成算法，結(jié)合變m的BA模型思想，分別生成了10、50、100、500、1 000個節(jié)點的網(wǎng)絡模型，重復100次實驗，得到3種算法的性能數(shù)據(jù)(如表3所示).

表3 3種算法構造路由表時的性能

從表3可以看出，在復雜網(wǎng)絡環(huán)境下，BFS、MD、MD+3種算法的性能中，最好的是MD+，其次是MD，最差的是BFS，這證明基于最大度的算法在復雜網(wǎng)絡模型下是實用的，且MD、MD+算法同網(wǎng)絡的平均度有關.網(wǎng)絡平均度越高，最大度算法的優(yōu)勢越明顯.

4 結(jié)語

文中利用復雜網(wǎng)絡冪律的特性，得出了復雜網(wǎng)絡一般模型的度序列長度l與log2N是同級別的結(jié)論，并通過模擬仿真與動態(tài)數(shù)據(jù)進一步驗證了該結(jié)論.基于該結(jié)論，對BFS、MD、MD+3種算法的性能進行了仿真對比，結(jié)果表明：在復雜網(wǎng)絡環(huán)境下，相比于傳統(tǒng)的基于廣度優(yōu)先的BFS算法，基于最大度的算法其性能有所提升.后續(xù)研究中將進一步探討復雜網(wǎng)絡基于最大度算法的動態(tài)性能，如網(wǎng)絡稀疏度以及擁塞控制等.

[1] Watts D J,Strogatz S H.Collective dynamics of “small-world” networks [J].Nature,1998,393(6684):440- 442.

[2] Barabási A L,Albert R.Emergence of scaling in random networks [J].Science,1999,286(5439):509- 512.

[3] Kleinberg J M.Navigation in a small world [J].Nature,2000,406(6798):845.

[4] Strogatz S H.Exploring complex networks [J].Nature,2001,410(6825):268- 276.

[5] Pastor-Satorras R,Vespignani A.Epidemic spreading in scale-free networks [J].Physical Review Letters,2001,86(14):3200- 3203.

[6] Albert R,Barabási A L.Statistical mechanics of complex networks [J].Reviews of Modern Physics,2002,74(1):47- 91.

[7] Newman M E J.The structure and function of complex networks [J].SIAM Review,2003,45(2):167- 256.

[8] Arrowsmith D,Di Bernardo M,Sorrentino F.Effects of variations of load distribution on network performance [C]∥Proceedings of IEEE International Symposium on Circuits and Systems(ISCAS 2005).Kobe:IEEE,2005:3773- 3776.

[9] Goh K-I,Kahng B,Kim D.Universal behavior of load distribution in scale-free networks [J].Physical Review Letters,2001,87(27):278701/1- 4.

[10] Wu J,Tse C K,Lau F,et al.Analysis of communication network performance from a complex network perspective [J].IEEE Transactions on Circuits and Systems I:Re-gular Papers,2013,60(12):3303- 3316.

[11] Echenique P,Gómez-Gardees J,Moreno Y.Improved routing strategies for Internet traffic delivery [J].Physical Review E,2004,70(5):056105/1- 4.

[12] Wang W X,Wang B H,Yin C Y,et al.Traffic dynamics based on local routing protocol on a scale-free network [J].Physical Review E,2006,73(2):026111/1- 7.

[13] Xiao W J,Jiang S Z,Chen G R.A small-world model of scale-free networks:features and verifications [J].Applied Mechanics and Materials,2011(50/51):166- 170.

[14] Xiao W J,Chen W D,Parhami B.On necessary conditions for scale-freedom in complex networks,with applications to computer communication systems [J].International Journal of Systems Science,2011,42(6):951- 958.

[15] Xiao W,Liu Y,Chen G.Characterizing vertex-degree sequences in scale-free networks [J].Physica A:Statistical Mechanics and its Applications,2014(404):291- 295.

A Degree Sequence-Based Complex Network Model and Its Routing Strategy Analysis

XiongYun-yan1XiaoWen-jun2MaoYi-jun3LaiZheng-wen1HanDong1

(1.School of Computer Science and Engineering，South China University of Technology，Guangzhou 510640，Guangdong，China;2.School of Software Engineering，South China University of Technology，Guangzhou 510006，Guangdong，China;3.School of Mathmatics and Informatics，South China University of Agriculture，Guangzhou 510642，Guangdong，China)

By analyzing the lengthlof the vertex-degree sequence {k1,k2,…,kl} (1≤k1

complex network;vertex-degree sequence;routing strategy

2015- 04- 15

國家自然科學基金資助項目(61170313) Foundation item: Supported by the National Natural Science Foundation of China(61170313)

熊云艷(1976-)，女，博士生，副教授，主要從事復雜網(wǎng)絡、數(shù)據(jù)中心網(wǎng)絡等的研究.E-mail: yunyanx@163.com

1000- 565X(2015)11- 0030- 05

TP 393.0

10.3969/j.issn.1000-565X.2015.11.005