小世界网络的短接边的讨论

马丽红 王宝丽 李 策

(1.河北建筑工程学院，河北张家口075024;2.北京交通大学海滨学院黄骅061100)

1 引言

网络作为一门学科应该是从Euler开创图论学算起，近年来复杂网络引起人们极大的兴趣.在社会系统中，朋友或熟人关系网络是最基本的网络［1，2，3］.有人曾经做过一个实验，实验要求参与者把一封信通过熟人传送给指定的某个人，借此找出熟人关系网中路径长度的分布.统计显示平均依次经过6个熟人就可传达到，这就是著名的“六度分离”.规则网络是秩序的象征，随机网络是混乱的代表，现实网络不可能是它们中的任何一个可代表的，于是由Watts和Strogatz提出著名的小世界模型［4，5，6］.

小世界网络模型的描述:

给定规则网络:假如网络的节点总数为N，每个节点与它最近邻的个节点连接，要求.

改变旧连线:以概率p为规则网络的每条旧连线重新连接，将该连线的一个端点随机的放到一个新位置上，不包括自身的连线和重复连线.

下面我们用平均场理论来研究小世界网络的性质:

2 平均场理论

2.1 模型的微小变化

在模型中选择任意两点短接，同时没有边从规则网络中删除.对于大尺度网络连接概率为p2k－1时距离都是一样的，当概率为p2k或更高时l就会产生变化.文中将会给出具体介绍.

2.2 连续变化的模型

考虑半径r的邻域，邻域是指属于r邻域的点或不属于它的点，m(r)为不属于A的r邻域的点子数，为单位长度的不属于A的r邻域的点子数.n(r)为A的r，邻域的空隙数单位长度的A的r邻域的空隙数.如图所示

由此可得出

公式(2)中随着r的增加n的增长率.当r增加dr时，r的邻边将覆盖短接点，另外一端将生长出新的点.另外一项是当r变为r+dr时，空隙点将减少或消失，减少的概率为个空隙的概率为，由(2)式可得(3)

L=ξ和L?ξ分别对应着和

由式(2)和(3)消去r，可得

可解的(4)式为

如果1=L=ξ或1=ξ=L，则(6)式是小世界网络的微分解.

当L→∞ 时，考虑到th(x1+x2)=(thx1+thx2)/1+thx1thx2，可得到

距离r的平均函数A(r)可表示为

2.3 讨论

考虑到r和让

上式表明当x=1时，短接边比较少;当x?1时，短接边比较多.

3 重整化群变换［7］

考虑重整化变换情况如下:

3.1 当 k=1 时

在一对相邻点中加入一个点生成一个一维的格子，这个格子中有许多点.如果加入的点和其它的点连接，重整化的格子中两个点连接在一起.变换下的保留的短接边的数目为s=pLk=pL.则

重整化前后任何两个点短接的概率是不一样的，对于大的L和小的p

因为L?1，p=1，将(15)、(16)式代入(14)式，发现

3.2 当k ＞1时

重整化变换形式如上.

通过上面理论分析可知，小世界网络在p值较小的一个范围内，具有较大的群集系数和短的平均路径，这种现象被称为小世界效应.许多现实网络都具有小世界效应.

［1］D.J.Watts and S.H.Strogatz.Nature 393.440(1998)

［2］Newman M E J.The structure and function of complex networks［J］.SIAM Review，2003，45(2):167 ～256.

［3］M.E.J.Newman and D.J.Watts，Phys.Lett.A263，341(1999)

［4］S.N.Dorogovtsev and J.F.F.Mendes.cond－mat/0005050

［5］R.Albert，H.Jeong，andA－L.Barabasi，Physica A 272(1999)173 ～187

［6］R.Albert，H.Jeong，and A－L.Barabasi，Nature 401，130(1999)

［7］Wenchen He，et al.Time evolution of the degree distribution of model A of random attachment growing networks.Physica A.384(2007):663～666

［8］Reka Albert and Albert－ Laszlo Barabasi.Phys.Rev.Lett.85(2000)5234 ～5237