一种动态的无标度网络模型.pdf

2009年 11月 第 32卷 第 6期 四川师范大学学报 自然科学版 Journal of Sichuan Nor malUniversity NaturalScience Nov 2009 Vo l 32 No 6 收稿日期 2008 06 30 基金项目 国家自然科学基金 10647005 和贵州省科学技术基金 20062006 资助项目 联系作者简介 蔡绍洪 1958 男 教授 博导 主要从事非线性物理和复杂性理论的研究 一种动态的无标度网络模型 贾秀丽 1 蔡绍洪1 2 张芙蓉 1 1 贵州大学 物理系 贵州 贵阳 550025 2 贵州财经学院 贵州省经济系统仿真重点实验室 贵州 贵阳 550004 摘要 针对 BA无标度网络模型模拟现实世界的局限性 同时参考其它扩展模型的结果 提出一种新模 型 该模型包含新节点的加入和旧节点的删除 旧节点之间择优的再生连接和反择优的删除连接 运用连续 介质理论和平均场理论建立起与之对应的演化方程 并计算出了它的严格解 导出了该模型的度分布和幂 律指数的表达式 分析结果表明该模型能自组织演化成无标度网络 其幂律指数在 1 3范围内 调节参数就 可与现实中的许多复杂网络的幂律指数相吻合 因此 该模型更具有一般性 关键词 复杂网络 BA 模型 度分布 幂律指数 无标度网络 中图分类号 O414 2 文献标识码 A 文章编号 1001 8395 2009 06 0839 04 do i 10 3969 j issn 1001 8395 2009 06 025 复杂网络由于可以用于描述如社会 生物 经 济 物理以及计算机等许多复杂性系统 近年来倍 受重视且得到了广泛及不断深入的研究 1 2 复杂 网络就是把真实的复杂网络系统抽象成一些节点 和一些线条 节点代表研究的对象个体 线条则代 表了这些个体之间的相互作用关系 描述网络结构 的一个重要测度是网络的度分布函数 P k 其定 义是 随机抽取网络中的某个节点 该节点具有 k 条边的概率 传统的图论 3 以及小世界网络 4 的研 究表明 P k 随 k具有指数衰减规律 然而 近年来 的研究表明 许多实际网络系统其度分布函数P k 随 k的变化表现为幂律形式 即 P k Wk C 其中 C 为幂指数 随着系统的不同而不同 为了描述具有 幂律形式度分布函数的网络系统 Barab si和 A l bert提出了著名的网络演化模型即 BA模型 5 并 提出生长和择优是产生幂律型度分布函数的两大 因素 在 BA模型的基础上 涌现出了大批的推广改 进模型及其相关研究 6 15 各推广改进模型都有其 自身的优缺点 为了更好地了解现实网络的性质 建立与现实网络相一致的模型是重要的 因此 无 标度网络模型是一个值得研究的课题 本文在 BA模型的基础上 同时参考其它扩展 模型的结果 提出一种新模型 利用连续介质理论 和平均场理论对该模型的演化方程进行分析和研 究 导出其度分布和幂律指数的表达式 以期能更 真实地反映和描述现实中实际复杂网络的物理性 质和演化规律 1 动态的网络模型的建立背景及其基本构造 BA网络模型最终演化成幂律指数恒定为 3的 无标度网络 BA模型的重要意义在于它首次捕捉 到了许多真实网络的幂律形成机制 抓住了网络的 本质特征 从理论上解释了无标度网络的现象 BA 模型是能够很好地解释网络的无标度特征 但是它 也有模型设计上的不足 如它是生长网络模型 它 只有节点的加入却没有节点的删除和节点间的重 新连接 其实一般自然的或者人造的网络更多的是 要与外界有节点交换的 而且节点间的连接也是不 断变化的 所以说 BA模型是不能反映现实网络的 真实情况的 为了对现实网络进行更深入的分析和 研究 还需要对 BA 模型进行扩展 它更加符合实 际 换言之 应当考虑更多的相关因素 使之更加全 面地反映现实存在的不同网络 在现实的不同网络 中 节点及节点间的相互连接情况是不一样的 比 如说文献索引网和科学家协作网 在这些网络中 一旦两个节点组成一个连接 那么这个连接就不会 被删除 相应的两个节点也不会离开这个网络 而 对于 world w ide web中的节点 节点容易加入到网 络中 也容易离开网络 同时已经存在的连接却很 可能会被轻易地删除 删除连线时采用反择优概率 更为合理 新的连接也可能会被轻易地产生 增加 连线时采用择优概率比较合理 当然 当一个节点 所有的连接都被删除时就可以认为这个节点本身 被删除了 若再次被连接则可视为新节点的加入 再如 在市场经济中 企业之间的供销关系并非一 成不变的 而总是处在不断变化之中 不断的有新 企业加入到网络中来 也有旧企业由于各种原因离 开了原网络 同时在老企业之间很可能会产生新的 连接 老的连接也可能轻易的删除 显然 BA模型是 无法描述这一种类型的网络特征的 因为网络节点 本身或者节点之间的连接既是不稳定的也是不可 靠的 因此 在 BA模型基础上 考虑到原有网络中 的节点随时都有可能离开网络 老节点之间的连接 既是不稳定的也是不可靠的 即既可以产生新连 接 也随时会断开一些旧连接 为了描述这种网络 的特征 建立一种动态的网络模型 该模型的基本 构造如下 开始时 t 0 网络内至少有 m0 m0 1 个少 量孤立节点 在此后的每一个时间步长内都会有 4 个操作过程发生 1 生长择优 增加一个新节点 新节点与网 络中原有的 m m m0 个不同点相连接 产生 m 条 新边 且新节点与旧节点 i相连接的择优概率 0i ki E j kj 1 2 在原网络中删除 c个旧节点 随机地删除 原网络中 c个节点 以及与 c个节点相连接的边都 被删除 3 在原网络在增加 r条新连边 新边的两个 端点均以择优概率被选取 旧节点 i成为新边一端 点的概率仍由 1 式确定 4 在原网络中删除 n条旧连边 删除的连线 的两个端点均以反择优概率被选取 旧节点 i成为 新边一端点的概率 0ic 1 0i N t 1 2 用 N t 表示在 t时刻网络中所有的节点数 即 N t 1 c t m0 用 S t 来表示 t时刻网络中所有 节点的度的总和 即 S t E j kj 则 t时刻网络中 节点的平均度3k t 4 S t N t 2 该模型的度分布及幂律指数推导 运用连续介质理论和平均场理论 可以获得网 络中节点 i的度分布 假设 ki是连续变化的 则 ki 满足的动力学方程 5ki 5t m 0i c ki N t r 0i 1 E jX i 0i0j n 0i 1 E jX i 0ic0jc 3 解释每 1项的含义 第 1项是新节点加入到网络中 引起 ki的变化 第 2项是随机删除节点引起 ki的 变化 第 3项是在网络择优加边引起 ki的变化 第 4项是在网络反择优删除边引起 ki的变化 在 t时 刻节点的平均度为 3k t 4 S t N t 2 m c3k t 4 r n 1 c 4 因此3k t 4 2 m r n 1 c 把 N t 1 c t 对充分大的 t 和节点的平均度代入 4 式得 S t 2 m r n 1 c 1 c t 5 把 S t N t 代入方程 3 近似为一阶线性微分 方程 5ki 5t m 2r cm 2cn 2 m r n 1 c ki t 2n 1 c 1 t 6 令 a m 2r cm 2cn 2 m r n 1 c b 2n 1 c 其初始条件 ki ti m 因此有 ki t m b a t ti a b a 7 解关于 ti的不等式 ki ti t m b a k b a 1 a 8 由此得到 P ki t m b a k b a 1 a 1 P ti t m b a k b a 1 a 9 840 四川师范大学学报 自然科学版 32卷 由于已经假定点 i加入系统的时间服从均匀分布 已经随机 因此得到节点的度分布 P k 5P ki 0 0 c n 这样 把这些参数的范围代到幂律指数 C的表达式 12 中 求出其幂指数 C 的范围为 1 C 3 3 该模型的普适性及适用性分析 该模型是在 BA模型的基础上 结合它改进模 型的优点建立起来的 具有一定的普适性 再改变 参数的值 该模型就会得到已有的结论 该模型中 若没有随机删除节点 连同它的连接一起删除 网 内旧节点之间没有连接 也没有删除 即 r c n 0 这时把这些参数代入 C 的表达式 12 中 算出的 结果为 C 3 没有随机删除节点 连同它的连接一 起删除 网内旧节点之间没有连接 也没有删除 只有生长与择优 这就跟 BA模型一样 这与文 5 中算出的的幂律指数是一样的 这时新模型就退化 成 BA模型 该模型中若没有旧节点之间的择优再 连接和旧节点之间的反择优删除旧连接 即 r n 0 把 r n的值代入 12 式算出 C 3 这就说明导致 无标度网络度分布特征起关键作用是择优连接 而 与随机的删除网络中的旧节点是无明显关系 这与 文 9 中结论是一致的 该模型中若没有删除旧节 点 把 c 0代入 12 式 得出 C 1 2 m r n m 2r 这与文 8 中的结论是完全一致的 因 此 BA模型可以作为新模型的特例 新模型比上述 模型有更深一层的物理内涵 它可以解释它们不能 解释的现象 该模型捕捉到许多实际网络的演化规 律 它能解释许多实际网络 因此更具有普适性 可 以调节参数来调整整个网络的特性 因此就可以根 据实际需要来指导实际网络的构造 这样就可以人 为的进行控制 许多实际网络都是无标度网络 该模型的物理 内涵比其它的模型的物理内涵更加丰富 既考虑了 节点加入网络中来时的择优连接 也考虑了旧节点 随时都有可能离开网络 网络内增加新连接更倾向 择优连接 断边时 那些连边比较少的节点的边更 容易去掉 通过对该模型度分布的计算 我们发现 幂律指数在一个相对广的范围 包含了许多实际网 络度分布的幂律指数 如新陈代谢网络 C 2 1 软 件包网络 C 1 6 C 1 4 对等网络 C 3 蛋白质 网络 C 2 4 www网络 C 2 1 C 2 4 电影演员 合作网络 C 2 3 等 12 现用新模型来解释其中的一个网络 其余的网 络跟这解释与此相类似 电影演员合作网络是把演 员看作节点 两个演员的一次合作看作一条边形 成 文 5 研究得到度分布服从幂律特征且幂律指 数 C 2 3 在开始阶段 只有少数的演员 随着电影 的发展 就不断的有新演员加入到这个网络中来 加入到其中的演员更希望自己与知名度 他 她 的 度比较高 比较高的演员合作 在网络中的演员由 于各方面的原因会不再出演 这种情况是随机的 每个人都有可能 那之前与他 她 相连的边就一 起跟着断开 由于新的一部电影会由网络中的演员 出演 当然选择其中的一个比较出众的演员 选好 之后 他 她 就会有选择找演过好多电影的演员合 作 同时 原来一起同台出演的演员由于形象 演技 等问题 原来与他 她 同时演出的演员不再愿意与 他 她 合作 他们之间的连接随之断开 这个模型 的 4个假设在电影合作网络中都出现 也符合实际 情况 择优 反择优在网络中是应该考虑的 这种现 象在 www网络 企业之间关系的供销网络等中都 出现 用该模型能解释这些网络中出现的现象 通 过 C 的表达式可以调节参数 能得到与实际网络相 同的幂律指数 841 第 6期贾秀丽等 一种动态的无标度网络模型 4 结语 本文提出了一种动态的无标度网络模型 考虑 了新节点的加入 旧节点的删除附带与该节点相连 的边也一并被删除 旧节点之间采用择优的再生连 接与旧节点采用反择优的删除连接 通过连续介质 理论建立方程及严格求解 给出了度分布幂律形式 的渐近解 并求出幂律指数的范围 符合 www网络 电影演员合作网络 企业之间的供销关系网络等的 实际情况 与 BA模型相比较 可以得出这样的结论 产生无标度网络的根本原因是连接的择优机制 旧 节点的删除 旧节点之间的再连与删除则影响幂律 指数 幂律指数由不变变成在一个范围内 通过参数 的设定 该模型可以解释生活中许多的网络 参考文献 1 A lbertR Barab seA L Statisticalmechanics of complex networks J Rev Mod Phys 2002 74 47 97 2 Dorogovtsev S N M endes JF F Evolving ofNet works J Adv Phys 2002 51 1079 1187 3 W atts D F Strogatz SH Collective dynamics of smal lworld network J Nature 1998 393 440 442 4 Erd s P R nyiA On the evolution of random graphs J PublM ath InstHung A cad 1960 5 17 61 5 Barab se A L AlbertR Emergence of scaling in random networks J Science 1999 286 509 512 6 BianconiG Barab se A L Bose Einstein condensation in co mplex networks J Phys Rev Let 2001 86 287 296 7 A lbertR Barab seA L Topology of evolving networks local events and universality J PhysRev Let 2000 85 24 5234 5237 8 ChenQ H ShiD H The modeling of scale free networks J PhysA 2004 335 240 248 9 唐芙蓉 蔡绍洪 李朝辉 无标度网络的嵌入 删除 补偿模型的建立及分析 J 中国矿业大学学报 自然科学版 2005 34 3 390 393 10 汪小帆 李翔 陈关荣 复杂网络理论及其应用 M 北京 清华大学出版社 2006 11 李增扬 韩秀萍 陆君安 等 内部演化的 BA 无标度网络模型 J 复杂系统与复杂性科学 2005 2 2 1 6 12 Ne wmanM E J The structure and function of co mplex net works J SI AM Revie w 2003 45 167 256 13 王力虎 韦思善 陈春旺 复杂网络度分布特征研究 J 广西师范大学学报 自然科学版 2006 24 3 13 16 14 方锦清 网络科学的诞生与发展前景 J 广西师范大学学报 自然科学版 2007 25 3 2 6 15 孙胜秋 用复杂网络理论研究疾病的传播 J 重庆师范大学学报 自然科学版 2005 22 4 1 5 A Dynam ic Scale free Net workM odel JI A Xiu li 1 CAI Shao hong1 2 ZHANG Fu rong 1 1 Department of Physics Guizhou University Guiyang 550025 Guizhou 2 Key Laboratory forEconomic Syste m Simulation of Guizhou Guizhou College of Finance and Economics Guiyang550004 Guizhou Abstract Regarding of some li m itation of the fa mous BA scale free network to si mulate the realisticworld and based on r