復(fù)雜網(wǎng)絡(luò)理論在對(duì)等網(wǎng)絡(luò)特性分析中的應(yīng)用?

彭浩，陸松年，，趙丹丹，李生紅，，張愛新

（1.上海交通大學(xué)電子工程系，上海200240；2.上海交通大學(xué)信息安全學(xué)院，上海200240）

復(fù)雜網(wǎng)絡(luò)理論在對(duì)等網(wǎng)絡(luò)特性分析中的應(yīng)用?

彭浩1，陸松年1，2，趙丹丹1，李生紅1，2，張愛新2

（1.上海交通大學(xué)電子工程系，上海200240；2.上海交通大學(xué)信息安全學(xué)院，上海200240）

基于現(xiàn)有的復(fù)雜網(wǎng)絡(luò)理論，研究了對(duì)等網(wǎng)絡(luò)的復(fù)雜特性，并就對(duì)等網(wǎng)絡(luò)中節(jié)點(diǎn)度和節(jié)點(diǎn)間平均最短路徑兩個(gè)特征參數(shù)進(jìn)行算法設(shè)計(jì)和仿真。仿真結(jié)果表明，對(duì)等網(wǎng)絡(luò)中使用復(fù)雜網(wǎng)絡(luò)理論的特性分析理論結(jié)果與實(shí)驗(yàn)結(jié)果基本一致，能準(zhǔn)確反映對(duì)等網(wǎng)絡(luò)的特性。

對(duì)等網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)；節(jié)點(diǎn)的度；最短路徑長(zhǎng)度

1 引言

近年來(lái)對(duì)等網(wǎng)絡(luò)的應(yīng)用越來(lái)越廣泛，如文件和數(shù)據(jù)共享及存儲(chǔ)、遠(yuǎn)程協(xié)同、并行計(jì)算等［1-2］，在這些領(lǐng)域中對(duì)等網(wǎng)絡(luò)發(fā)揮著越來(lái)越重要的作用。但是，在上述對(duì)等網(wǎng)絡(luò)的應(yīng)用研究中，研究的重點(diǎn)都集中在保證系統(tǒng)性能和安全傳輸上［3］，沒(méi)有對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)行為進(jìn)行合理分析與研究，而節(jié)點(diǎn)的行為特征與整個(gè)網(wǎng)絡(luò)系統(tǒng)的性能密不可分。復(fù)雜網(wǎng)絡(luò)理論［4-5］作為分析復(fù)雜網(wǎng)絡(luò)系統(tǒng)性能的有效工具，已經(jīng)滲透到許多實(shí)際網(wǎng)絡(luò)系統(tǒng)的研究與設(shè)計(jì)中。具體來(lái)說(shuō)，對(duì)于現(xiàn)實(shí)網(wǎng)絡(luò)系統(tǒng)的節(jié)點(diǎn)行為方式，使用復(fù)雜網(wǎng)絡(luò)理論中的平均路徑長(zhǎng)度、聚類系數(shù)、節(jié)點(diǎn)的度分布等要素，能很好地描述節(jié)點(diǎn)行為特征。因而，復(fù)雜網(wǎng)絡(luò)理論逐漸成為研究復(fù)雜網(wǎng)絡(luò)系統(tǒng)的重要工具。

本文利用復(fù)雜網(wǎng)絡(luò)理論，對(duì)對(duì)等網(wǎng)絡(luò)系統(tǒng)節(jié)點(diǎn)行為的特征進(jìn)行了分析，通過(guò)這些特征參數(shù)，我們能深入了解對(duì)等網(wǎng)絡(luò)系統(tǒng)節(jié)點(diǎn)的行為，從而幫助我們優(yōu)化對(duì)等網(wǎng)絡(luò)系統(tǒng)的設(shè)計(jì)，更好地發(fā)揮對(duì)等網(wǎng)絡(luò)的性能。

2 復(fù)雜網(wǎng)絡(luò)相關(guān)理論

2.1 節(jié)點(diǎn)的度

節(jié)點(diǎn)的度是復(fù)雜網(wǎng)絡(luò)理論中描述具體節(jié)點(diǎn)的很重要的一個(gè)特征參數(shù)。一般的定義，節(jié)點(diǎn)的度是指整個(gè)網(wǎng)絡(luò)系統(tǒng)中與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目。特別地，對(duì)于有向網(wǎng)絡(luò)系統(tǒng)來(lái)說(shuō)，節(jié)點(diǎn)的度還分節(jié)點(diǎn)的入度與節(jié)點(diǎn)的出度兩種類型。根據(jù)節(jié)點(diǎn)的度的大小能定量地反映該節(jié)點(diǎn)在網(wǎng)絡(luò)系統(tǒng)中的重要程度，度越大意味著該節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位越重要。

2.2 節(jié)點(diǎn)間的平均路徑長(zhǎng)度

復(fù)雜網(wǎng)絡(luò)理論里，節(jié)點(diǎn)間的平均路徑長(zhǎng)度是指系統(tǒng)中任意兩個(gè)節(jié)點(diǎn)之間距離的平均值。盡管實(shí)際網(wǎng)絡(luò)系統(tǒng)的規(guī)模龐大，節(jié)點(diǎn)數(shù)目驚人，但是網(wǎng)絡(luò)的平均路徑長(zhǎng)度卻小得驚人。從這個(gè)角度上看，復(fù)雜網(wǎng)絡(luò)系統(tǒng)是具有小世界效應(yīng)的。

2.3 復(fù)雜網(wǎng)絡(luò)模型

要很好地理解網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)節(jié)點(diǎn)行為之間的關(guān)系，就必須對(duì)網(wǎng)絡(luò)的模型進(jìn)行分類研究。在復(fù)雜網(wǎng)絡(luò)理論里，描述復(fù)雜網(wǎng)絡(luò)系統(tǒng)的模型主要包括規(guī)則網(wǎng)絡(luò)模型、隨機(jī)網(wǎng)絡(luò)模型、小世界網(wǎng)絡(luò)模型與無(wú)標(biāo)度網(wǎng)絡(luò)模型4種。

（1）規(guī)則網(wǎng)絡(luò)模型

最初的網(wǎng)絡(luò)模型多采用規(guī)則網(wǎng)絡(luò)結(jié)構(gòu)，如完全規(guī)則的全局耦合網(wǎng)絡(luò)及最近鄰耦合網(wǎng)絡(luò)，前者過(guò)于稠密而后者又顯稀疏，因而不能準(zhǔn)確反映實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)行為特征。

（2）隨機(jī)網(wǎng)絡(luò)模型

隨機(jī)網(wǎng)絡(luò)起源于兩位匈牙利數(shù)學(xué)家在1960提出的ER隨機(jī)圖模型［6］，該網(wǎng)絡(luò)模型描述了從多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)相同的概率p隨機(jī)相連而形成網(wǎng)絡(luò)系統(tǒng)的過(guò)程。后來(lái)在ER隨機(jī)圖的基礎(chǔ)上，許多學(xué)者提出了不同概率的隨機(jī)連接思想實(shí)現(xiàn)擴(kuò)展的ER模型［7］。

（3）小世界網(wǎng)絡(luò)模型

現(xiàn)實(shí)生活的實(shí)際網(wǎng)絡(luò)既不是完全隨機(jī)的也不是完全規(guī)則的?？的螤柎髮W(xué)的Watts［8］等人揭示了一種小世界網(wǎng)絡(luò)模型的雛形，并且在《Nature》雜志上發(fā)表了一篇題為《小世界網(wǎng)絡(luò)的群體動(dòng)力學(xué)行為》的論文，這篇論文揭示了復(fù)雜網(wǎng)絡(luò)的小世界特性。

（4）無(wú)標(biāo)度網(wǎng)絡(luò)模型

上面的隨機(jī)網(wǎng)絡(luò)模型與小世界網(wǎng)絡(luò)模型都屬于均勻網(wǎng)絡(luò)，網(wǎng)絡(luò)的分布模型可以用泊松分布來(lái)表示。所謂無(wú)標(biāo)度網(wǎng)絡(luò)模型，是指網(wǎng)絡(luò)的度分布在網(wǎng)絡(luò)節(jié)點(diǎn)度的平均值附近出現(xiàn)峰值，然后迅速出現(xiàn)衰減的一種網(wǎng)絡(luò)度分布模型。

3 對(duì)等網(wǎng)絡(luò)的特征分析

對(duì)等網(wǎng)絡(luò)系統(tǒng)中，各個(gè)節(jié)點(diǎn)地位平等，不對(duì)任何系統(tǒng)中的節(jié)點(diǎn)強(qiáng)加任何屬性，任意節(jié)點(diǎn)可以自由地加入或離開該對(duì)等網(wǎng)絡(luò)，這樣就給整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)帶來(lái)了隨機(jī)性。傳統(tǒng)上對(duì)這種類型的網(wǎng)絡(luò)進(jìn)行理論建模分析時(shí)，一般采用的是隨機(jī)網(wǎng)絡(luò)模型，但是隨機(jī)網(wǎng)絡(luò)模型并不能準(zhǔn)確地描述這些網(wǎng)絡(luò)的某些特性，例如節(jié)點(diǎn)度的概率分布、平均最短路徑長(zhǎng)度、網(wǎng)絡(luò)節(jié)點(diǎn)的聚集度以及在受攻擊情況下的網(wǎng)絡(luò)分布特性等。基于上述這些理論分析與現(xiàn)實(shí)需求，本文利用復(fù)雜網(wǎng)絡(luò)理論，分析對(duì)等網(wǎng)絡(luò)的節(jié)點(diǎn)度分布以及最小路徑長(zhǎng)度等重點(diǎn)特征參數(shù)。

（1）對(duì)等網(wǎng)絡(luò)節(jié)點(diǎn)的度分析

前面提到了復(fù)雜網(wǎng)絡(luò)系統(tǒng)中節(jié)點(diǎn)度的相關(guān)概念，這里我們結(jié)合對(duì)等網(wǎng)絡(luò)對(duì)等、動(dòng)態(tài)、隨機(jī)的特點(diǎn)，可以看出，最直觀描述該網(wǎng)絡(luò)的模型就是隨機(jī)網(wǎng)絡(luò)模型和無(wú)標(biāo)度網(wǎng)絡(luò)模型。因此，本節(jié)對(duì)對(duì)等網(wǎng)絡(luò)節(jié)點(diǎn)度的描述，是以隨機(jī)網(wǎng)絡(luò)模型與無(wú)標(biāo)度網(wǎng)絡(luò)模型中的度的設(shè)置進(jìn)行改進(jìn)得出的。

在隨機(jī)網(wǎng)絡(luò)模型中，節(jié)點(diǎn)之間是以一定的概率隨機(jī)連接在一起。這里我們假定對(duì)等網(wǎng)絡(luò)中有N

個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)內(nèi)部各節(jié)點(diǎn)之間都以一定的概率p隨機(jī)連接，并獨(dú)立于其他節(jié)點(diǎn)之間的聯(lián)系獨(dú)立存在。對(duì)等網(wǎng)絡(luò)中節(jié)點(diǎn)的度，這里我們是指與某個(gè)節(jié)點(diǎn)相連接的節(jié)點(diǎn)的數(shù)目。令對(duì)等網(wǎng)絡(luò)中N個(gè)節(jié)點(diǎn)的平均度為ˉn，由于各個(gè)節(jié)點(diǎn)之間的聯(lián)系是獨(dú)立的，那么隨機(jī)概率p可以表示為p=ˉn／N-1，這樣在對(duì)等網(wǎng)絡(luò)系統(tǒng)中，節(jié)點(diǎn)度為n的概率可以表示如下：

由等式（1）可以看出，在N值取極值時(shí)，對(duì)等網(wǎng)絡(luò)中節(jié)點(diǎn)的度呈泊松分布。在實(shí)際的復(fù)雜網(wǎng)絡(luò)系統(tǒng)中，許多網(wǎng)絡(luò)節(jié)點(diǎn)的度分布有時(shí)候呈冪律分布。設(shè)置方法如下：

公式（2）是利用累積分布函數(shù)經(jīng)過(guò)改進(jìn)設(shè)計(jì)得出，這樣可以消除原始冪律分布函數(shù)的消極影響，同時(shí)還保持網(wǎng)絡(luò)的冪律特性。因此，本文對(duì)對(duì)等網(wǎng)絡(luò)系統(tǒng)中節(jié)點(diǎn)度的分析，主要是利用公式（2）的計(jì)算得出。在本文第四節(jié)的仿真中，我們對(duì)公式（1）和（2）反映節(jié)點(diǎn)度的結(jié)果分別進(jìn)行比較，得出最適合對(duì)等網(wǎng)絡(luò)系統(tǒng)的節(jié)點(diǎn)度的計(jì)算方法。

（2）對(duì)等網(wǎng)絡(luò)的節(jié)點(diǎn)間平均最短路徑分析

在本文的第二節(jié)提到節(jié)點(diǎn)間平均路徑長(zhǎng)度的概念，這里我們也要借鑒其中的概念。另外，這里分析對(duì)等網(wǎng)絡(luò)中的最小路徑長(zhǎng)度，需要介紹Newman［3］等人提出的節(jié)點(diǎn)度分布的生成函數(shù)。

定義1：設(shè)對(duì)等網(wǎng)絡(luò)系統(tǒng)中包含N個(gè)節(jié)點(diǎn)，則該網(wǎng)絡(luò)中任意節(jié)點(diǎn)度分布的生成函數(shù)可以表示成：

式中，pn表示對(duì)等網(wǎng)絡(luò)系統(tǒng)中節(jié)點(diǎn)度為n的概率，并且滿足F（1）=1。這里生成函數(shù)具有以下性質(zhì)：

性質(zhì)1：在概率pn所定義的概率空間里，所有N個(gè)節(jié)點(diǎn)的平均度可以用定義1中的生成函數(shù)表示如下：

性質(zhì)2：對(duì)等網(wǎng)絡(luò)中任意節(jié)點(diǎn)互相獨(dú)立、地位平等，那么m個(gè)節(jié)點(diǎn)的聯(lián)合生成函數(shù)可以用單個(gè)節(jié)點(diǎn)生成函數(shù)的m次冪獲得。下面，我們以兩個(gè)節(jié)點(diǎn)為例來(lái)具體說(shuō)明該性質(zhì)：

由上面公式可以看出，xn的系數(shù)是對(duì)等網(wǎng)絡(luò)系統(tǒng)中兩個(gè)節(jié)點(diǎn)的度之和為n的pipj之和，不難驗(yàn)證，高階次的n同樣滿足性質(zhì)2，這里不進(jìn)行驗(yàn)證。

下面根據(jù)上述兩個(gè)性質(zhì)來(lái)計(jì)算對(duì)等網(wǎng)絡(luò)系統(tǒng)中任意節(jié)點(diǎn)間的路徑長(zhǎng)度。假定對(duì)等網(wǎng)絡(luò)中存在一度為n的節(jié)點(diǎn)，則對(duì)等網(wǎng)絡(luò)中任意節(jié)點(diǎn)連接到該節(jié)點(diǎn)的概率與該節(jié)點(diǎn)的度成正比。這樣，任意節(jié)點(diǎn)能連接到該節(jié)點(diǎn)的概率的生成函數(shù)可以表示如下：

對(duì)上述公式進(jìn)行歸一化處理，可以得到

對(duì)于上面隨機(jī)選擇的度為n的節(jié)點(diǎn)，從該節(jié)點(diǎn)出發(fā)，可以直接達(dá)到與該節(jié)點(diǎn)連接的節(jié)點(diǎn)，然后可以向下到達(dá)下面一層連接的節(jié)點(diǎn)，以此類推。這樣，沿著上述任意一條路徑訪問(wèn)某個(gè)節(jié)點(diǎn)時(shí)，與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)數(shù)的分布的生成函數(shù)可以表示如下：

由性質(zhì)2可知，對(duì)于對(duì)等網(wǎng)絡(luò)中某一特定的節(jié)點(diǎn)，它的第二層相連的節(jié)點(diǎn)（也就是與第一層節(jié)點(diǎn)直接相連的其他節(jié)點(diǎn)）總數(shù)的概率分布生成函數(shù)可以表示為

與上述公式類似，可以推算與網(wǎng)絡(luò)中某一特定的節(jié)點(diǎn)相連的第三層相連的節(jié)點(diǎn)總數(shù)的概率分布生成函數(shù)可以表示為F（F1（F1（x））），以此類推其他各層相連節(jié)點(diǎn)的。這樣根據(jù)公式（9）可知，與該節(jié)點(diǎn)第二層相連的所有節(jié)點(diǎn)平均度可以計(jì)算如下：

由公式（4）與公式（10）可知與對(duì)等網(wǎng)絡(luò)系統(tǒng)中指定節(jié)點(diǎn)相連的節(jié)點(diǎn)以及第二層接連的節(jié)點(diǎn)的度的平均度。將公式（2）分別代入式（4）和式（10），假定對(duì)等網(wǎng)絡(luò)系統(tǒng)中節(jié)點(diǎn)度的最大值為nmax，則有

由文獻(xiàn)［9］可知，對(duì)具有N個(gè)節(jié)點(diǎn)的冪律指數(shù)為α的復(fù)雜網(wǎng)絡(luò)系統(tǒng)而言，所有節(jié)點(diǎn)的最大度可以表示如下：

由上述分析可知，F(xiàn)′（1）與F′（1）F′1（1）分別代表與指定節(jié)點(diǎn)相連的節(jié)點(diǎn)數(shù)量的平均度，令

以此類推第i層節(jié)點(diǎn)數(shù)量的平均度記作Li，可以得到

根據(jù)上述公式推導(dǎo)，下面我們來(lái)分析對(duì)等網(wǎng)絡(luò)系統(tǒng)中任意兩節(jié)點(diǎn)的最短路徑長(zhǎng)度。假定對(duì)等網(wǎng)絡(luò)中存在兩個(gè)節(jié)點(diǎn)a、b以及兩節(jié)點(diǎn)間的最短路徑長(zhǎng)度s，可以看出s表示為節(jié)點(diǎn)a與b之間從第一層到第s層的層數(shù)，且是最短的。同時(shí)在對(duì)等網(wǎng)絡(luò)系統(tǒng)中，節(jié)點(diǎn)與節(jié)點(diǎn)通過(guò)各種連接與多種層次連接的節(jié)點(diǎn)總數(shù)（包括直接或間接連接的）為（N-1），可以得出

將公式（18）代入式（19），可以得出

對(duì)于對(duì)等網(wǎng)絡(luò)系統(tǒng)而言，節(jié)點(diǎn)的數(shù)量級(jí)別一般在104～105左右，因此節(jié)點(diǎn)的數(shù)量N?L1、L2。這樣公式（20）可以表示為

現(xiàn)在我們代入公式（14）與公式（16），可以得出對(duì)等網(wǎng)絡(luò)系統(tǒng)中的節(jié)點(diǎn)最短路徑長(zhǎng)度：

由公式（22）可知：對(duì)等網(wǎng)絡(luò)系統(tǒng)中，節(jié)點(diǎn)間的最短路徑長(zhǎng)度主要與這個(gè)網(wǎng)絡(luò)系統(tǒng)的節(jié)點(diǎn)規(guī)模相關(guān)，對(duì)等網(wǎng)絡(luò)系統(tǒng)的冪律指數(shù)不起主要作用。

4 仿真與討論

本實(shí)驗(yàn)以典型的對(duì)等網(wǎng)絡(luò)系統(tǒng)Gnutella為仿真場(chǎng)景，通過(guò)P2Psim軟件建立Gnutella網(wǎng)絡(luò)環(huán)境，分析對(duì)等網(wǎng)絡(luò)節(jié)點(diǎn)行為的度分布、平均路徑長(zhǎng)度兩種特征。設(shè)每個(gè)用戶共享帶寬為5 Mbit／s，定義系統(tǒng)中擁有節(jié)點(diǎn)用戶數(shù)為50 000個(gè)，0≤n≤nmax（節(jié)點(diǎn)度大小為n的節(jié)點(diǎn)），s為對(duì)等網(wǎng)絡(luò)中最小路徑長(zhǎng)度。

（1）節(jié)點(diǎn)度分布與節(jié)點(diǎn)數(shù)量的關(guān)系

根據(jù)公式（1）與公式（2）分別對(duì)應(yīng)的隨機(jī)網(wǎng)絡(luò)模型和無(wú)標(biāo)度網(wǎng)絡(luò)模型對(duì)應(yīng)的節(jié)點(diǎn)度計(jì)算方法，分別與節(jié)點(diǎn)實(shí)際的度分布數(shù)據(jù)進(jìn)行對(duì)比，如圖1所示，可以看出，無(wú)標(biāo)度網(wǎng)絡(luò)模型的度分布計(jì)算方法得出的數(shù)據(jù)更加接近實(shí)際的度分布，這與第三節(jié)的理論分析基本吻合。

圖1 節(jié)點(diǎn)度分布與節(jié)點(diǎn)數(shù)量的關(guān)系Fig.1 The relationship between the degree distribution of peers and the number of peers

（2）節(jié)點(diǎn)間的最短路徑分析

在本文第3節(jié)我們提到，無(wú)標(biāo)度網(wǎng)絡(luò)模型更加適合用來(lái)分析對(duì)等網(wǎng)絡(luò)系統(tǒng)節(jié)點(diǎn)的行為分析，因此這里我們基于P2Psim軟件運(yùn)行的數(shù)據(jù)，將實(shí)驗(yàn)結(jié)果的理論數(shù)據(jù)（即公式（22）所反映的最短路徑計(jì)算方法）與實(shí)際數(shù)據(jù)通過(guò)Pajek軟件［9］進(jìn)行分析，比較結(jié)果如表1所示?？梢钥闯?，我們?cè)诠?jié)點(diǎn)規(guī)?？刂圃?2 500、25 000、37 500、50 000分別進(jìn)行分析，實(shí)際數(shù)據(jù)與無(wú)標(biāo)度網(wǎng)絡(luò)模型的最短路徑長(zhǎng)度誤差基本控制在10%左右（這里是對(duì)所有節(jié)點(diǎn)最短路徑取了平均值，因此精確到小數(shù)點(diǎn)后3位）；由于復(fù)雜網(wǎng)絡(luò)系統(tǒng)的小世界特性，最短路徑長(zhǎng)度一般不會(huì)超過(guò)7，因此誤差在10%完全可以忽略。同時(shí)我們可以看到，理論分析數(shù)據(jù)與實(shí)際數(shù)據(jù)存在一定的差異性。產(chǎn)生該差異的原因主要包括兩點(diǎn)：首先，是我們?cè)谶M(jìn)行理論分析的過(guò)程中，為了討論的連續(xù)性，對(duì)數(shù)據(jù)進(jìn)行了近似處理，如公式（14）和公式（21）的近似處理；其次，我們?cè)趯?shí)際數(shù)據(jù)收集的過(guò)程中，存在許多不確定因素，如仿真環(huán)境、網(wǎng)絡(luò)帶寬、仿真主機(jī)的數(shù)據(jù)處理能力等。上述兩點(diǎn)因素的相互影響，分別對(duì)理論數(shù)據(jù)和實(shí)際數(shù)據(jù)產(chǎn)生了一定的影響，就對(duì)等網(wǎng)絡(luò)仿真實(shí)驗(yàn)的結(jié)果而言，誤差范圍控制在±15%內(nèi)都可以接受，顯然這里的數(shù)據(jù)對(duì)比結(jié)果完全可以滿足仿真實(shí)驗(yàn)的要求。因此，本文第三節(jié)給出的對(duì)等網(wǎng)絡(luò)系統(tǒng)中節(jié)點(diǎn)間最短路徑的理論分析具有一定的正確性和合理性。

表1 實(shí)驗(yàn)數(shù)據(jù)與模型數(shù)據(jù)比較Table 1 Comparison between experimental data and model data

5 結(jié)論

本文基于復(fù)雜網(wǎng)絡(luò)理論，對(duì)對(duì)等網(wǎng)絡(luò)中網(wǎng)絡(luò)行為的特征進(jìn)行了深入分析。這些特征主要包括節(jié)點(diǎn)的度、平均路徑長(zhǎng)度等衡量參數(shù)，這些參數(shù)作為對(duì)等網(wǎng)絡(luò)的重要特征量，直接關(guān)系到諸如對(duì)等網(wǎng)絡(luò)系統(tǒng)路由、拓?fù)浣Y(jié)構(gòu)等性能的優(yōu)化和改進(jìn)。實(shí)驗(yàn)結(jié)果表明，本文給出的特征分析結(jié)果具有一定的合理性，能很好地體現(xiàn)對(duì)等網(wǎng)絡(luò)的節(jié)點(diǎn)行為特征。然而，對(duì)于類似P2P網(wǎng)絡(luò)這樣的復(fù)雜網(wǎng)絡(luò)，還需結(jié)合具體的網(wǎng)絡(luò)架構(gòu)進(jìn)行特征分析，從而豐富本文的理論，更好地描述對(duì)等網(wǎng)絡(luò)的節(jié)點(diǎn)行為特征，這將是下一步的研究重點(diǎn)。

［1］Newman M E J.The Structure and Function of Complex Net -works［J］.SIAM Review，2003，45（2）：167-256.

［2］Ravoaja Aina，Anceaume Emmanuelle.STORM：A Secure Overlay for P2PReputation Management［C］／／Proceedings of the First InternationalConference on Self-Adaptiveand Self-Organizing Systems.Boston，Mass，USA：IEEE，2007：247-256.

［3］Feng Qinyuan，Wu Yu，Sun Yan，etal.User BehaviorModeling in Peer-to-Peer File Sharing Networks：Dissecting Download and Removal Actions［C］／／Proceedings of 2009 IEEE International Conference on Acoustics，Speechand Signal Processing.Taipei，China：IEEE，2009：3477-3480.

［4］Wang X，Chen G.Synchronization in scale-free dynamical networks：robustness and fragility［J］.IEEE Transactions on Circuits and Systems，2002，49（1）：54-61.

［5］Li Xiang，Chen Guan-rong.A local-world evolving networkmodel［J］.Physical A，2003，328（1／2）：274-279.

［6］汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論與及其應(yīng)用［M］.北京：清華大學(xué)出版社，2005：9-33. WANG Xiao-fan，LI Xiang，CHEN Guan-rong.Complex network theory and its application［M］.Beijing：Tsinghua University Press，2005：9-33.（in Chinese）

［7］Watts D.有序與無(wú)序之間的網(wǎng)絡(luò)動(dòng)力學(xué)［M］.陳禹，譯.北京：中國(guó)人民大學(xué)出版社，2006：114-132. Watts D.Network dynamics between order and disorder［M］. Translated by CHEN Yu.Beijing：Renmin University of China Press，2006：114-132.（in Chinese）

［8］Watts D J，Strogatz S H.Collective dynamics of‘small world’networks［J］.Nature，1998（393）：440-442.

［9］Batagelj V，Mrvar A.Pajek-analysis and visualization of large networks［C］／／Processing of Graph Drawing Software. Springer，Berlin：IEEE，2003：77-103.

PENG Hao was born in Taixing，Jiangsu Province，in 1982.He received the M.S.degree in 2007.He is currently working toward the Ph.D.degree.His research concerns network security，computer communication networks.

Email：penghao2007＠sjtu.edu.cn

陸松年（1947—），男，上海人，1982年獲學(xué)士學(xué)位，現(xiàn)為教授、博士生導(dǎo)師，主要研究方向?yàn)橛?jì)算機(jī)通信網(wǎng)、信息保密與安全；

LU Song-nian was born in Shanghai，in 1947.He received the B.S.degree in 1982.He isnow a professor and also the Ph.D. supervisor.His research concerns computer communication networks，information secracy and security.

Email：snlu＠sjtu.edu.cn

趙丹丹（1981—），女，浙江臺(tái)州人，2007年獲碩士學(xué)位，現(xiàn)為博士研究生，主要研究方向?yàn)樾畔踩?、視頻編解碼技術(shù)；

ZHAO Dan-dan was born in Taizhou，Zhejiang Province，in 1981.She received the M.S.degree in 2007.She is currently working toward the Ph.D.degree.Her research concerns information security and video codec technology.

Email：zhaodandan＠sjtu.edu.cn

李生紅（1971—），男，遼寧葫蘆島人，1999年獲博士學(xué)位，現(xiàn)為教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔踩?、信?hào)與信息處理；

LISheng-hong was born in Huludao，Liaoning Province，in 1971.He received the Ph.D.degree in 1999.He is now a professor and also the Ph.D.supervisor.His research concerns information security，signal and information processing.

Email：shli＠sjtu.edu.cn

張愛新（1973—），女，上海人，2003年獲博士學(xué)位，現(xiàn)為副研究員、碩士生導(dǎo)師，主要研究方向?yàn)樾畔踩?、密碼協(xié)議、多媒體信息處理及內(nèi)容安全。

ZHANG Ai-xin was born in Shanghai，in 1973.She received the Ph.D.degree in 2003.She is now an associate research fellow and also the instructor of graduate students.Her research concerns information security，cryptographic protocols，multimedia information processing，and content security.

Email：axzhang＠sjtu.edu.cn

Application of Com plex Network Theory in Characteristics Analysis of Peer to Peer Networks

PENGHao1，LU Song-nian1，2，ZHAO Dan-dan1，LISheng-hong1，2，ZHANGAi-xin2
（1.Department of Electronic Engineering，Shanghai Jiaotong University，Shanghai200240，China；2.School of Information Security，Shanghai Jiaotong University，Shanghai200240，China）

According to the existing complex network theory，the complexity characteristics of peer to peer network are studied and then the achievement algorithm of two characteristic parameters including the degree of peers and the average shortest path between peers is designed and simulated.Simulation results show that the theoretical results using the analysis of the characteristics of the complex network theory are basically consistent with the experimental data results and the theoretical results can accurately reflect the characteristics of peer to peer network.

P2P（Peer to Peer networks）；complex network；the degree of a peer；the shortest path length

The National Program on key Basic Research Project（973 Program）（2010CB731403／2010CB731406）；The National Natural Science Foundation of China（No.61071152／61171173）

TP393.01

A

10.3969／j.issn.1001-893x.2012.04.030

彭浩（1982—），男，江蘇泰興人，2007年獲碩士學(xué)位，現(xiàn)為博士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、計(jì)算機(jī)通信網(wǎng)；

1001-893X（2012）04-0571-05

2011-12-20；

2012-03-13

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃（973計(jì)劃）項(xiàng)目（2010CB731403／2010CB731406）；國(guó)家自然科學(xué)基金資助項(xiàng)目（61071152／61171173）