,書式設定,書式設定,第 2,第 3,第 4,第 5,“,复杂网络论坛圈”博文大赛参赛博文,为什么网络会加速增长,?,第六届全国网络科学论坛 暨 第二届全国混沌应用研讨会,网络加速增长现象的经济学解释及仿真分析,1,报告提纲,一、网络加速增长现象,二、加速增长现象的经济学解释,三、网络加速演化模型及其仿真分析,四、结论与问题,2,一、网络加速增长现象,表现：,平均度随时间增加,（,边比节点的增速更快,）,加速增长是实际网络演化中的普遍现象,已有数十类网络被证实具有加速增长特性（因特网、万维网、引文网、语言网、科学家合作网络、生物代谢网络、蛋白质作用网络,）,科学家合作网,Barabsi,et al,.2002,因特网（,AS,层）,Faloutsos,et al,.1999,3,网络加速增长的两种方式,该图引自：,Sen,，,PRE,2004,方式,a,：边只在新老节点之间产生，适用于描述引文网络等少数网络（但目前被研究得更多）；,方式,b,：边可以在老节点内部产生，符合大多数实际网络的增长情况（目前尚未受到广泛关注）。,4,从边增加的视角理解网络加速增长,在网络“年轻”时，边更多地是以连接新节点的形式增加；,随着网络年龄的增长，越来越多的边会在老节点之间产生；,相对于边增加的速度，网络节点增加的速度越来越慢，网络呈现,边加速增长,的趋势。,5,二、网络加速增长现象的经济学解释,为什么一些实际的网络会有前述这种“初期节点增速快，后期边增速快”的规律？本文尝试用经济学中的,效用理论,来解释这一现象产生的原因。,微观经济学中的,效用,是用来描述消费品对消费者需求满足程度的一个概念。根据效用最大化原理和随机效用原理，效用越大的消费品被选择的概率也越大。,边际效用递减理论,：在消费者连续消费某种消费品时，随着所消费的该消费品的数量增加，其总效用虽然相应增加，但消费品的边际效用（每消费一次所带来的效用增量）有递减趋势。,6,边际效用递减导致网络加速增长,如果我们认为网络是自组织的，那么可以,把网络自身理解为一个消费者，把网络演化过程中边的增加理解为一次消费行为，而把边连接新节点还是老节点理解为两种消费品,。,在网络增加边的一次“消费行为”中，是选择连接新节点还是选择连接老节点，取决于这二者中的哪个会带给网络自身更大的“效用”。,而根据边际效用递减理论，随着网络中边数量的增加，连接新节点带给网络的效用会越来越小。因此，网络会越来越不倾向于连接新节点，而是倾向于在老节点之间建立连接，网络将呈现出边加速增长的趋势。,7,对一些实际网络的解释,公交网络：,图片来源：,科学家合作网络：,图片来源：,8,三、网络加速演化模型及其仿真分析,根据以上讨论，本文构造了一个网络演化模型来模拟网络加速增长的过程。它按照如下规则生成一个网络：,Step 1,：,初始化，令演化时刻,t,=0,，创建一个包含,n,个节点,(,n,2),的完全图；,Step 2,：,生成一个包含,n,个节点,(,n,2),的完全图，以正比于,(t),的概率选择,m,个新节点,(0,(t),1,，且,(t),是一个减函数,),，其余,n,-,m,个节点从现有网络中按正比于节点度,k,的概率选择（即择优连接）；,Step 3,：,令,t,=,t,+1,，返回,Step 2,，直到,t,=,T,（给定的最大步长）。,9,对模型的一些说明,(1),以完全图作为网络增长的基本单元,更符合合作网络演化的实际情况,如果,n,=2,，则每步演化加入的是一条边，可以描述一些非合作网络的加速增长。,(2),边际效用递减律体现在函数,(t),中,0,(t),1,，且,(t),是一个减函数,可根据网络增长特性取线性、指数、幂函数等多种形式,(3),模型的两个特例,(t),为常数时，退化为,RDP,模型,(,Ramasco,et al,，,2004,),n,=2,且,(t),=0.5,时，退化为,BA,模型,(Barabsi,et al,1999),10,模型度分布的初步解析,如果,(t),为定值,（与时间无关），则可用率方程解析得到网络的节点度分布为：,上式为漂移幂律分布（,Chang,et al,，,2007,），度分布指数（随,的减小）从,-,到,-2,变化。,如果,(t),随时间递减,，尚无法求得解析解，后面将给出度分布的仿真分析结果。,11,模型的仿真分析,设定,n,=10,，每演化,100,步，对网络的主要拓扑性质进行一次统计，结果见下表：,演化步长,节点数量,边数量,节点平均度,平均距离,平均群聚系数,100,810,4534,11.20,3.85,0.90,200,1510,9029,11.96,3.78,0.87,300,2110,13516,12.81,3.66,0.84,400,2610,18006,13.80,3.51,0.82,500,3010,22488,14.94,3.38,0.78,600,3310,26958,16.29,3.26,0.75,特征：,平均度,随时间,增加，平均距离,随时间,下降，平均群聚系数,随时间,下降,*无论,(t),取线性、指数还是幂函数形式，均会出现这一规律,12,与科学家合作网实证数据的对比,平均度随时间增加,平均距离随时间下降,平均群聚系数随时间下降,数学领域（,M,）和神经科学领域（,NS,）科学家合作网从,1991,年到,1998,年的主要拓扑特征变化情况（,图引自：,Barabsi,et al,.,Physica A,2002,）,13,与城市公交网络实证数据的对比,年份,线路数量,站点数量,边数量,线路平均站点数量,平均度,平均距离,平均群聚系数,1996,44,500,6472,18.23,25.89,2.24,0.86,2000,70,696,12326,20.39,35.42,2.30,0.80,2004,86,899,18341,21.24,40.80,2.35,0.78,2008,104,1033,22027,21.96,42.65,2.38,0.77,城市公交线网拓扑特征统计（石家庄市,1996-2008,，每,4,年统计一次）,石家庄市公交网络的平均度随演化时间增加而增加，平均群聚系数下降，与模型仿真结果相吻合。,但网络的平均距离却也随演化时间增加，这可能是由于公交网络演化,受空间距离约束,，缺乏长程连接所导致的结果。,14,模型与实际网络度分布的对比,仿真模型的节点累积度分布,石家庄市公交网络站点累积度分布,数学领域（,M,）和神经科学领域（,NS,）科学家合作网度分布（,Barabsi,et al,.,2002,）,15,四、结论与问题,结论：,用经济学中的效用理论解释网络加速增长现象产生的可能原因，认为若自组织网络增加节点的边际效用是递减的，则网络自身对效用最大化的追求会驱动网络加速增长。揭示了导致网络加速增长的一种可能机制。,构建了一种加速增长的合作网络演化模型，仿真分析结果表明，该模型能够再现实际网络加速增长的现象，一些关键拓扑性质与实证数据能够较好地吻合。,16,需进一步研究的问题,(1),对模型网络的拓扑性质进行精确解析,由于,(t),随时间递减，这一点并不容易做到,(2),边际效用递减现象能否自发出现？,本文模型的边际效用递减规则是人为设定的，能否构造一种模型，使网络自发出现边际效用递减现象？,(3),各种实际网络增长速度的评价与调控,增长速度如何影响网络效率,如何优化或引导网络保持合理增速,17,谢 谢！请各位老师、同学批评指导！,闫小勇,石家庄铁道大学 交通运输学院,第六届全国网络科学论坛 暨 第二届全国混沌应用研讨会,18,