基于復(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ò)模型對(duì)研究網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和行為有著重要的意義.針對(duì)現(xiàn)有模型不能全面地反映實(shí)際網(wǎng)絡(luò)提出了基于復(fù)雜網(wǎng)絡(luò)特征的P2P網(wǎng)絡(luò)模型.本文在基于組增長(zhǎng)和選擇具有較大吸引力的節(jié)點(diǎn)這些特征基礎(chǔ)上建立一個(gè)新的模型，經(jīng)過實(shí)驗(yàn)證明此模型更接近實(shí)際網(wǎng)絡(luò).

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

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

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

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

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

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

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

1 P2PSM的建立過程如下

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

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

（3）組的增長(zhǎng)：

①生成組:

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

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

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

②加入組:

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

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

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

2 舉例分析

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

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

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

（4）每加入20個(gè)節(jié)點(diǎn)計(jì)算G(ni)中每個(gè)節(jié)點(diǎn)的度數(shù).

經(jīng)過了10t的時(shí)間且加入了236條邊；經(jīng)過計(jì)算得共有6個(gè)新加入的節(jié)點(diǎn)度數(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]來分析模型的度分布，對(duì)度分布進(jìn)行數(shù)值擬合運(yùn)算可得服從冪率分布P（k）=ak-r，r=1±0.3，見圖1所示.

圖1 度分布示意圖

證明因?yàn)橥ǔ的取值都較小，所以認(rèn)為G'加入之前每個(gè)節(jié)點(diǎn)的度為k.忽略重連對(duì)G'中節(jié)點(diǎn)度的影響.每個(gè)組的加入近似看成是n個(gè)節(jié)點(diǎn)逐個(gè)加入的，每個(gè)單位時(shí)間t加入一個(gè)節(jié)點(diǎn)，并滿足：

解微分方程得：

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

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

因?yàn)楣?jié)點(diǎn)是等時(shí)間間隔添加到系統(tǒng)的，所以ti的概率分布是一個(gè)均勻離散分布列為:

帶入方程可得：

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

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

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

從表1可以看出:

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

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

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

4 結(jié)論

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

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

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

〔4〕郭雷，許曉鳴.復(fù)雜網(wǎng)絡(luò)[Z].上海：上?？萍冀逃霭嫔纾?006.

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

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

TP393

A

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