设为首页 加入收藏 期刊导航 网站地图
  • 首页
  • 期刊
    • 数学与物理
    • 地球与环境
    • 信息通讯
    • 经济与管理
    • 生命科学
    • 工程技术
    • 医药卫生
    • 人文社科
    • 化学与材料
  • 会议
  • 合作
  • 新闻
  • 我们
  • 招聘
  • 千人智库
  • 我要投搞
  • 办刊

期刊菜单

  • ●领域
  • ●编委
  • ●投稿须知
  • ●最新文章
  • ●检索
  • ●投稿

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
Advances in Applied Mathematics 应用数学进展, 2014, 3, 22-28
http://dx.doi.org/10.12677/aam.2014.31004 Published Online February 2014 (http://www.hanspub.org/journal/aam.html)
An Approximation Algorithm for Average Path Length
in A Small-World Network Model
Ke Zhang1, Haixing Zhao2, Feng Li2
1Department of Mathematics, Qinghai Normal University, Xining
2School of Computer Science, Qinghai Normal University, Xining
Email: hbsanli@163.com, h.x.zhao@163.com
Received: Dec. 29th, 2013; revised: Jan. 30th, 2014; accepted: Feb. 7th, 2014
Copyright © 2014 Ke Zhang et al. This is an open access article distributed under the Creative Commons Attribution License, which
permits unrestricted use, dis tribution, and rep roduction in any medium, pro vided the o riginal work is pro perly cited. In a ccordance of the
Creative Commons Attribution License all Copyrights © 2 014 are reserved for Hans and the owner of the intellectual property Ke Zhang
et al. All Copyright © 2014 are guarded by law and by Hans as a guardian.
Abstract: Deterministic small-world network is an important branch of study of complex networks. In 2008,
Zhang et al. in Eur.Phys.J.B 63 have offered detailed topological characteristics of the deterministic uniform
recursive tree from the viewpoint of complex network. They derived topological characteristics of the deter-
ministic uniform recursiv e tree. It shows a logarithmic scaling with the size of the network, however, its clus-
tering coefficient is zero. In 2012, Lu, et al. in Physica A 391, based on the deterministic uniform recursive
tree, by a simple rule to add some edges, got a deterministic small-world network model. In this paper, using
an approximation algorithm based on the network construction, we show explicitly the average path length of
the model constructed in Physica A 391.
Keywords: Graph Theory; Small-World Network; Average Path Length
一种确定性小世界网络模型平均路径长度的逼近方法
张 科1,赵海兴 2,李 峰2
1青海师范大学数学系,西宁
2青海师范大学计算机学院,西宁
Email: hbsanli@163.com, h.x.zhao@163.com
收稿日期:2013 年12 月29 日;修回日期:2014年1月30 日;录用日期:2014年2月7日
摘 要:确定性小世界网络是复杂网络中的一个重要的研究分支。2008 年,章忠志等人(Eur.Phys.J.B 63)
在复杂网络的视角下对确定性均匀递归树作了详尽地分析,得到了其拓扑属性。尽管确定性均匀递归
树的平均路径长度表现出了网络大小的对数规模,但是它的聚类系数为零。2012 年,陆哲明等人(Physica
A 391)通过在确定性均匀递归树的基础上以一个简单的规则添加一些边得到一个确定性小世界网络模
型。本文根据网络模型的结构用分析的方法给出了文献Physica A 391中的模型的平均路径长度的逼近
方法。
关键词:图论;平均路径长度;小世界网络
1. 引言
很多现实生活网络都体现出了小世界效应[1-4],诸如交通网络、电力网络、选举网络和社会关系网络。小世
界网络有两个典型的属性:其一,较短的平均路径长度。平均路径长度与网络顶点个数的对数成正比例关系。
OPEN ACCESS
22
张科 等 | 一种确定性小世界网络模型平均路径长度的逼近方法
其二,较高的聚类系数。高的聚类系数使网络包含一些块。
除度分布[5,6]、中心性[7]等以外,平均路径长度是一个基本的刻画复杂网络的度量。同时,网络的平均路径
长度对其不同的动力学特性具有很大的影响,如疾病传播[8]、随机游走[9]、同步[10]等。因为平均路径长度对于网
络来说意义重大,所以说对它的研究引起了广泛的重视[11-15]。
本文的研究所基于的网络模型源于均匀递归树[16]。均匀递归树是 ER随机网络之外的一个重要的随机模型。
均匀递归树可以按如下的简单的方式生成:在每一次迭代中,一个新的顶点随机选择连接到一个已经存在的顶
点上。确定性小世界网络是复杂网络中的一个重要的研究分支[17]。在2002 年,确定视角下的均匀递归树[18]被构
造出来去模仿现实生活网络,该网络的顶点数与时间步成指数关系。在2008 年,章忠志等人[19]在复杂网络的视
角下对确定性均匀递归树作了详尽的分析。他们得出确定性均匀递归树的拓扑特性,如度分布、平均路径长度、
介数分布、度相关性,并且计算出了 Laplacian 矩阵的特征值和特征向量。确定性均匀递归树的平均路径长度表
现出网络大小的对数规模,然而,它的聚类系数为零。在 2012 年,陆哲明等人[20]根据确定性均匀递归树得到一
个小世界网络。通过在每一个迭代步以一种简单的规则添加一些边,从而可以获得一个高的聚类系数。此模型
的构造是在树的结构的基础上得到二树的典型例子,使被构造的模型具有了小世界性。
本文用逼近的方法,计算了文献[20]中所构造的模型的平均路径长度。在研究复杂网络的结构属性时,有些
属性难以精确计算,而用数据模拟又具有局限性,本文提供了一个有用的参考。
2. 模型及特性分析
确定性均匀递归树的生成过程非常简单[18]。用
t
U
表示经过
t
步迭代后的确定性均匀递归树,并用
t
V
和
t
E
分
别表示其顶点数和边数。其中 ,
0,1,2, ,1tT= −
,
T
为迭代的总步数。如图 1(迭代的前四步)所示。确定性均匀
递归树的生成过程可以描述如下:
第0步:初始状态。当
0t=
时,
0
U
为连接两个顶点的一条边,此时,
00
2, 1VE= =
。
第1步:
1t
U+
在
t
U
的基础上生成。对于
t
U
的每一个顶点都对应添加一个新的顶点并分别用一条边相连。从
而有,
12
tt
VV
+=
,
1
t tt
E EV
+= +
。
第2步:若
1tT<−
,令
1tt= +
转第 1步。否则,迭代停止。
上述的迭代进行
1
T−
次后,可以得到一个顶点数
1
2
t
t
V
+
=
、边数
1
21
t
t
E
+
= −
的确定性树。
章忠志等人对确定性均匀递归树的几个重要的拓扑属性进行了研究[19],其主要结果为:1) 累积度分布
( )
1
2
k
cum
UP k
−+
=
,关于
k
呈单调递减的指数 关系 ,即确定 性均 匀递 归树 是一 个指数分 布的 网络 ,其 度分布与随
机性均匀递归树的度分布类似。2) 平均路径长路
() ()
11
2 12 1
tt
t
Ud t
++
=+−
,当
t→∞
时,
lnln 21
tt
Ud tV→= −
。
由此,其平均路径长度与网络顶点个数的对数成正比例关系,具有与均匀递归树和 WS 网络模型类似的小世界
现象。3) 介数分布表现出底为2的指数函数关系,具有与均匀递归树相同的规模。4) 度相关性
( )
nn
Uk k
正相关
于
k
的线性函数,这表明确定性均匀递归树是对称的。尽管他们没有给出确定性均匀递归树的聚类系数,但很
容易知道其聚类系数为0,因为均匀递归树中不存在三角形。因此确定性均匀递归树不是小世界网络。
陆哲明等人[20]在确定性均匀递归树生成规律的基础上调整添加边数的规则,使网络具有较大的聚类系数,
从而具有小世界性。用
( )
Gt
表示经过
t
步迭代后的小世界网络,并用
t
N
和
t
B
分别表示其顶点数和边数。其中,
0,1,2, ,1tT= −
,
T
为迭代的总步数。随着时间步
t
的递增给每一个顶点标注一个自然数,则其生成过程
Figure 1. The first four iterations of the growth process of deterministic uniform recursive tree
图1. 确定性均匀递归树的生成过程的前 4步
OPEN ACCESS 23
张科 等 | 一种确定性小世界网络模型平均路径长度的逼近方法
可以描述如下:
第0步:初始状态。当
0t=
时,
( )
0G
为连接两个顶点的一条边,这两个顶点分别标记为“1”和“2”,
此时,
00
2, 1NB= =
。
第1步:
( )
1Gt+
在
( )
Gt
的基础上生成。这一步包含以下两个分步。
第1.1 步:生成确定性均匀递归树。
( )
Gt
中标号为“
p
”的顶点和新增加的标号为“
t
Np+
”的顶点用一
条边相连。其中,
1, 2,,t
pN=
。
第1.2 步:添加边。
( )
1Gt+
中新添加的标号为“
t
Np+
”的顶点和
( )
Gt
中标号为“
1
t
Np−+
”的顶点用
一条边相连。其中,
1, 2,,t
pN=
。
显然,经过这两个分步之后,有
12
tt
NN
+=
,
1
2
ttt
BBN
+
= +
。
第2步:若
1tT<−
,令
1tt= +
转第 1步。否则,迭代停止。
上述的迭代进行
1T−
次后,就可以得到一个高的聚类系数的确定性网络。如图 2(a)(迭代的前四步)所示。
上述的迭代进行
1T−
次后,由顶点数和边数之间的关系
12
tt
NN
+=
、
1
2
ttt
BBN
+
= +
及初始条件
0
2N=
、
01B=
,
可以计算得出
1
2
t
t
N
+
=
、
2
23
t
t
B
+
= −
。
陆哲明等人对所构建的确定性小世界网络的几个重要的拓扑属性进行了研究[20],其主要结果为:1) 度分布
( )
2
2
k
Pk
−
∝
,关于
k
呈指数关系,即构造的确定性小世界网络,与包括 WS 网络模型在内的很多小世界网络
的度分布的表现一致。2) 聚类系数
()
1
1
22
21
tn
t
n
Ct tn
−+ −
=
= +
+
∑
,当
t→∞
时,
( )
ln 2Ct→
。由此,其聚类系数较高,
符合小世界现象对聚类系数的要求。3) 直径
( )
ln
1ln 2
t
V
Dt t=+=
,可知网络的直径与网络顶点个数的对数成正比
例关系,而网络的直径不会大于其平均路径长度,所以网络的平均路径长度增长得更缓慢。表现出小世界现象。
从所造网络的上述拓扑属性可以断言其为一个确定性小世界网络,因为其具有高的聚类系数和小的平均路
径长度,符合小世界网络对于其拓扑属性的要求。
实际上,整个过程是将树变成二树。图 2(a)中的曲线部分为新添加的边。这个巧妙的简单的迭代生成过程
也可以换一个视角描述为:初始状态
0t=
时,为连接两个顶点的一条边;
1
t=
时,在初始边的两侧条添加一个
顶点,并均与初始的两个顶点相连;
2
t=
时,在
1t=
步新添加的边所围成的四边形中,任选一组对边,在此两
边的两侧各添加一个顶点,并均与相应的边上的两个顶点相连,第 t步的网络模型是在第
1t−
步的基础上生成的:
在第
1t−
步新添加的边所围成的四边形中,任选一组对边按
1t=
时的规则添加新的边,直到网络达到所需要的
规模。如图2(b)(迭代的前四步)所示。比较图2(a)和图 2(b),可以看出,后者将前者平面化了,能清楚地看到此
(a)
(b)
Figure 2. (a) The first four iterations of the growth process of the network proposed by Lu et al.; (b) The first four iterations of the growth
process of the network proposed by Lu et al. on a new viewpoint
图2. (a) 陆哲明等人所构造的小世界网络的生成过程的前 4步;(b) 在新的视角下陆哲明等人所构造的小世界网络的生成过程的前4步
OPEN ACCESS
24
张科 等 | 一种确定性小世界网络模型平均路径长度的逼近方法
网络模型具有自相似性。可见,从图形的结构上审视它,更容易发现网络模型的生成规律。便于用分析的方法
计算该确定性小世界网络的平均路径长度。
3. 平均路径长度的逼近方法
平均路径长度是一个重要的刻画网络特性的参数。平均路径长度定义为网络中任意两点间最短路径长度的
平均值。在现实生活网络中,人们常常能注意到“小世界”现象,即短的平均路径长度。对于大多数网络,很
难给出一个精确的计 算平 均路 径长 度的 方法 。很 明显 ,该 网络 模型的平均路 径长度与 生成 网络的迭代步 数
t
有
关。
根据图 3,下面给出了一种逼近的方法来计算该网络模型的平均路径长度。
用
,ij
d
表示
( )
Gt
中的顶点
i
与顶点
j
之间的最短路径长度,用
( )
Vt
表示
( )
Gt
中的所有顶点组成的集合,由
定义
( )
Gt
的平均路径长度可以表示如下:
( )( )
( )
( )
,
,
1
12
t ij
ijVt
dd
Vt Vt
∈
=−
∑
(1)
其中
( )
1
2
t
t
Vt N
+
= =
(2)
根据
( )
Gt
的标准的迭代结构来获得
t
d
的值。图
( )
1Gt+
是在图
( )
Gt
的两个拷贝(记为
( )
1
Gt
、
( )
2
Gt
)之间
连三条边得到的。如图3所示。
Figure 3. Schematic illustration of the recursive construction of the network proposed by Lu et al. on a new viewpoint
图3. 在新的视角下陆哲明等人所构造的小世界网络的循环示意图
两个拷贝
( )
1
Gt
和
( )
2
Gt
相互之间通过
( )
1
Gt
中的顶点集
{ }
,XY
和
( )
2
Gt
中的顶点集
{ }
,ZO
连接。
( )
1Gt+
中
其余的点称之为内点。
用
1,2
t
∆
表示从
( )
1
Gt
的内点到
( )
2
Gt
的内点的所有最短路径长度之和。用
t
∆
表示
( )
1
Gt
的点到顶点集
{ }
,OZ
及
( )
2
Gt
的点到顶点集
{ }
,XY
的所有路径长度之和。
( )
1Gt+
中任意两点之间的路径长度之和(即维纳指数)记为
( )
( )
,
,1
1
ij
ijVt
Wt d
∈+
+=∑
,则有
( )( )
1,2
12 tt
Wt Wt+=+∆ +∆
(3)
将
( )
1
Gt
的内点分为两类
( )
X
Pt
,
( )
Y
Pt
,则
( )
X
Pt
中的内点经过点
X
路径长度最小,
( )
Y
Pt
中的内点经过点
Y
路径长度最小。同样地我们把
( )
2
Gt
中的点也分成了两部分
( )
Z
Pt
和
( )
O
Pt
有
( )( )( )( )( )
221
2
t
XYZO
Gt
PtPtPtPt−
===== −
(4)
OPEN ACCESS 25
张科 等 | 一种确定性小世界网络模型平均路径长度的逼近方法
且易知
( )( )( )( )
,,, ,
X YZO
Xi YiZiOi
iPtiP tiPtiPt
dddd
∈ ∈∈∈
= ==
∑∑∑∑
(5)
令
( )
( )
,
X
Xi
iP t
d St
∈
=
∑
,根据网络的结构
()()()
1
12 22
t
St StSt−
=−+− +
(6)
由(6)式可得
( )()
1
12
t
StStt −
+ −=⋅
(7 )
可以进一步得到
() {}() {}() {}() {}
( )
( )
( )
( )
2 211
,,,,
\,\,\ ,\ ,
,, ,,
5
625
OZ
t XiYiZiOi
iVtZOiVtZOiV tXYiV tXY
XOOiX ZZi
iP tiP t
d ddd
dd dd
∈ ∈∈∈
∈∈
∆=+ + ++
= ++ ++
∑∑∑∑
∑∑
(8)
而
()
( )
()
( )
( )
,,
21221 1
Z
tt
XZ Zi
iP t
Std dSt
∈
−+≤+≤− +−
∑
(9)
由(8)式和(9)式,可以得到
( )
( )
( )
( )
8218510218 1
tt
t
St St−+ +≤∆≤ −+ −
(10)
另一方面,为了计算
1,2
t
∆
,有
( )( )( )( )()( )( )( )
1,2,,,,
,,, ,
XO YZYOXz
tuv uv uv uv
uPtvPt uPtvPt uPtvPt uPtvPt
dddd
∈ ∈∈∈∈∈∈∈
∆=+ + +
∑∑∑∑
(11)
由网络结构的自相似性,有
( )( )( )( )()( )
,,,
,,,
XO YZYo
uvuvuv
uPtvP tuPtvP tuP tvPt
ddd
∈ ∈∈∈∈∈
= =
∑∑∑
(12)
根据(11)和(12)式,易知
( )( )()( )
1,2,,
,,
3
XO XZ
tuv uv
uP tvPtuP tvPt
dd
∈∈ ∈∈
∆= +
∑∑
(13)
而
( )()( )( )
( )
( )( )( )( )()( )
( )( )
( )
( )
( )
( )
( )( )
( )
( )
( )
( )
,,, ,,,,,
,
2
,
2
21212121 21
22121
XOXOXOX OOO
X
uvuvuXXO OvuXXOOv
uPtvPtuPtvP tuPtvP tuPtvP tvPtvP t
t tttt
uX
uP t
tt
dddddd dd
dSt StSt
St
∈∈∈∈∈∈∈ ∈∈∈
∈

==++ =++




=−+−+=−+−+−

= −+−
∑∑∑∑∑∑ ∑∑∑
∑
(14)
类似地,有
( )
( )
( )
( )( )
( )
( )
( )( )
22
,
,
22121221221 21
XZ
t tttt
uv
uPtvP t
Std St
∈∈
−+−≤≤−+−−−
∑
(15)
因此,可以得到
()
( )
( )( )
( )
( )()
22
1,2
821421821521 21
ttt tt
t
St St−+−≤∆≤−+−−−
(16)
OPEN ACCESS
26
张科 等 | 一种确定性小世界网络模型平均路径长度的逼近方法
根据初始条件
( )
17S=
,有
当
( )
( )
82 185
t
tSt∆=− ++
,
( )
( )
( )
2
1,2
821 421
tt
t
St∆= −+−
时,由(3)式有
()( )( )
32
1 22421
tt
WtWt St
+
+ =++⋅+
(17)
计算得,
( )
22212
22212
14
222 1,
399
7 11
222 1,
399
t tt
t tt
tt
Wt tt
+ ++
+ ++
⋅−⋅+⋅−


=
⋅+⋅−⋅−


为奇数
为偶数
(18)
当
()
()
10 2183
t
tSt
∆=− ++
,
( )
( )
()()
2
1,2
82152121
t tt
t
St∆=−+− −−
时,由(3)式有
()( )( )
32
122522 1
t tt
WtWt St
+
+ =++⋅−−
(19)
计算得,
( )
22 211
22 21
55
2222 1,
318 18
37 115
2222 1,
31818
tt tt
tt tt
ttt
Wt ttt
++ −
+−
⋅+⋅+⋅−⋅ +


=
⋅+⋅−⋅−⋅+


为奇数
为偶数
(20)
根据前文的定义
( )
( )
,
,ij
ijVt
Wtd
∈
=
∑
,由(1)式、(2)式、(18)式及(20)式,当
t→∞
时,
( )
22
ln 1
33
tt
dt V≈= −
(21)
因此,对于大的网络,平均路径长度的增长与网络的大小规模的增长呈对数关系。并且,经过简单的计算
21
33
tt
t
−
=
,可知对于大的
t
,按规则在均匀递归树的基础上填加一些边得到的确定性小世界网络的平均路径长
度减小了三分之一。
4. 总结
现实生活中的很多网络都体现了小世界性。本文运用分析方法中的逼近方法计算出了一个经典的确定性小
世界网络模型的平均路径长度,基于网络模型的结构,计算结果相对精确。发现当网络的规模趋近于无穷时,
其平均路径长度和顶点数的关系为:
~ ln
tt
dV
。本文提供的逼近方法可以作为一些复杂的网络属性的计算的参
考。
项目基金
科技部 973 专项(No. 2010CB334708)、国家自然基金项目(No. 61164005)、教育部长江学者与创新团队支持
计划(No. IRT1068)、青海省自然基金项目(No. 2012-Z-943)。
参考文献 (References)
[1] Newman, M.E.J. (2000) Models of the small world. Journal of Statistical Physics, 101, 819-941.
[2] Albert, R. and Barabási, A.-L. (2002) Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47-97.
[3] Newman, M.E.J. (2003) The structure and function of complex networks. SIAM Review, 45, 167-256.
[4] Yu, S., Huang, D., Singer, W. and Nikolic, D. (2008) A small world of neuronal synchrony. Cerebral Cortex, 18, 2891-2901.
[5] Chung, F. and Lu, L. (2002) The average distances in random graphs with given expected degrees. Proceedings of the National Academy of
OPEN ACCESS 27
张科 等 | 一种确定性小世界网络模型平均路径长度的逼近方法
Sciences of USA, 99, 15879-15882.
[6] Cohen, R. and Havlin, S. (2003) Scale-free networks are ultrasmall. Physical Review Letters, 90, Article ID: 058701.
[7] Dorogovtsev, S.N., Mendes, J.F.F. and Oliv eira , J.G. (2006) Degree-depe n den t in tervertex separation in co mplex n etworks. Physical Review E,
73, Article ID: 056122.
[8] Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of “small-world” networks. Nature, 393, 440-442.
[9] Condamin, S., Benichou, O., Tejedor, V., Voituriez, R. and Klafter, J. (2007) First-passage times in complex scale-invariant media. Nature,
450, 77-80.
[10] Nishikawa, T., Motter, A.E., Lai, Y.-C. and Hoppensteadt, F.C. (2003) He terogeneity in oscillator netwo rks: Are smaller worlds easier to syn-
chronize? Physical Review Letters, 91, Article ID: 014101.
[11] Dorogovtsev, S.N., Mendes, J.F.F. and Samukhin, A.N. (2003) Metric structure of random networks. Nuclear Physics, 653, 307-338.
[12] Lovejoy, W.S. and Loch, C.H. (2003) Mini mal and maximal characteristi c path lengths in c onnected sociomatrices. Social Netw orks, 25, 333-
347.
[13] Fronczak, A., Fronczak, P. and Holyst, J.A. (2004) Average path length in random networks. Physical Review E, 70, Article ID: 056110.
[14] Holyst, J.A., Sienkiewicz, J., Fronczak, A., Fronczak, P. and Suchecki, K. (2005) Universal scaling of distances in co mplex netwo rks. Physical
Review E, 72, Article ID: 026108.
[15] Fekete, A.,Vattay, G. and Posfai, M. (2009) Shortest path discovery of complex networks. Physical Review E, 79, Article ID: 065101.
[16] Smythe, R.T. and Mahmoud, H. (1995) A survey of recursive trees. Theorya Imovirnosty ta Matemika Statystika, 51, 1-27.
[17] 章忠志, 周水庚, 方锦清 (2008) 复杂网络确定性模型研究的最新进展. 复杂系统与复杂性科学, 4, 29-46.
[18] Jung, S., Kim, S. and Kahng, B. (2002) A geometric fractal growth model scale free networks. Physical Review E, 65, Article ID: 056101.
[19] Zhang, Z.Z., Zhou, S.G., Qi, Y. and Guan, J.H. (2008) Topologies and Laplacian spectra of a deterministic uniform recursive tree. European
Physical Journal B, 63, 507-513.
[20] Lu, Z.M. and Guo, S.Z. (2012) A small-world network derived from the deterministic uniform recursive tree. Physica A, 391, 87-92.
OPEN ACCESS
28

版权所有:汉斯出版社 (Hans Publishers) Copyright © 2012 Hans Publishers Inc. All rights reserved.