基于復(fù)雜網(wǎng)絡(luò)特征的P2P系統(tǒng)模型的研究

王曉燕，毛紅閣

（南陽師范學(xué)院軟件學(xué)院，河南南陽473061）

基于復(fù)雜網(wǎng)絡(luò)特征的P2P系統(tǒng)模型的研究

王曉燕，毛紅閣

（南陽師范學(xué)院軟件學(xué)院，河南南陽473061）

研究表明小世界和無尺度是很多大型復(fù)雜網(wǎng)絡(luò)的重要特征,研究具有復(fù)雜網(wǎng)絡(luò)特征的P2P網(wǎng)絡(luò)模型對研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和行為有著重要的意義.針對現(xiàn)有模型不能全面地反映實際網(wǎng)絡(luò)提出了基于復(fù)雜網(wǎng)絡(luò)特征的P2P網(wǎng)絡(luò)模型.本文在基于組增長和選擇具有較大吸引力的節(jié)點這些特征基礎(chǔ)上建立一個新的模型，經(jīng)過實驗證明此模型更接近實際網(wǎng)絡(luò).

復(fù)雜網(wǎng)絡(luò)；P2P；靜態(tài)參數(shù)

小世界和無標(biāo)度出現(xiàn)以后，引發(fā)了許多學(xué)者對復(fù)雜網(wǎng)絡(luò)模型的研究.吳艾等學(xué)者提出了基于組增長的Sale-free網(wǎng)絡(luò)模型[1],劉美玲等學(xué)者提出了擇優(yōu)選擇節(jié)點構(gòu)成的復(fù)雜網(wǎng)絡(luò)模型研究[2]，這些研究沒有考慮真實網(wǎng)絡(luò)的大部分特征，而是一部分特征的刻畫.在上述兩文中節(jié)點加入網(wǎng)絡(luò)都是以概率進行擇優(yōu)連接的，而在真實系統(tǒng)中一個節(jié)點的連接不僅與節(jié)點的度數(shù)有關(guān)而且與節(jié)點的吸引度有關(guān)[3].例如,在網(wǎng)絡(luò)中,有些網(wǎng)站創(chuàng)建更好的內(nèi)容吸引瀏覽者,可以在更短的時間內(nèi)獲得大量的連接反而超過那些創(chuàng)建時間很早的網(wǎng)站.這說明一個簡單的模型相對于系統(tǒng)中其它的節(jié)點,有些節(jié)點能以更高的速率獲得連接數(shù)量，我們把這些不同歸結(jié)于節(jié)點本身具有的吸引力的大小,我們把節(jié)點具有的吸引力稱之為吸引因子.為了更好的刻畫實際網(wǎng)絡(luò)，提高網(wǎng)絡(luò)的魯棒性，降低其脆弱性，本文對建立p2p網(wǎng)絡(luò)模型提出了一下幾點：

（1）復(fù)雜網(wǎng)絡(luò)的形成是一個動態(tài)的成長變化的過程；

（2）網(wǎng)絡(luò)的增長不需要全局擇優(yōu)，而是部分擇優(yōu)；

（3）網(wǎng)絡(luò)中多個節(jié)點以組的方式加入也是網(wǎng)絡(luò)的增長方式；

（4）新增節(jié)點與吸引因子較大的節(jié)點相連接；

綜上所述，本文提出了P2PSM(P2PSystemModel)網(wǎng)絡(luò)模型.

1 P2PSM的建立過程如下

初始網(wǎng)絡(luò)中有n個節(jié)點，e條邊，節(jié)點的吸引因子即為β，ki為結(jié)點i的度數(shù)，βi為節(jié)點i的吸引因子,模型的建立過程如下：

（1）開始時，網(wǎng)絡(luò)中有n個節(jié)點，e條邊，該網(wǎng)絡(luò)即為G（n，e）.

（3）組的增長：

①生成組:

每次添加一組n個節(jié)點組成網(wǎng)絡(luò)G'，模型中G'由兩步得到:

a:首先,生成不同ki的規(guī)則的連接圖，ki的值等于每個節(jié)點與鄰居相連的邊數(shù)k0(模型中k0≥3)，根據(jù)需要決定ki的多少.

b:然后，重連上述規(guī)則網(wǎng)絡(luò)圖的一些邊，在G'中隨機選擇兩個節(jié)點且vj'≠vi'，按概率p在vi'和vj'之間建立連接,0≤p≤1.p=0時為規(guī)則網(wǎng)絡(luò)，隨著p的增加，G'無序程度逐漸增加，逐漸接近隨機網(wǎng)絡(luò).所有節(jié)點執(zhí)行重連操作后，G'的總邊數(shù)增加了，在0

②加入組:

每隔一定時間t,加入一組帶有et條邊的節(jié)點，以概率連接到局域世界G（ni），若邊數(shù)ei>r，則多余的邊加到G(ni)之外的節(jié)點上.

(4)在每加入1組節(jié)點后，計算G(ni)中每個節(jié)點的度數(shù)，如果某些新加入的節(jié)點（假設(shè)有s個）ei>min{ki}(ki為老節(jié)點連接新節(jié)點后的度數(shù))，則把這s個新節(jié)點也看作老節(jié)點，則以后再加入的節(jié)點組，再以概率(i,j=1,2,…N)連接到s+r個結(jié)點上.

本算法第一步從一個小型網(wǎng)絡(luò)開始,從現(xiàn)實網(wǎng)絡(luò)來看，很多節(jié)點局部擇優(yōu)加入網(wǎng)絡(luò)，網(wǎng)絡(luò)中節(jié)點被連接的概率與節(jié)點的吸引力大小有關(guān),并且節(jié)點的加入可能是以組的方式加入,本模型從整體上考慮了現(xiàn)實網(wǎng)絡(luò)的特性,我們通過調(diào)節(jié)βi和p控制整個網(wǎng)絡(luò).

2 舉例分析

下面舉例說明，真實網(wǎng)絡(luò)的增長過程:

（1）初始一個小網(wǎng)絡(luò)G（30，90），即帶有30個節(jié)點，90條邊;

（3）每隔一定的t時間，加入一組（10個節(jié)點，k0=4，p=0.15）帶有ei條邊的節(jié)點以概率與G(ni)連接.

（4）每加入20個節(jié)點計算G(ni)中每個節(jié)點的度數(shù).

經(jīng)過了10t的時間且加入了236條邊；經(jīng)過計算得共有6個新加入的節(jié)點度數(shù)ei>{kni}.網(wǎng)絡(luò)G（30，90）變成了新網(wǎng)絡(luò)G（30+100，90+236）=G（130，326），G(ni)變?yōu)镚(ni)(i=1,2…11).

3 參數(shù)分析

（1）通過continuum理論[4，5]來分析模型的度分布，對度分布進行數(shù)值擬合運算可得服從冪率分布P（k）=ak-r，r=1±0.3，見圖1所示.

圖1 度分布示意圖

證明因為通常p的取值都較小，所以認(rèn)為G'加入之前每個節(jié)點的度為k.忽略重連對G'中節(jié)點度的影響.每個組的加入近似看成是n個節(jié)點逐個加入的，每個單位時間t加入一個節(jié)點，并滿足：

解微分方程得：

該方程的相對初始條件是每個節(jié)點i在ti時刻到達系統(tǒng)連通度ki(ti)=ei,所以上述解應(yīng)為：

則節(jié)點連通度ki(ti)

因為節(jié)點是等時間間隔添加到系統(tǒng)的，所以ti的概率分布是一個均勻離散分布列為:

帶入方程可得：

當(dāng)t趨于＋∞時可得r=1,由于取得節(jié)點較少，所以誤差很為±0.3.

（2）利用UCINET軟件計算并分析P2PSM與B-A模型的靜態(tài)統(tǒng)計量，如下表所示：

表1 靜態(tài)特征參數(shù)表

從表1可以看出:

①擴展模型生成的網(wǎng)絡(luò)其度分布也服從冪律分布，但冪指數(shù)很小，說明這個網(wǎng)絡(luò)冪律特征沒有B-A模型生成的網(wǎng)絡(luò)明顯，所以它魯棒性更好；

②從聚集系數(shù)和最短路徑上可以看出改進的模型生成的網(wǎng)絡(luò)集聚性更強一些，由于B-A模型的全局擇優(yōu)機制，所以平均路徑要比擴展模型的網(wǎng)絡(luò)更短一些，但改進模型的擇優(yōu)更減少了節(jié)點的工作量，而改進的模型搜索速度快，這也更加符合現(xiàn)實網(wǎng)絡(luò)；

③改進后的模型考慮了節(jié)點以組的方式加入，所以該模型有助于建立更接近實際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)的動態(tài)成長過程，從而能更準(zhǔn)確地分析、設(shè)計和評測與網(wǎng)絡(luò)結(jié)構(gòu)和行為相關(guān)的工作.

4 結(jié)論

〔1〕吳艾，劉心松，劉丹，左朝樹.基于組增長的小世界Scalefree網(wǎng)絡(luò)模型[J].計算機科學(xué)，2005，32（7）.

〔2〕劉美玲，王仲君.擇優(yōu)選擇節(jié)點構(gòu)成的復(fù)雜網(wǎng)絡(luò)模型研究[J].系統(tǒng)工程與電子技術(shù)，2006，28（4）.

〔3〕陶少華，楊春，李慧娜，張勇.基于節(jié)點吸引力的復(fù)雜網(wǎng)絡(luò)演化模型研究[J].計算機工程，2009，35（1）.

〔4〕郭雷，許曉鳴.復(fù)雜網(wǎng)絡(luò)[Z].上海：上海科技教育出版社，2006.

〔5〕Reka Albert*and Albert-Laszlo Barabasi.Statistical mechanics of complex networks[J].REVIEWS OF MODERN PHYSICS,VOLUME 74,JANUARY 2002.

通過實驗證明，P2PSM模型更有利于我們對現(xiàn)實網(wǎng)絡(luò)的認(rèn)識.P2PSM模型也有一些缺點：它只考慮了節(jié)點的加入，沒有考慮到成組的結(jié)點的刪除；在實際網(wǎng)絡(luò)中大部分節(jié)點是異質(zhì)的，我們建立模型時，把所有節(jié)點當(dāng)作同質(zhì)的進行構(gòu)造，會產(chǎn)生一些誤差.

TP393

A

1673-260X（2011）01-0023-02