一类确定性小世界网络模型及特性分析 A Kind of Deterministic Small-World Networks Model and Analysis of Their Characteristics

doi:10.12677/CSA.2014.42006

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Computer Science and Application 计算机科学与应用, 2014, 4, 27-31

http://dx.doi.org/10.12677/csa.2014.42006 Published Online February 2014 (http://www.hanspub.org/journal/csa.html)

A Kind of Deterministic Small-World Networks Model and

Analysis of Their Characteristics

Ke Zhang1, Haixing Zhao2, Faxu Li2, Yuzhi Xiao2, 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. 27th, 2013; revised: Jan. 26th, 2014; accepted: Feb. 5th, 2014

stricted use, distribution, and reproduction in any medium, provided the origin al work is properly cited. In accordance of th e Creative Commons At-

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 deterministic u niform recursive tree.

It shows a logarithmic scaling w ith the size of the network; however its cluste ring coefficient is zero. In 2012, Lu et al.

in Physica A 391, based on the deterministic uniform recursive tree and by a simple rule, added some edges and got a

deterministic small-world network model. In this paper, we study the law of the structure on the basis of the model con-

structed in P hysica A 391 from a new viewpoint, naturally, we generalize and change the rule to get an iterated class of

sma ll-world networks, and then give the analytic solutions to several important topological characteristics of these

models proposed. The obtained vigorous results show that these networks have power-law cumulative degree distribu-

tion, high clustering coefficient and small diameter.

Keywords: Small-World Network; The Deterministic Uniform Recursive Tree; Topological Characteristics

一类确定性小世界网络模型及特性分析

张科1，赵海兴 2，李发旭 2，肖玉芝 2，李峰2

1青海师范大学数学系，西宁

2青海师范大学计算机学院，西宁

Email: hbsanli@163.com, h.x.zhao@163.com

收稿日期：2013 年12 月27 日；修回日期：2014年1月26 日；录用日期：2014年2月5日

摘要：确定性小世界网络是复杂网络中的一个重要的研究分支。2008年，章忠志等人(Eur.Phys.J.B 63)在复杂

网络的视角下对确定性均匀递归树作了详尽地分析，得到了其拓扑属性。尽管确定性均匀递归树的平均路径长

度表现出了网络大小的对数规模，但是它的聚类系数为零。2012 年，陆哲明等人(Physica A 391)通过在确定性均

匀递归树的基础上以一个简单的规则添加一些边得到一个确定性小世界网络模型。本文在新的视角下对文献

Physica A 391中的模型的构造规律进行了探究，并自然地对其进行了推广。构造了一类确定性小世界网络模型，

然后运用分析的方法给出了所构造网络模型的几个重要拓扑属性，包括呈幂律分布的累积度分布、高的聚类系

数和小的直径。

关键词：小世界网络；确定性均匀递归树；拓扑属性

OPEN ACCESS 27

一类确定性小世界网络模型及特性分析

1. 引言

很多现实生活网络都体现出了小世界效应，诸如

交通网络、电力网络、选举网络和社会关系网络。小

世界网络有两个典型的属性：其一，较短的平均路径

长度。平均路径长度与网络顶点个数的对数成正比例

关系。其二，较高的聚类系数。高的聚类系数使网络

包含一些块。

在过去十几年里，为了描述现实生活网络的小世

界性，很多网络模型被构造出来了。首创的小世界网

络模型是 WS 模型，它在 1998 年Watts 和Strogatz[1]

的论文中被引入。WS 模型是通过对规则网络以一个

确定的概率重联边来构造的。

确定性网络的主要优势在于它们的拓扑属性可

以用分析的方法进行计算。在 2000 年，Comellas[2]

等人用图论的方法构造了第一个确定性的小世界网

络。紧接着一些静态的和用迭代的方法构造的动态的

[3-5]确定性小世界网络模型被构造出来。根据分形图形

[6,7]、典型的数列[8]等也构造出了很多确定性小世界网

络模型。当然，对小世界网络的研究所考虑的因素在

趋于多样化[9]，并且小世界性的研究领域在进一步扩

展[10]。

均匀递归树[11]是ER 随机网络之外的一个重要的

随机模型。均匀递归树可以按如下的简单的方式生成：

在每一次迭代中，一个新的顶点随机选择连接到一个

已经存在的顶点上。确定性小世界网络是复杂网络中

的一个重要的研究分支[12]。在 2002 年，确定视角下

的均匀递归树[13]被构造出来去模仿现实生活网络，该

网络的顶点数与时间步成指数关系。在 2008 年，章

忠志等人[14]在复杂网络的视角下对确定性均匀递归

树作了详尽的分析。他们得出确定性均匀递归树的拓

扑属性，如度分布、平均路径长度、介数分布、度相

关性，并且计算出了 Laplacian 矩阵的特征值和特征

向量。确定性均匀递归树的平均路径长度表现出网络

大小的对数规模，然而，它的聚类系数为零。在2012

年，陆哲明等人[15]根据确定性均匀递归树得到一个小

世界网络，并给出了所构造模型的几个拓扑属性。在

2013 年，作为所提出的计算生成树数目的新方法的算

例，赵海兴等人[16]计算出了文献[15]中的模型的生成树

数目。

本文对文献[15]中的模型作了推广：(1) 从图形结

构着眼看待文献[15]中的模型，由网络模型的平面图形，

描述网络模型的生成规律；(2) 设定参数，构造了一

类确定性小世界网络模型，然后运用分析的方法给出

了所构造网络模型的几个重要的拓扑属性。本文可以

为相关领域的研究人员提供借鉴，即从不同角度去审

视网络模型更容易探索出其潜在的生成规律；本文也

给出了在已经存在的经典模型的基础上，通过调整生

成规则而获得满足需要网络特性的网络模型的一个

生动的实例。

2. 模型及拓扑属性

2.1. 模型

确定性均匀递归树的生成过程非常简单[13]，如图

1 (迭代的前四步)所示。

陆哲明等人[15]在其基础上调整添加边数的规则，

使网络具有较大的聚类系数，从而具有小世界性。图

2(a)的曲线部分为新添加的边。实际上，整个过程是

将树变成二树。这个巧妙的简单的迭代生成过程也可

以换一个视角描述为：初始状态

0t=

时，为连接两个

顶点的一条边；

1t=

时，在初始边的两侧条添加一个

顶点，并均与初始的两个顶点相连；

2t=

时，在

1t=

步新添加的边所围成的四边形中，任选一组对边，在

此两边的两侧各添加一个顶点，并均与相应的边上的

两个顶点相连；第

步的网络模型是在第

1t−

步的基

础上生成的，在第

1t−

步新添加的边所围成的四边形

中，任选一组对边按

1t=

时的规则添加新的边，直到

网络达到所需要的规模。如图2(b) (迭代的前四步)所

示。比较图 2(a)和图 2(b)，可以看出，后者将前者平

面化了，能清楚地看到此网络模型具有自相似性。可

见，结合图论的思想，从图形的结构上审视它，更容

易发现网络模型的生成规律。

本文的模型是将陆哲明等人构造的模型一般化，

即每一个迭代步，在选定的边的每一侧各添加

( )

2mm≥

个顶点，并分别与该边的两端点相连。图

3所示是

2m=

的前三个迭代步的情形。

反过来看，若边的一侧只添加一个顶点并使其与

边的一个端点相连，即为确定形均匀递归树的生成方

式。

1m=

即为文献[15]所构建的模型。文献[14,15]对

这两种情形下模型的相关特性进行了深入的研究。

用

表示时间步

时网络的顶点数，用

表示时

OPEN ACCESS

一类确定性小世界网络模型及特性分析

Figure 1. The first four iterations of the growth process of deterministic uniform recursive tree

图1. 确定性均匀递归树的生成过程的前 4步

(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步

Figure 3. The first thr ee iterations of the growth process of the network proposed

图3. 本文所构造的网络的生成过程的前3步

间步

时网络的边数。用

( )

表示第

个时间步所增

加的顶点数。注意到增加一个顶点的同时，会增加两

条边，因此第

个时间步增加的边数

( )( )

nt nt=

。

根据该网络的结构，当

1t≥

时，可以得到。

( )()

nt m=

(1)

( )

2 22

+−

=−

(2)

( )()

nt m=

(3)

( )

222 1

+−−

=−

(4)

因此，对于大的

，平均度

约为 4。

2.2. 度分布

度分布是一个重要的描绘网络特性的拓扑属性。

用与顶点

关联的边的条数来定义顶点

的度。用

( )

表示第

个时间步时顶点

的度，

1, 2,3,,

iN=

。

OPEN ACCESS 29

一类确定性小世界网络模型及特性分析

度为

的顶点的概率定义为度分布

( )

。根据算法及初始条件

( )( )

0 01kk= =

，可以得到：

( )

( )( )( )

, 12

2 22222

,11, 2,3,,

1 2121

itl ll

mm i

kt mmmm m

i lt

mm m

−+ +

−− ≤≤

−



=−+− +−

+≤≤ =

−− −



(5)

因此，该网络的度分布是一个离散的序列：在时

间步

( )

1tt≥

时，度为

2,22,222, ,1

km mmm

−−

= +++−



的顶

点数分别为

( )( )()

2,2,2, ,2

tt t

mm m

−−



。

从而

( )

()( )

( )

2 12,1

2 22

22 121

2 22

mmkm

Pk mmm

−+

−

−

=−

+−

=−−−

=

−

+−



(6)

由(6)式分析、计算，可以得到累计度分布

()()

()

ln 2

2 22

cum

mk km

mk k

−

−+ −







=−

−+



≈



(7)

可见，当

较大时，累计度分布近似为

ln 2

mk k

−

−+







，服从幂律分布。

2.3. 聚类系数

聚类系数是一个与度相关的衡量网络的顶点的

聚集程度的量。聚类系数可以通过对所有顶点的聚类

系数取平均值得到。

表示顶点

的聚类系数，

表

示顶点

的度，

表示与顶点

邻接的顶点间存在的

边数。

刻画的是与顶点

邻接的顶点间存在边的可

能性，其表达式为

()

iii

Ckk

=−

。对于本网络模型，

用

( )

表示时间步

顶点

的聚类系数。当

0t=

时，

容易知道

( )( )

0 00CC= =

。由图 3，可知，当

0t>

时，

若顶点

是刚添加到网络中去的，则有

2, 1

kL= =

，

从而，

Lk= −

。进而，可知顶点间每连接一条边，

和

都要增加 1，因此可以得到它们之间的满足所

有顶点的关系，即

Lk= −

，由此，可以得到：

( )()

( )( )

()

()( )( )

ii ii

Ct kt

kt ktkt kt

−





===

−−





(8)

由(8)式聚类–度相关性可以简单地描述为

( )

Ck k

−

∝

。根据这个结果，可以知道聚类系数和度之

间呈负相关的关系，这就意味着，度越大的顶点，其聚

类系数越小。

由

( )

与

和

之间的关系，(8)式可以改写为：

( )

( )( )( )

, 12

2 22222

1,1,1, 2,3,,

21 21

ill

Ct mmm m

mi lt

−+

− ≤≤

−−



=+− +−

−

+≤≤ =

−−

−



(9)

由此，对于

0t>

时，网络的平均聚类系数

计算如下：

( )( )( )

( )( )

11 1

1 211

21 1

2 22

Ntl

it ttl

CtC tm

Nmmm

+ +−+

= =

−



−−

== ⋅+



−− −

+−



∑∑

(1 0)

由(10)式可知，对于

2m=

，当

趋于无穷大时，

单调递增趋近于 0.8201；对于

3m=

，当

趋于无穷

大时，

单调递增趋近于 0.8699；对于

4m=

，当

趋

于无穷大时，

单调递增趋近于 0.8975。同时

也趋

于无穷时，

单调递增趋近于 1。可见所构造的网络

的聚类系数较大。由文献[15]可知，对于

，当

趋

OPEN ACCESS

一类确定性小世界网络模型及特性分析

于无穷大时，

ln2 0.6931C= ≈

。所以，通过控制参数

，可以构造平均聚类系数介于

ln 2

和1之间的一类

网络模型。

2.4. 直径

众所周知，网络直径的定义是任意两个顶点间最

小距离的最大值，它是反映网络最大传递延迟的属性。

小的直径是小世界网络的一个重要属性。用

( )

表示

本网络模型的时间步

时的直径。由图3可知

()( )

0 1,12DD= =

。对于每一个

1t>

的时间步，很容

易知道，直径由当前时间步新添加的顶点中某对顶点

之间的距离决定。根据网络模型的构造，

2m≥

时与

1m=

时的模型具有相同的直径。因此，网络的直径满

足下面的式子：

( )( )

21 22

1 ln2

mNm

Dt tm

− −+

=+=

(11)

易知，直径按网络顶点的对数规模增长。

3. 总结

本文在确定性均匀递归树的基础上构造了一类

确定性小世界网络。通过改变迭代规则，把聚类系数

从0提高到趋近于 1，从而使这些网络模型满足小世

界网络模型的特性。用分析的方法计算出了所构造网

络的度分布、聚类系数、聚类–度相关性及直径。因

为所构造的一类确定性小世界模型是按照简单的规

则在初始的树形结构上添加一些边和顶点得到的，这

就使得研究这类网络模型有更加简单有效的方法，文

献[16]就是一个充分的证明。由此，本文可以为相关

领域的研究人员提供借鉴，即从不同角度去审视网络

模型更容易探索出其潜在的生成规律；本文也给出了

在已经存在的经典模型的基础上，通过调整生成规则

而获得满足需要网络属性的网络模型的一个生动的

实例。

基金项目

科技部 973 专项(No. 2010CB334708)、国家自然

基金项目(No. 61 164005)、教育部长江学者与创新团队

支持计划(No. IRT1068)、青海省自然基金项目(No.

2012-Z-943)。

参考文献 (References)

[1] Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of

“small-world” networks. Nature, 393, 440-442.

[2] Comellas, F., Ozon, J. and Peters, J.G. (2000) Deterministic

small-world communication networks. Information Processing

Letters, 76, 83-90.

[3] Zhang, Z.Z., Rong, L.L. and Guo, C.H. (2006) A deterministic

small-world network created by edge iterations. Physica A: Sta-

tistical Mechanics and Its Applications, 363, 567-572.

[4] Zhang, Z., Zhou, S., Shen, Z. and Guan, J. (2007) From regular

to growing small-world networks. Physica A: Statistical Me-

chanics and Its Applications, 385, 765-772.

[5] Hu, G.N., Xiao, Y.Z., Jia, H.S. and Zhao, H.X. (2013) A new

class of the planar networks with high clustering and high en-

tropy. Abstract and Applied A nalysi s, 2013, Article ID: 795682.

[6] Zhang, Z.Z., et al. (2010) Mapping Koch curves into scale-free

small-world networks. Journal of Physics A: Mathematical and

Theoretical, 43, Ar ticle I D: 395101.

[7] Zhang, Z.Z., et al. (2007) Maximal planar scale-free Sierpinski

networks with small-world effect and power law strength-degree

correlation. Europhysics Letters, 79, Article ID: 38007.

[8] Zhang, Z. and Comellas, F. (2011) Farey graphs as models for

complex networks. Theoretical Computer Science, 412, 865-875.

[9] Zhang, Y.C., Zhang, Z.Z., Zhou, S.G. and Guan, J.H. (2010)

Deterministic weighted scale-free small-world networks. Physi-

ca A: Statistical Mechanics and Its Applications, 389, 3316-

3324.

[10] GovorčIn, J., Knor, M. and Škrekovski, R. (2013) Line graph

operation and small worlds. Information Processing Letters, 113,

196-200.

[11] Smythe, R.T. and Mahmoud, H. (1995) A survey of recursive

trees. Theory of Probability and Mathematical Statistics, 51, 1-

27.

[12] 章忠志, 周水庚, 方锦清 (2008) 复杂网络确定性模型研究

的最新进展.

复杂系统与复杂性科学

, 4, 29-46.

[13] Jung, S., Kim, S. and Kahng, B. (2002) A geometric fractal

growth model scale free networks. Physical Review E, 65, Ar-

ticle ID: 056101.

[14] Zhang, Z.Z., Zhou, S.G., Qi, Y. and Guan, J.H. (2008) Topolo-

gies and Laplacian spectra of a deterministic uniform recursive

tree. The European Physical Journal B, 63, 507-513.

[15] Lu, Z.M. and Guo, S.Z. (2012) A sma ll-world network derived

from the deterministic unifo rm recursive tree. Physica A: Statis-

tical Mechanics and Its Applications, 391, 87-92.

[16] Xiao, Y.Z. and Zhao , H.X. (2013) New method for co unting the

number of spanning trees in a two-tree network. Physica A: Sta-

tistical Mechanics and Its Applications, 392, 4576-4583.

OPEN ACCESS 31