基于两种不同择优概率下的无标度网络模型

马 飞,姚 兵

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

基于两种不同择优概率下的无标度网络模型

马 飞,姚 兵

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

基于标准的无标度网络模型,建立了一般的网络动力系统所符合的偏微分方程,不仅给出无标度网络的一个拓扑性质,而且讨论了其中每个功能函数的实际意义.接着本文扩展了BA网络模型增长的“度优先连接机制”原则,从更一般的情形出发,建立了一类具有2种不同优先连接概率共存的网络模型,通过理论分析,得知该模型具有无标度特性.最后对无标度网络的幂律指数γ的取值范围与多种择优概率并存现象之间的相互关系做了探索,并依据节点在整个网络中的“贡献度”,提出了一类优先连接概率.

无标度网络模型; 动态演化; 偏微分方程; 度优先连接; 特殊图形优先连接

0 引言及术语

无数的网络(有形或无形)充满了人们的世界,如细胞中的新陈代谢网、大脑中的神经网、生态系统中的食物链网、社会关系网络、科研合作网络、经贸互惠网络、互联网、万维网以及电力网和交通运输网等等.诸如此类的复杂网络与我们的生活息息相关.面对这些复杂多变的网络,研究者将其抽象转化成模型—–图.起初研究者们运用图论的方法对其进行研究,但是图论中研究的图形大多都是规则的、单一的,而真实网络的结构不仅很复杂,而且构成网络的节点数目也很庞大.这样一来,复杂网络的研究对传统经典图论的发展提出了新的要求.20世纪50年代,Erd¨os和R´enyi[1]基于经典图论的研究,提出了随机网络模型(ER模型),该模型能够很好地体现网络的随机性,但是节点的度(与节点相连接的边的数目)之间相差不大,几乎相等,度分布服从Poisson分布,其图像是一条钟型曲线.显然,真实网络中节点的度并不都是相等的.为了解释蕴含在网络中的规律,1998年,Watts和Strogatz[2]提出了小世界网络模型,该模型在继承了随机网络模型的随机性后,产生了新的网络拓扑性质:属于该网络模型中的初始节点的度相对要大一些,它的度分布呈现出指数衰减.随后,1999年,基于万维网拓扑结构的大量研究,Barab´asi和Albert[3]发现钟型曲线消失了,出现了一条递减的曲线,为了刻画这一现象,他们首次提出了无标度网络模型(BA模型),该模型满足幂率分布公式

其中γ叫做无标度指数,它的取值范围是2＜γ＜3.在他们首创性的研究工作之后,复杂网络的研究得到了众多研究者的重视.结合大量理论研究和实际经验数据,人们发现:生活中大量的网络都具有无标度特性(scale-free property),即服从幂率分布(1);然而,部分真实网络的幂律指数γ的取值范围却超出了2到3,落在1到4之间[4].为此,关于无标度网络幂律指数γ的取值范围仍是一个值得重视的研究课题.

近年来,国内外的研究人员对BA模型进行了不同层次的推广和拓展,得到的成果颇多[5-9],如随机性模型:BA无标度网络的双向演化模型[10]、基于组增长的小世界Scale-free网络模型[11]、一类无标度合作网络的演化模型[12]、一种动态的无标度网络模型[13]等等;确定性模型:Apollonian网络模型[14]、Farey图网络模型[15]、Sierpinski网络模型[16]等等.在这些研究中,人们共同发现网络中存在“先到先得,富者越富,适者更富”的现象.针对这种现象,总结得出具有无标度特性的网络演化(增长)必须满足2条性质:均匀增长和择优连接.特别是择优连接方式对一个演化的网络是否具有无标度特性起到决定性的作用,已证实运用线性择优连接方式将会得到无标度网络,非线性的择优连接方式将会影响到网络的度分布,使其不再服从幂率分布[17].但是,在这些模型中,均匀增长方式都是在单一的择优概率假设条件下进行的,因此,关于复杂网络如何进行均匀增长的讨论仍在探索.本文将设立更一般意义上的复杂网络动态演化所符合的动力方程,并依此建立了一类择优概率混存的动态随机无标度网络模型.

1 动态微分方程

在Barab´asi和Albert[3]首次提出了一类无标度网络模型之后,复杂网络的研究迎来了重大的突破[18-21].不论是通过理论研究,还是运用计算机进行仿真模拟,研究人员针对网络的动态演化(讨论随着时间的延续,网络中不断地有新节点进入、新边的加入、旧节点的删除以及旧边的删除)的描述与刻画都存在着及其相似之处(所有的演化都是在单一的择优假设条件下发生的).这样一来,随着时间的延续,网络的规模会越来越庞大(节点数目与边数目巨大、结构复杂).任何事物都不可能无休止地增长下去,对网络而言,在历经一段时间的增长后也会趋于稳态或衰退.结合实际意义与理论分析,本文引入5个功能函数,试图对复杂系统与复杂网络的动态演化方式进行探索式刻画.

假如,一个最初具有m0个节点的网络N(0)的动态演化是连续的,t时刻后,对网络N(t)中一个度为ki(t)的节点,依据事件的独立性可以得到一个动态方程

设方程 (2)的解为 ki(t)= θ(t,ti,α1,α2,···,αr),其中参数 αi(i=1,2,···,r)与时间变量t和ti无关.进一步,得

方 程 式 (3)中 的 参 数 βi(i = 1,2,···,r)与 时 间 变 量 t和 ki(t)均 无 关,表示ki(t)的反函数.解得网络N(t)中顶点度数为k的概率

注 在获得方程(2)的解的过程中,有两种情形.情形1:如果方程(2)右边部分式子中出现的ki与t含有不同指数指标,在时间t趋于无穷大时,可做近似舍弃该项来获得近似解;情形2:如果方程(2)右边部分式子中含有形式的表达式,在时间t充分大的前提下,可做近似舍弃该项来获得近似解.从纯数学角度通过下面的例子仅解释情形1,设有微分方程

本文以文献[5-7]为背景,分析了其中的无标度网络模型,发现它们中节点的增长方式均采用了单一的度优先连接概率,但现实中网络的增长模式并非单一,而是在多种优先概率共存的条件下进行的.鉴于这样的实际背景意义,建立了一种幂律指数γ的取值范围在1到3之间的两种优先概率混合共存的无标度网络模型,并对该类复杂网络的特性进行了探究.

2 具有2种优先概率共存的网络模型

任何一个网络都不是独立存在的,在进行演化时,不仅要受到自身因素的影响,而且还要受到来自外界因素的干扰(促进或阻碍).就网络增长的过程而言,目前的研究都采用了比较单一的度优先连接增长机制,这样使得研究具有一定的局限性.试想一下,现实生活中的网络在进行节点加入时,不同的时刻,加入网络的节点数不仅是变化的,而且每一个节点进入网络后采取的连边运算也并不是按一个确定的准则进行的.例如:在一个合作网络中,有人喜欢与其中互相之间存在密切联系的一圈人进行合作;有些人更偏向于与整个合作网络中的强手(度数较大)合作(只要有可能);在不清楚该合作网络潜在运行规则的情况下,甚至有些人随机地与其中的某些人进行合作.为了刻画这样一类简单合作网络的动态演化过程,本文建立了一类两种优先概率(度优先连接概率和特殊图形优先连接概率)混合共存下的网络模型,并设立了与之对应的动力学方程.

文中模型N(t)的构造过程如下:初始网络N(0)是具有m(≥3)个节点、条边的完全图Km.从t≥1时刻起,执行以下操作.

(1)增长:t时刻有a个节点加入网络N(t−1)中.

(2)优先连边运算:这a个新节点由三类不同的节点组成,第i类节点共有pia(0≤pi≤1,i=1,2,3)个.属于第一类中的每一个节点随机地从网络N(t−1)中选择一个完全图Km,并与该完全图Km中的m个节点进行连边运算,表示一次进行了m+1人次的合作.易知每一时刻后,网络中会增加p1a个完全图和p1am个完全图Km.属于第二类中的每一个节点采用优先连接概率Πi=与已存在于网络模型N(t−1)中的s(≤m−2)个不同节点进行连边运算.属于第三类中的每一个节点随机均匀地与网络模型N(t−1)中的n(＜m−1)个不同节点进行连边运算.这样的演化可以进行数次,直到获得期望的模型为止.

当第一类新节点进入网络时,总会与一个随机选择的完全图Km的m节点进行连边,可以看出,节点的度数越大,它就越容易出现在更多的完全图Km中,从而也就是说,度数越大的节点越容易获得新的连接.通过分析可知,这样的择优连接方式与第二类节点的度优先连接概率不同,在这里称之为特殊图形(Km)择优连接概率.在前面两类节点采用择优连接的条件下,第三类节点却采用了随机均匀概率.本文的合作网络模型就是基于上述这三种不同概率的前提下建立起来的.经历这样的t次演化后,网络模型N(t)具有nv(t)=m+at个节点和ev(t)=个Km完全图,度为ki的节点所属的Km完全图的数目为显然当参数p1=p3=0时,该网络模型就退化成了BA模型.

对第一类节点,假设ki是连续实变量,根据模型的演化机理,在动态方程(2)的5个功能函数中,加点函数

其余的功能函数g∗(t)=h∗(t)=z∗(t)=φ(t)=0.则有如下的动态方程.

上述方程(5)可写为

其中

当t→∞时,在Q(t)与R(t)中分别取

则有

在初始条件ki(ti)=m下,方程(6)的解为

在模型的构造过程中,任意m个第二或第三类节点无论什么时刻都不可能同属一个完全图Km,因此,在设立与第二或第三类节点度数变化相应的动力方程时,方程(5)中的Q(t)将不包含这一项.当t→∞时,在上式Q(t)中可以取和R(t)中取l2=p3n,在初始条件ki=s和ki=n下,分别获得方程(6)的解为

网络中任选一个第一类节点度数为ki(t)且不超过k的概率可以写成如下形式.

假设插入“新”节点到网络的时间t服从均匀分布,即P(ti)便可得到节点的度分布函数

当t充分大时,

网络度分布服从幂率分布,且幂率指数γ1=1/h1+1,它的取值范围为1＜γ1＜3.若在该模型中节点的优先连接概率仅仅采用单一的特殊图形Km择优连接概率,则p2=0,这时幂率指数的取值范围为2＜γ1＜3.可以看出,同时采用两种不同的优先连接概率在一定程度上会使无标度网络的幂率指数的取值范围发生变化.

类似地,网络中任选一个第二或第三类节点度数为k的概率可以写成如下形式.

网络度分布服从幂率分布,且幂率指数γ2=1/h2+1,幂率指数的取值范围为γ2＞3.若在该模型中节点的优先连接概率仅仅采用单一的度优先连接概率,则p1=0,这时幂率指数γ2=的取值范围为γ2＞3.可以看出,同时采用两种不同的连接概率(度优先连接概率和随机均匀概率)也会使无标度网络的幂率指数的取值范围在一定程度上发生变化.

对网络中每一类节点的动力方程(2)进行求和计算得

上式中|V(ki,t)|表示t时刻度数为ki的节点数目.当t充分大时,(10)式的左端趋近于常数a[p1m+p2s+p3n].对于网络安全的研究而言,人们在获得P(k)的同时也希望得到网络中hub节点的个数,这样便可以通过控制hub节点来达到对网络实施安全维护.这里采用节点的度累积分布公式

结合积分性质和连续化手段,得

本文模型中,

通过以上分析,可以看出该模型具有无标度特性,是一个无标度网络.

3 结论以及问题

本文首先根据前人对复杂网络与复杂系统研究的成果,设立了更加一般的动力学方程,抽象地解析了该方程在初始条件下的通解.其次,从现实复杂网络中确实混存多种择优概率的背景下,建立了一种涉及了两类不同择优连接概率:度优先连接概率和特殊图形(Km)择优连接概率的网络模型,并证明了它具有无标度特性.为了说明两类择优概率的特点与作用,在这里选取度优先连接概率为特殊图形(Km)择优连接概率为进行求和运算后可得

这就说明:通过不同角度设立的优连接概率仅仅反映的是网络中普遍存在“先到先得,适者更富,赢者通吃”的现象.为了今后的研究,有以下问题.

问题1(贡献与亏损) 一般情况下,对于一个演化的网络,其中的每一个节点都对网络本身的运行起到“贡献或亏损”作用,基于节点对网络“贡献或亏损”程度的突出与否,提出一个假设:节点择优连接服从

式中的参数αi表示节点i对整个网络的贡献度,其中αi＞0表示在网络中是贡献节点(αi=1表示理想贡献节点,αi＞1表示超负荷贡献节点,0＜αi＜1表示现实贡献节点),αi＜0表示在网络中是亏损节点.目前的研究都是在不考虑节点的贡献度不同的情形下探讨的,若每个节点的贡献度αi是一个在0到1之间的常数,那么

上式中θji=假设时间t是连续变量,可以得到

在连续的条件下,采用平均场方法[3]便可以计算得到P(k)≈k−γ,其中幂率指数γ=1+θji.最特殊的情形便是节点的贡献度与节点的度毫无关系,即所有的节点在网络中都被“一视同仁”(任意节点的贡献度参数αi=1),此时有这便是经典的BA模型.

问题2(精确化幂率指数的取值范围) 运用不同的方法、技术、技巧,从不同的角度出发,发现大量的现实网络几乎都具有无标度特性,度数为k的节点在网络中出现的概率满足(1)式,但是,幂律指数γ取值集中于1到4.通过对上述模型分析,γ＞1时,网络总体呈现出增长状态;γ∼1时,网络总体呈现出“边静态”(随时间推移,节点数不断增加,但网络的边数却没有发生变化);γ＜1时,网络总体呈现出衰退.这或许就可以解释为什么当前人们通过研究,发现不少网络服从P(k)∼k−γ,且γ∈(1,4)这一现象,这不同于先前所关注的增长网络,仍可以作为今后探索的一个主题.

[1]ERH˝OS P,R´ENYI A.On random graphs[J].Publ Math,1959(6):290-297.

[2] WATTS D J,STROGATZ S H.Collective dynamics of small-world networks[J].Nature,1998,393:440-442.

[3]BARAB´ASI A L,ALBERT R,JEONG H.Mean-field theory for scale-free random networks[J].Physica A,1999,272:173-187.

[4] 刘浩广,蔡绍洪,张玉强.无标度网络模型研究进展[J].大学物理,2008(4):43-47.

[5] YAO B,YAO M,CHEN X E,et al.Research on edge-growing models related with scale-free small-world networks[J].Applied Mechanics and Materials,2014:2444-2448.

[6] SONG C M,KOREN T,WANG P,et al.Modelling the scaling properties of human mobility[J].Nature Physics,2010,1760:1-6.

[7] YAN G,TSEKENIS G,BARZEL B,et al.Spectrum of controlling and observing complex networks[J].Nature Physics,2015,3422:779-786.

[8] CHEN Q H,SHI D H.The modeling of scale-free networks[J].Physica A,2004,335:240-248.

[9] 梁宏振,姚洪兴,张学兵.一类无标度网络的特征分析[J].复杂系统与复杂性科学,2005(3):67-71.

[10] 辜芳琴,樊锁海.BA无标度网络的双向演化模型[J].暨南大学学报(自然科学版),2013(5):475-478.

[11] 吴艾,刘心松,刘丹,等.基于组增长的小世界Scale-free网络模型[J].计算机科学,2005,32(7):23-25.

[12] 张忠志,荣莉莉,周涛.一类无标度合作网络的演化模型[J].系统工程理论与实践,2005(11):55-60.

[13] 贾秀丽,蔡绍洪,张芙蓉.一种动态的无标度网络模型[J].四川师范大学学报(自然科学版),2009(6):839-842.

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

[15] ZANG Z Z,WU B,LIN Y.Counting spanning trees in a small-world Farey graph[J].Physica A,2012,391:3342-3349.

[16] ZANG Z Z,ZHOU S G,SU Z,et al.Random Sierpinski network with scale-free small-world and modular structure[J].The European Physical Journal B,2008,65(1):141-147.

[17]KRAPIVSKY P L,REDNER S,LEYVRAZ F.Connectivity of growing random network[J].Phys Rev Lett,2000,85:4629-4632.

[18] DEL GENIO C I,GROSS T,BASSLER K E.All scale-free networks are sparse[J].Phys Rev Lett,2011,178701:1-4.

[19] 王林,戴冠中.复杂网络的度分布研究[J].西北工业大学学报(自然科学版),2006(4):405-409.

[20] YAO B,LIU X,ZHANG W J,et al.Applying graph theory to the internet of things[C]//International Conference on High Perfermance Computing and Communication.2013.

[21] YAO B,YANG C,YAO M,et al.Graphs as models of scale-free networks[J].Applied Mechanics and Materials,2013,380-384:2720-2723.

(责任编辑:林 磊)

One scale-free network model based on two different preferential attachment probabilities

MA Fei, YAO Bing
(College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)

Based on the classic scale-free network model,we set up the partial differential equation satisfied a more general network dynamic system,and then we not only find another important topological property of scale-free network,but also discuss the real background meaning of every function.Meanwhile,we extend the BA-network-model growth principle,degree-preferential attachment mechanism. Starting from a more general situation,we establish a network model containing degree-preferential attachment probability and special-graph-preferential attachment probability.By analysis,this model is scale-free. Finally,we distinguish the connect between the scope of the power law parameter γ of scale-free network and the phenomena all kinds of preferential attachment probabilities co-existing.According to the contribution level from the vertex to the whole network,we come up with a preferential attachment probability.

scale-free network model; dynamical evolution;partial differential equation; degree preferential attachment; graph preferential attachment

O157.5

A

10.3969/j.issn.1000-5641.2017.06.004

1000-5641(2017)06-0042-08

2016-06-01

国家自然科学基金(61163054,61363060,61662066)

马 飞,男,硕士研究生,研究方向为图的标号和复杂网络.E-mail:mafei123987@163.com.

姚 兵,男,教授,研究方向为图着色与标号以及复杂网络.E-mail:yybb918@163.com.