闫小勇-网络加速增长的经济学解释与仿真分析-yanxy.pptx

“复杂网络论坛圈”博文大赛参赛博文为什么网络会加速增长? 闫小勇yanxy@sjzri.edu.cn石家庄铁道大学 交通运输学院第六届全国网络科学论坛 暨 第二届全国混沌应用研讨会——网络加速增长现象的经济学解释及仿真分析 报告提纲一、网络加速增长现象二、加速增长现象的经济学解释三、网络加速演化模型及其仿真分析四、结论与问题 一、网络加速增长现象表现：平均度随时间增加（边比节点的增速更快）加速增长是实际网络演化中的普遍现象已有数十类网络被证实具有加速增长特性（因特网、万维网、引文网、语言网、科学家合作网络、生物代谢网络、蛋白质作用网络……）科学家合作网 Barabási et al. 2002因特网（AS层） Faloutsos et al. 1999 网络加速增长的两种方式该图引自： Sen，PRE , 2004方式a：边只在新老节点之间产生，适用于描述引文网络等少数网络（但目前被研究得更多）；方式b：边可以在老节点内部产生，符合大多数实际网络的增长情况（目前尚未受到广泛关注） 。 从边增加的视角理解网络加速增长在网络“年轻”时，边更多地是以连接新节点的形式增加；随着网络年龄的增长，越来越多的边会在老节点之间产生；相对于边增加的速度，网络节点增加的速度越来越慢，网络呈现边加速增长的趋势。 二、网络加速增长现象的经济学解释为什么一些实际的网络会有前述这种“初期节点增速快，后期边增速快”的规律？本文尝试用经济学中的效用理论来解释这一现象产生的原因。微观经济学中的效用是用来描述消费品对消费者需求满足程度的一个概念。根据效用最大化原理和随机效用原理，效用越大的消费品被选择的概率也越大。边际效用递减理论：在消费者连续消费某种消费品时，随着所消费的该消费品的数量增加，其总效用虽然相应增加，但消费品的边际效用（每消费一次所带来的效用增量）有递减趋势。 边际效用递减导致网络加速增长如果我们认为网络是自组织的，那么可以把网络自身理解为一个消费者，把网络演化过程中边的增加理解为一次消费行为，而把边连接新节点还是老节点理解为两种消费品。在网络增加边的一次“消费行为”中，是选择连接新节点还是选择连接老节点，取决于这二者中的哪个会带给网络自身更大的“效用”。而根据边际效用递减理论，随着网络中边数量的增加，连接新节点带给网络的效用会越来越小。因此，网络会越来越不倾向于连接新节点，而是倾向于在老节点之间建立连接，网络将呈现出边加速增长的趋势。 对一些实际网络的解释 三、网络加速演化模型及其仿真分析根据以上讨论，本文构造了一个网络演化模型来模拟网络加速增长的过程。它按照如下规则生成一个网络：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 （给定的最大步长）。 对模型的一些说明(1) 以完全图作为网络增长的基本单元更符合合作网络演化的实际情况如果n=2 ，则每步演化加入的是一条边，可以描述一些非合作网络的加速增长。(2) 边际效用递减律体现在函数θ(t) 中0< θ(t) ≤1 ，且θ(t)是一个减函数可根据网络增长特性取线性、指数、幂函数等多种形式(3) 模型的两个特例θ(t) 为常数时，退化为RDP 模型 (Ramasco et al，2004) n=2 且θ(t) =0.5时，退化为BA模型(Barabási et al , 1999) 模型度分布的初步解析如果θ(t) 为定值（与时间无关），则可用率方程解析得到网络的节点度分布为：上式为漂移幂律分布（Chang et al，2007），度分布指数（随θ 的减小）从- ∞ 到 -2 变化。如果θ(t) 随时间递减，尚无法求得解析解，后面将给出度分布的仿真分析结果。 模型的仿真分析设定 n = 10, ，每演化100步，对网络的主要拓扑性质进行一次统计，结果见下表：演化步长节点数量边数量节点平均度平均距离平均群聚系数100810453411.203.850.902001510902911.963.780.8730021101351612.81 3.66 0.84 40026101800613.80 3.51 0.82 50030102248814.94 3.38 0.78 60033102695816.29 3.26 0.75 ………………………………特征：平均度随时间增加，平均距离随时间下降，平