一类作为网络模型的可平面无标度图

马 飞，姚 兵

(西北师范大学 数学与统计学院, 甘肃 兰州 730070 )

一类作为网络模型的可平面无标度图

马 飞，姚 兵*

(西北师范大学 数学与统计学院, 甘肃 兰州 730070 )

无标度特性普遍存在于大量的实际网络和人造网络中．为了更好地研究这类无标度网络模型的拓扑性质和内在动力学，大量的模型被建立，如随机网络模型和确定性网络模型．鉴于以往确定性模型中的无标度指数都是唯一不变的常数，定义了一类具有广义自相似性的增长网络模型，分析了它的一些拓扑性质:平均度、聚集系数、直径、度分布、最多叶子生成树．得出该模型具有无标度特性和小世界效应，并且可以通过调整相应的参数来获得丰富的无标度指数．

无标度图；网络模型；小世界效应

0 引 言

为了认识自然、改造自然，学者们在面对大到天体，小到人类及其他动物界，甚至微生物界之间存在的种种联系时，形象生动地提出了复杂网络这一概念，随之产生了大量的复杂网络模型．Watts等[1]提出了小世界网络模型，Barabsi等[2]首次提出了无标度网络模型．在此之后的十几年，学术界对复杂网络的研究热潮不衰反增，吸引了众多学者的不断涌入，使得复杂网络的研究不论纵向深入还是横向拓展都取得了丰硕的成果．现今复杂网络研究涵盖了诸多学科领域，如物理、数学、计算机科学、化学、生物学、经济学等，在研究各领域中不同的研究对象时，产生了大量的网络模型，如物联网、地震网、食物链网、电力网、细胞新陈代谢网、神经信号传送网、股市等[3-10]．

对真实网络进行了海量的研究之后，学者们不约而同地阐释了众多网络具有的拓扑共性：(1)小的直径和平均距离；(2)高的聚集系数；(3)服从幂率分布(无标度性)；(4)自相似性；(5)层次结构．从而为复杂网络的进一步研究指明了方向．为了认识、理解复杂网络，学者们通过循环迭代的方法构造新的随机模型，讨论它的拓扑性质．

1 模型的迭代及其拓扑性质

1.1 模型的迭代

在本文的网络模型M(t)中，用顶点刻画研究中的每个实体对象，顶点间的连边表示实体对象间的相互联系，L(t)表示M(t)的最多叶子生成树的叶子数，文中未定义的术语和符号均采用图论中标准的术语和符号[12]．模型M(t)可以通过迭代的方法得到，如下：

(1)当t=0时，模型M(0)由一条活动边和与之关联的两个顶点组成．

(2)当t>0时，模型M(t)可以通过对模型M(t-1) 中的活动边实施平行加边运算获得．这里的活动边是指模型M(t-1)在t-1时刻新产生的边，每条活动边至少含有1个二度顶点，不妨称在t-1时刻之前的边为休眠边．

(1)

(2)

通过上述迭代构造出的模型M(t)是可平面的，如果加边参数d同时满足d=m+n，m表示一条活动边上方加边的条数，n表示一条活动边下方加边的条数，这样便可以得到一族可平面的广义自相似网络模型．随着时间的推移，这一族网络模型将是相当复杂的[8]．图1为模型M(t)在t=0，1，2，d=m+n=2(m=n=1)的拓扑结构.

图1 模型M(t)拓扑结构Fig.1 Model M(t) topological structures

1.2 模型的拓扑性质

1.2.1 平均度 网络的平均度〈k〉为边个数的2倍与顶点个数之比，即

(3)

随着时间的推移，模型M(t)的顶点和边数目越来越大，不难发现，当t→∞时，整个模型M(t)的平均度趋于一固定常数3，即

(4)

位于活动边xy上下不同位置的新顶点和新边会影响以后进入网络的新顶点和新边的位置，从而导致模型M(t)的拓扑结构的复杂性(图2)．

图2 模型M(t)在t=0,1,d=m+n=6的拓扑结构Fig.2 Model M(t) topological structures at t=0, 1, d=m+n=6

1.2.3 直径 直径作为研究复杂网络的另一个重要参数，往往对网络的随机游走研究起到一定的作用，然而很多复杂网络的直径并不是轻松获得的，一般来说，获得一些网络直径的精确解是相当困难的．模型M(t)基于对称迭代构造，便于获得直径的精确解．分析得知，模型M(t)中任意两顶点间的距离中只有在t时刻新加入的对称顶点间的距离最长，根据直径的定义D(t)=max{dij|i，j∈V(t)}，其中dij表示顶点i与顶点j的距离，进一步分析得知，M(t)中的直径D(t)可以表示为：顶点i先走到与之相邻的在t时刻休眠边的顶点it，顶点j先走到与之相邻的在t时刻休眠边的顶点jt，直径D(t)=1+ditjt+1．根据模型的对称性知，顶点it与顶点jt的距离ditjt是模型M(t-1) 的直径，故D(t)=D(t-1)+2，t≥2，因D(1)=1，M(t)的直径为

D(t)=3+2(t-1)

(5)

1.2.4 度分布 度分布是一个刻画复杂网络是否具有无标度性质的拓扑参数．对模型M(t)中顶点的度构成的度谱分析可知，这是一些离散的数据，为了获得模型M(t)的度分布，采取累积度分布的计算方法[4]：

(6)

其中V(t，k′)表示在t时刻M(t)中度为k′的顶点集合，下面做详细的论证．在t=0时，M(0)有两个度为1的顶点，之后的每一次迭代中新加入的顶点的度都是2．为了简化叙述，采用符号k(i，t)，kg(i，t)，kp(i，t)表示在t≥ti时与顶点i相关联的边的数目、活动边的数目、休眠边的数目．显然有k(i，t)=kg(i，t)+kp(i，t)．鉴于模型M(t)的构造，可以得到：当i=0时，模型M(t)中的两个属于M(0)的初始顶点的度为

(7)

在ti≥1时，

kp(i，t+1)=kg(i，t)+kp(i，t)，kg(i，ti)=2

kg(i，t+1)=2dkg(i，t)，kp(i，ti)=0

(8)

由式(8)计算得

(9)

(10)

在ti时刻，考察度为k的顶点的度分布，由式(10)可得

(11)

联立式(6)、(7)、(11)，得到网络模型M(t)的累积度分布为

(12)

当t很大时，由式(11)知，式(12)可简化为

当k≫1时，将获得如下表达式：

(14)

(15)

2 结 语

理论分析表明，本文建立的模型具有无标度特性和小世界效应．在最近的生物网络研究中，有学者发现了一类特殊的现象：网络中每个顶点的邻居顶点集中任何顶点彼此之间没有边相连(聚集系数〈c〉=0)[8,13]，而且这样的网络具有较强的鲁棒性．在实际生活中，可以提高对蓄意攻击的预防性，加强网络的安全性．本文的模型正好吻合这一现象，有力推动对该类特殊网络的进一步研究，这也提醒人们在今后的研究中更加关注此类复杂网络．复杂网络的研究正在如火如荼地进行着，研究成果层出不穷，研究方法也在日趋完善，日后将关注网络研究中的熵与随机游走等问题[8,10]．

[1]WATTS D J, STROGATZ S H. Collective dynamics of ′small-world′ networks [J]. Nature, 1998, 393(6684):440-442.

[3]WATTS D J. Small Worlds:The Dynamics of Networks between Order and Randomness [M]. New Jersey:Princeton University Press, 1999.

[4]ZHANG Zhongzhi, ZHOU Shuigeng, FANG Lujun,etal. Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation [J]. EPL, 2007, 79(3):417-429.

[5]YAO Bing, YAO Ming, CHEN Xiangen,etal. Research on edge-growing models related with scale-free small-world networks [J]. Applied Mechanics and Materials, 2014(513-517):2444-2448.

[6]ZHANG Z Z, WU B, COMELLAS F. The number of spanning trees in Apollonian networks [J]. Discrete Applied Mathematics, 2014, 169:206-213.

[7]TEUFL E, WAGNER S. Resistance scaling and the number of spanning trees in self-similar lattices [J]. Journal of Statistical Physics, 2011, 142(4):879-897.

[8]MIRALLES A, COMELLAS F, CHEN L C,etal. Planar unclustered scale-free graphs as models for technological and biological networks [J]. Physica A:Statistical Mechanics and its Applications, 2010, 389(9):1955-1964.

[9]SONG C M, KOREN T, WANG P,etal. Modelling the scaling properties of human mobility [J]. Nature Physics, 2010, 6(10):818-823.

[10]YAN G, TSEKENIS G, BARZEL B,etal. Spectrum of controlling and observing complex networks [J]. Nature Physics, 2015, 11(9):779-786.

[11]DEL GENIO C I, GROSS T, BASSLER K E. All scale-free networks are sparse [J]. Physical Review Letters, 2011, 107(17):178701.

[12]BONDY J A, MURTY U S R. Graph Theory with Applications [M]. London:The Macmillan Press Ltd., 1976.

[13]COMELLAS F, ZHANG Zhongzhi, CHEN Lichao. Self-similar non-clustered planar graphs as models for complex networks[J]. Journal of Physics A Mathematical & Theoretical, 2009, 42(4):461-471.

A planar scale-free graphs as network models

MA Fei,YAO Bing*

(College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China )

The scale-free feature is popular in amounts of real-life and artificial complex networks. In order to study the topological properties and intrinsic dynamics of this kind of scale-free network model, lots of models are presented, such as random network models and deterministic ones. Considering that the scale-free exponent is an unique constant in those previous deterministic models, a generalized self-similarity growing network model is proposed. Its topological properties, including average degree, clustering coefficient, diameter, degree distribution, maximum-leaf-spanning-tree are analyzed. It shows that this model has scale-free characteristics and small-world effects, and the scale-free exponent can be enriched by adjusting corresponding parameters.

scale-free graph; network model; small-world effect

1000-8608(2017)04-0436-05

2016-09-28；

2017-03-13．

国家自然科学基金资助项目(61163054，61662066，61363060).

马 飞(1992-)，男，硕士生，E-mail：mafei123987@163.com；姚 兵*(1956-)，男，教授，E-mail：yybb918@163.com.

O157.5

A

10.7511/dllgxb201704016