基于复杂网络特征的P2P系统模型的研究

王晓燕，毛红阁

（南阳师范学院软件学院，河南南阳473061）

基于复杂网络特征的P2P系统模型的研究

王晓燕，毛红阁

（南阳师范学院软件学院，河南南阳473061）

研究表明小世界和无尺度是很多大型复杂网络的重要特征,研究具有复杂网络特征的P2P网络模型对研究网络的拓扑结构和行为有着重要的意义.针对现有模型不能全面地反映实际网络提出了基于复杂网络特征的P2P网络模型.本文在基于组增长和选择具有较大吸引力的节点这些特征基础上建立一个新的模型，经过实验证明此模型更接近实际网络.

复杂网络；P2P；静态参数

小世界和无标度出现以后，引发了许多学者对复杂网络模型的研究.吴艾等学者提出了基于组增长的Sale-free网络模型[1],刘美玲等学者提出了择优选择节点构成的复杂网络模型研究[2]，这些研究没有考虑真实网络的大部分特征，而是一部分特征的刻画.在上述两文中节点加入网络都是以概率进行择优连接的，而在真实系统中一个节点的连接不仅与节点的度数有关而且与节点的吸引度有关[3].例如,在网络中,有些网站创建更好的内容吸引浏览者,可以在更短的时间内获得大量的连接反而超过那些创建时间很早的网站.这说明一个简单的模型相对于系统中其它的节点,有些节点能以更高的速率获得连接数量，我们把这些不同归结于节点本身具有的吸引力的大小,我们把节点具有的吸引力称之为吸引因子.为了更好的刻画实际网络，提高网络的鲁棒性，降低其脆弱性，本文对建立p2p网络模型提出了一下几点：

（1）复杂网络的形成是一个动态的成长变化的过程；

（2）网络的增长不需要全局择优，而是部分择优；

（3）网络中多个节点以组的方式加入也是网络的增长方式；

（4）新增节点与吸引因子较大的节点相连接；

综上所述，本文提出了P2PSM(P2PSystemModel)网络模型.

1 P2PSM的建立过程如下

初始网络中有n个节点，e条边，节点的吸引因子即为β，ki为结点i的度数，βi为节点i的吸引因子,模型的建立过程如下：

（1）开始时，网络中有n个节点，e条边，该网络即为G（n，e）.

（3）组的增长：

①生成组:

每次添加一组n个节点组成网络G'，模型中G'由两步得到:

a:首先,生成不同ki的规则的连接图，ki的值等于每个节点与邻居相连的边数k0(模型中k0≥3)，根据需要决定ki的多少.

b:然后，重连上述规则网络图的一些边，在G'中随机选择两个节点且vj'≠vi'，按概率p在vi'和vj'之间建立连接,0≤p≤1.p=0时为规则网络，随着p的增加，G'无序程度逐渐增加，逐渐接近随机网络.所有节点执行重连操作后，G'的总边数增加了，在0

②加入组:

每隔一定时间t,加入一组带有et条边的节点，以概率连接到局域世界G（ni），若边数ei>r，则多余的边加到G(ni)之外的节点上.

(4)在每加入1组节点后，计算G(ni)中每个节点的度数，如果某些新加入的节点（假设有s个）ei>min{ki}(ki为老节点连接新节点后的度数)，则把这s个新节点也看作老节点，则以后再加入的节点组，再以概率(i,j=1,2,…N)连接到s+r个结点上.

本算法第一步从一个小型网络开始,从现实网络来看，很多节点局部择优加入网络，网络中节点被连接的概率与节点的吸引力大小有关,并且节点的加入可能是以组的方式加入,本模型从整体上考虑了现实网络的特性,我们通过调节βi和p控制整个网络.

2 举例分析

下面举例说明，真实网络的增长过程:

（1）初始一个小网络G（30，90），即带有30个节点，90条边;

（3）每隔一定的t时间，加入一组（10个节点，k0=4，p=0.15）带有ei条边的节点以概率与G(ni)连接.

（4）每加入20个节点计算G(ni)中每个节点的度数.

经过了10t的时间且加入了236条边；经过计算得共有6个新加入的节点度数ei>{kni}.网络G（30，90）变成了新网络G（30+100，90+236）=G（130，326），G(ni)变为G(ni)(i=1,2…11).

3 参数分析

（1）通过continuum理论[4，5]来分析模型的度分布，对度分布进行数值拟合运算可得服从幂率分布P（k）=ak-r，r=1±0.3，见图1所示.

图1 度分布示意图

证明因为通常p的取值都较小，所以认为G'加入之前每个节点的度为k.忽略重连对G'中节点度的影响.每个组的加入近似看成是n个节点逐个加入的，每个单位时间t加入一个节点，并满足：

解微分方程得：

该方程的相对初始条件是每个节点i在ti时刻到达系统连通度ki(ti)=ei,所以上述解应为：

则节点连通度ki(ti)

因为节点是等时间间隔添加到系统的，所以ti的概率分布是一个均匀离散分布列为:

带入方程可得：

当t趋于＋∞时可得r=1,由于取得节点较少，所以误差很为±0.3.

（2）利用UCINET软件计算并分析P2PSM与B-A模型的静态统计量，如下表所示：

表1 静态特征参数表

从表1可以看出:

①扩展模型生成的网络其度分布也服从幂律分布，但幂指数很小，说明这个网络幂律特征没有B-A模型生成的网络明显，所以它鲁棒性更好；

②从聚集系数和最短路径上可以看出改进的模型生成的网络集聚性更强一些，由于B-A模型的全局择优机制，所以平均路径要比扩展模型的网络更短一些，但改进模型的择优更减少了节点的工作量，而改进的模型搜索速度快，这也更加符合现实网络；

③改进后的模型考虑了节点以组的方式加入，所以该模型有助于建立更接近实际的网络拓扑结构和网络的动态成长过程，从而能更准确地分析、设计和评测与网络结构和行为相关的工作.

4 结论

〔1〕吴艾，刘心松，刘丹，左朝树.基于组增长的小世界Scalefree网络模型[J].计算机科学，2005，32（7）.

〔2〕刘美玲，王仲君.择优选择节点构成的复杂网络模型研究[J].系统工程与电子技术，2006，28（4）.

〔3〕陶少华，杨春，李慧娜，张勇.基于节点吸引力的复杂网络演化模型研究[J].计算机工程，2009，35（1）.

〔4〕郭雷，许晓鸣.复杂网络[Z].上海：上海科技教育出版社，2006.

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

通过实验证明，P2PSM模型更有利于我们对现实网络的认识.P2PSM模型也有一些缺点：它只考虑了节点的加入，没有考虑到成组的结点的删除；在实际网络中大部分节点是异质的，我们建立模型时，把所有节点当作同质的进行构造，会产生一些误差.

TP393

A

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