復雜網絡理論在對等網絡特性分析中的應用?

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

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

復雜網絡理論在對等網絡特性分析中的應用?

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

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

基于現有的復雜網絡理論，研究了對等網絡的復雜特性，并就對等網絡中節點度和節點間平均最短路徑兩個特征參數進行算法設計和仿真。仿真結果表明，對等網絡中使用復雜網絡理論的特性分析理論結果與實驗結果基本一致，能準確反映對等網絡的特性。

對等網絡；復雜網絡；節點的度；最短路徑長度

1 引言

近年來對等網絡的應用越來越廣泛，如文件和數據共享及存儲、遠程協同、并行計算等［1-2］，在這些領域中對等網絡發揮著越來越重要的作用。但是，在上述對等網絡的應用研究中，研究的重點都集中在保證系統性能和安全傳輸上［3］，沒有對網絡中的節點行為進行合理分析與研究，而節點的行為特征與整個網絡系統的性能密不可分。復雜網絡理論［4-5］作為分析復雜網絡系統性能的有效工具，已經滲透到許多實際網絡系統的研究與設計中。具體來說，對于現實網絡系統的節點行為方式，使用復雜網絡理論中的平均路徑長度、聚類系數、節點的度分布等要素，能很好地描述節點行為特征。因而，復雜網絡理論逐漸成為研究復雜網絡系統的重要工具。

本文利用復雜網絡理論，對對等網絡系統節點行為的特征進行了分析，通過這些特征參數，我們能深入了解對等網絡系統節點的行為，從而幫助我們優化對等網絡系統的設計，更好地發揮對等網絡的性能。

2 復雜網絡相關理論

2.1 節點的度

節點的度是復雜網絡理論中描述具體節點的很重要的一個特征參數。一般的定義，節點的度是指整個網絡系統中與該節點連接的其他節點的數目。特別地，對于有向網絡系統來說，節點的度還分節點的入度與節點的出度兩種類型。根據節點的度的大小能定量地反映該節點在網絡系統中的重要程度，度越大意味著該節點在網絡中的地位越重要。

2.2 節點間的平均路徑長度

復雜網絡理論里，節點間的平均路徑長度是指系統中任意兩個節點之間距離的平均值。盡管實際網絡系統的規模龐大，節點數目驚人，但是網絡的平均路徑長度卻小得驚人。從這個角度上看，復雜網絡系統是具有小世界效應的。

2.3 復雜網絡模型

要很好地理解網絡結構與網絡節點行為之間的關系，就必須對網絡的模型進行分類研究。在復雜網絡理論里，描述復雜網絡系統的模型主要包括規則網絡模型、隨機網絡模型、小世界網絡模型與無標度網絡模型4種。

（1）規則網絡模型

最初的網絡模型多采用規則網絡結構，如完全規則的全局耦合網絡及最近鄰耦合網絡，前者過于稠密而后者又顯稀疏，因而不能準確反映實際網絡結構和節點行為特征。

（2）隨機網絡模型

隨機網絡起源于兩位匈牙利數學家在1960提出的ER隨機圖模型［6］，該網絡模型描述了從多個網絡節點通過相同的概率p隨機相連而形成網絡系統的過程。后來在ER隨機圖的基礎上，許多學者提出了不同概率的隨機連接思想實現擴展的ER模型［7］。

（3）小世界網絡模型

現實生活的實際網絡既不是完全隨機的也不是完全規則的。康奈爾大學的Watts［8］等人揭示了一種小世界網絡模型的雛形，并且在《Nature》雜志上發表了一篇題為《小世界網絡的群體動力學行為》的論文，這篇論文揭示了復雜網絡的小世界特性。

（4）無標度網絡模型

上面的隨機網絡模型與小世界網絡模型都屬于均勻網絡，網絡的分布模型可以用泊松分布來表示。所謂無標度網絡模型，是指網絡的度分布在網絡節點度的平均值附近出現峰值，然后迅速出現衰減的一種網絡度分布模型。

3 對等網絡的特征分析

對等網絡系統中，各個節點地位平等，不對任何系統中的節點強加任何屬性，任意節點可以自由地加入或離開該對等網絡，這樣就給整個網絡的拓撲結構帶來了隨機性。傳統上對這種類型的網絡進行理論建模分析時，一般采用的是隨機網絡模型，但是隨機網絡模型并不能準確地描述這些網絡的某些特性，例如節點度的概率分布、平均最短路徑長度、網絡節點的聚集度以及在受攻擊情況下的網絡分布特性等。基于上述這些理論分析與現實需求，本文利用復雜網絡理論，分析對等網絡的節點度分布以及最小路徑長度等重點特征參數。

（1）對等網絡節點的度分析

前面提到了復雜網絡系統中節點度的相關概念，這里我們結合對等網絡對等、動態、隨機的特點，可以看出，最直觀描述該網絡的模型就是隨機網絡模型和無標度網絡模型。因此，本節對對等網絡節點度的描述，是以隨機網絡模型與無標度網絡模型中的度的設置進行改進得出的。

在隨機網絡模型中，節點之間是以一定的概率隨機連接在一起。這里我們假定對等網絡中有N

個節點，網絡內部各節點之間都以一定的概率p隨機連接，并獨立于其他節點之間的聯系獨立存在。對等網絡中節點的度，這里我們是指與某個節點相連接的節點的數目。令對等網絡中N個節點的平均度為ˉn，由于各個節點之間的聯系是獨立的，那么隨機概率p可以表示為p=ˉn／N-1，這樣在對等網絡系統中，節點度為n的概率可以表示如下：

由等式（1）可以看出，在N值取極值時，對等網絡中節點的度呈泊松分布。在實際的復雜網絡系統中，許多網絡節點的度分布有時候呈冪律分布。設置方法如下：

公式（2）是利用累積分布函數經過改進設計得出，這樣可以消除原始冪律分布函數的消極影響，同時還保持網絡的冪律特性。因此，本文對對等網絡系統中節點度的分析，主要是利用公式（2）的計算得出。在本文第四節的仿真中，我們對公式（1）和（2）反映節點度的結果分別進行比較，得出最適合對等網絡系統的節點度的計算方法。

（2）對等網絡的節點間平均最短路徑分析

在本文的第二節提到節點間平均路徑長度的概念，這里我們也要借鑒其中的概念。另外，這里分析對等網絡中的最小路徑長度，需要介紹Newman［3］等人提出的節點度分布的生成函數。

定義1：設對等網絡系統中包含N個節點，則該網絡中任意節點度分布的生成函數可以表示成：

式中，pn表示對等網絡系統中節點度為n的概率，并且滿足F（1）=1。這里生成函數具有以下性質：

性質1：在概率pn所定義的概率空間里，所有N個節點的平均度可以用定義1中的生成函數表示如下：

性質2：對等網絡中任意節點互相獨立、地位平等，那么m個節點的聯合生成函數可以用單個節點生成函數的m次冪獲得。下面，我們以兩個節點為例來具體說明該性質：

由上面公式可以看出，xn的系數是對等網絡系統中兩個節點的度之和為n的pipj之和，不難驗證，高階次的n同樣滿足性質2，這里不進行驗證。

下面根據上述兩個性質來計算對等網絡系統中任意節點間的路徑長度。假定對等網絡中存在一度為n的節點，則對等網絡中任意節點連接到該節點的概率與該節點的度成正比。這樣，任意節點能連接到該節點的概率的生成函數可以表示如下：

對上述公式進行歸一化處理，可以得到

對于上面隨機選擇的度為n的節點，從該節點出發，可以直接達到與該節點連接的節點，然后可以向下到達下面一層連接的節點，以此類推。這樣，沿著上述任意一條路徑訪問某個節點時，與該節點連接的其他節點數的分布的生成函數可以表示如下：

由性質2可知，對于對等網絡中某一特定的節點，它的第二層相連的節點（也就是與第一層節點直接相連的其他節點）總數的概率分布生成函數可以表示為

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

由公式（4）與公式（10）可知與對等網絡系統中指定節點相連的節點以及第二層接連的節點的度的平均度。將公式（2）分別代入式（4）和式（10），假定對等網絡系統中節點度的最大值為nmax，則有

由文獻［9］可知，對具有N個節點的冪律指數為α的復雜網絡系統而言，所有節點的最大度可以表示如下：

由上述分析可知，F′（1）與F′（1）F′1（1）分別代表與指定節點相連的節點數量的平均度，令

以此類推第i層節點數量的平均度記作Li，可以得到

根據上述公式推導，下面我們來分析對等網絡系統中任意兩節點的最短路徑長度。假定對等網絡中存在兩個節點a、b以及兩節點間的最短路徑長度s，可以看出s表示為節點a與b之間從第一層到第s層的層數，且是最短的。同時在對等網絡系統中，節點與節點通過各種連接與多種層次連接的節點總數（包括直接或間接連接的）為（N-1），可以得出

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

對于對等網絡系統而言，節點的數量級別一般在104～105左右，因此節點的數量N?L1、L2。這樣公式（20）可以表示為

現在我們代入公式（14）與公式（16），可以得出對等網絡系統中的節點最短路徑長度：

由公式（22）可知：對等網絡系統中，節點間的最短路徑長度主要與這個網絡系統的節點規模相關，對等網絡系統的冪律指數不起主要作用。

4 仿真與討論

本實驗以典型的對等網絡系統Gnutella為仿真場景，通過P2Psim軟件建立Gnutella網絡環境，分析對等網絡節點行為的度分布、平均路徑長度兩種特征。設每個用戶共享帶寬為5 Mbit／s，定義系統中擁有節點用戶數為50 000個，0≤n≤nmax（節點度大小為n的節點），s為對等網絡中最小路徑長度。

（1）節點度分布與節點數量的關系

根據公式（1）與公式（2）分別對應的隨機網絡模型和無標度網絡模型對應的節點度計算方法，分別與節點實際的度分布數據進行對比，如圖1所示，可以看出，無標度網絡模型的度分布計算方法得出的數據更加接近實際的度分布，這與第三節的理論分析基本吻合。

圖1 節點度分布與節點數量的關系Fig.1 The relationship between the degree distribution of peers and the number of peers

（2）節點間的最短路徑分析

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

表1 實驗數據與模型數據比較Table 1 Comparison between experimental data and model data

5 結論

本文基于復雜網絡理論，對對等網絡中網絡行為的特征進行了深入分析。這些特征主要包括節點的度、平均路徑長度等衡量參數，這些參數作為對等網絡的重要特征量，直接關系到諸如對等網絡系統路由、拓撲結構等性能的優化和改進。實驗結果表明，本文給出的特征分析結果具有一定的合理性，能很好地體現對等網絡的節點行為特征。然而，對于類似P2P網絡這樣的復雜網絡，還需結合具體的網絡架構進行特征分析，從而豐富本文的理論，更好地描述對等網絡的節點行為特征，這將是下一步的研究重點。

［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］汪小帆，李翔，陳關榮.復雜網絡理論與及其應用［M］.北京：清華大學出版社，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.有序與無序之間的網絡動力學［M］.陳禹，譯.北京：中國人民大學出版社，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年獲學士學位，現為教授、博士生導師，主要研究方向為計算機通信網、信息保密與安全；

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—），女，浙江臺州人，2007年獲碩士學位，現為博士研究生，主要研究方向為信息安全、視頻編解碼技術；

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年獲博士學位，現為教授、博士生導師，主要研究方向為信息安全、信號與信息處理；

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年獲博士學位，現為副研究員、碩士生導師，主要研究方向為信息安全、密碼協議、多媒體信息處理及內容安全。

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年獲碩士學位，現為博士研究生，主要研究方向為網絡安全、計算機通信網；

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

2011-12-20；

2012-03-13

國家重點基礎研究發展規劃（973計劃）項目（2010CB731403／2010CB731406）；國家自然科學基金資助項目（61071152／61171173）