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

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

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

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

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

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

復(fù)雜網(wǎng)絡(luò)；節(jié)點(diǎn)度序列；路由策略

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

(1)

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

l≤O(log2N)

(2)

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

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

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

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

(3)

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

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

(4)

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

(5)

由式(3)和(5)可得

(6)

當(dāng)i=1時(shí)，可得

(7)

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

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

(8)

即

(9)

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

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

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

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

if(nki>ki){

c=nki/ki；

r=nki%ki；

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

剩余r個(gè)點(diǎn)兩兩相連，未能連接的半連接待步驟4補(bǔ)充；

}else{

nki個(gè)點(diǎn)兩兩相連，未能連接的半連接待步驟4補(bǔ)充；

}

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

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

2.2 數(shù)據(jù)驗(yàn)證

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

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

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

(10)

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

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

1)BA(1 000,3)表示該BA模型初始有3個(gè)節(jié)點(diǎn)，每個(gè)步驟優(yōu)先連接已有的3個(gè)節(jié)點(diǎn)，經(jīng)過一定的演化步驟后，最終形成具有1 000個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，余類同；ε為公式(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ù)進(jìn)行驗(yàn)證.

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

表2 實(shí)證結(jié)果

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

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

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

3.1 路由策略

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

(1)MD算法

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

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

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

步驟3 重復(fù)步驟1和2，直到當(dāng)前節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)的任一個(gè)鄰域節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)即被找到，查找完成.

(2)MD+算法

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

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

3.2 仿真結(jié)果

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

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

表3 3種算法構(gòu)造路由表時(shí)的性能

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

4 結(jié)語

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

[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

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

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

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

TP 393.0

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