复杂网络动力学的 一般方法论 中国科学技术大学 近代物理系 周 涛

Presentation on theme: "复杂网络动力学的 一般方法论 中国科学技术大学 近代物理系 周 涛"— Presentation transcript:

1 复杂网络动力学的 一般方法论 中国科学技术大学 近代物理系 周 涛 zhutou@ustc.edu

2 复杂网络的动力学问题 复杂网络上的动力学，是指发生在复 杂网络上的动力学过程，例如传播与 渝渗、交通流与信息流、级联问题、 网络同步、自旋动力学等。而网络自 身结构随着时间变化的过程有时候也 被称作网络的演化动力学，它与本报 告所指的网络动力学隶属不同范畴。

3 将动力学问题推广到网络上，或者从随机或规则网络推广到一般网络上 讨论动力学在不同网络类上的差别（开始多以定性为主），以及最重要的拓扑量 （平均距离，度分布特征）对动力学的影响（相变点，临界指数等的定量计算） 更细致 的拓扑 量, 如簇 系数, 相 关性, 群 落结构, 权重分 布对动 力学的 影响。 因理论 兴趣或 具体应 用背景 而改变 动力学 规则或 设计特 别的网 络环境 考虑如 何增强 或减弱 某种动 力学的 特征， 如同步 能力交 通能力 等。 研究局 域动力 学，以 及网络 中地位 不同的 节点不 同的局 域动力 学性质 针对具 体的工 程问题 设计相 应的动 力学， 关注网 络拓扑 结构的 影响 动力学 的鲁棒 性问题 主要指 网络拓 扑结构 变化对 相应动 力学的 影响。 网络动 力学的 运筹与 优化问 题，采 用优化 算法提 高某种 动力学 性质。

4 将动力学问题推 广到网络上，或 者从随机或规则 网络推广到一般 网络上

5 同 步 的 例 子 惠更斯钟摆，青蛙齐鸣，萤火虫的同步 发光，心肌细胞和大脑神经网络的同步， 剧场中观众鼓掌频率的逐渐同步； 两个动力学系统的耦合同步； 规则网络（完全连通网络）上的动力学 同步 目前最前沿和系统的专著：郑志刚，耦合非线性系 统的时空动力学与合作行为，北京，高等教育出版社

6 同步 on 小世界网络 Gade P M and Hu C-K ． Phys ． Rev ． E 2000 ， 62(5) ： 6409-6413 ．

7 同步 on 小世界网络 Barahona M and Pecora L M ． Phys ． Rev ． Lett ． 2002 ， 89(5) ： 054101(4) ．

8 同步 on 无标度网络 Wang X F and Chen G ． IEEE Trans ． Circuits Syst ． I ． 2002 ， 49(1) ： 54-62 ．

9 传 播 的 例 子 经典传播模型，对象如流行病、计算机 病毒、谣言、恐慌情绪等。 模型如 SIR （腮腺炎，艾滋病）， SIS （感冒）， SI （ SARS 传播早期）等 方法：微分方程 网络观点：完全图 H. W. Hethcote, SIAM Review, 42, 599(2000).

10 SIR on General Networks 最早提出应该讨论网络上的 SIR 问题，并 证明该问题与键渝渗等价【 P.Grassberger, Math. Biosci., 63, 157(1983) 】 SIR 在小世界网络上【 C. Moore and M. E. J. Newman, Phys. Rev. E, 61, 5678(2000) 】 SIR 在无标度网络上【 Y. Moreno, J. B. Gomez and A. F. Pacheco, Phys. Rev. E, 68, 035103(2003) 】

11 SIS/SI on General Networks 利用平均场理论得到一般网络上 SIS 过程的临 界传播强度，将其应用于无标度网络，解决了 困惑已久的问题 【 R. Pastor-Satorras and A. Vespignani, Phys. Rev, Lett., 86, 3200(2001) ； Phys. Rev. E, 63, 066117(2001) 】 SI 模型在无标度网络上的动力学特性【 M. Barthelemy, A. Barrat, R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett, 92, 178701 (2004) 】

12 Sandpile on scale-free networks —— 节点异质 K. -I. Goh, et al, Phys. Rev. Lett. 91, 148701(2003)

13 Sandpile on scale-free networks —— 节点同质 T. Zhou and B. -H. Wang, Chin. Phys. Lett. 22, 1072(2005)

14 其 他 例 子 交通动力学【 L. Zhao, et al, Phys. Rev. E 71, 026125(2005); T. Zhou, et al, to appear in Dynamics of Continuous, Discrete and Impulsive Systems B 】 布尔动力学【 T. Zhou, et al, Phys. Rev. E 72, 046139(2005) 】 博弈问题【 M. A. Nowak, Nature 428, 646(2004) 】

15 研究最重要的拓扑 特征量对动力学的 影响 —— 相变点位 置，临界指数计算， 有限尺度效应

16 同步：小世界网络中 重连概率的影响 Hong H ， Choi M Y ， and Kim B J ． Phys ． Rev ． E 2002 ， 65(2) ： 026139

17 同步：无标度网络度分布指数 对同步能力的影响 T. Nishikawa, et al ． Phys. Rev. Lett. 91, 014101(2003)

18 同步：平均距离与度分布方差对 网络同步能力的影响 M. Zhao, T. Zhou, B.-H. Wang, arXiv: cond-mat/0510332

19 布尔动力学：度分布方差越大系 统总收益越小 T. Zhou, et al, Phys. Rev. E 72, 046139(2005)

20 有限尺度效应 有限大的无标度网络存在正的传播强度 临界值【 R. M. May et al, Phys. Rev. E, 64, 066112 (2001) ； R. Pastor-Satorras et al, Phys. Rev. E, 65, 035108(2002) 】 利用有限尺度效应求小世界网络同步的 耦合强度临界值【 H. Hong, Phys. Rev. E 65, 026139(2002) 】

21 更细致的拓扑量, 如 簇系数, 相关性, 群 落结构, 权重分布对 动力学的影响。

22 同步：网络同步能力的上下界 这个上下界是平凡而稀疏的，有兴趣的 研究者可以考虑更好的 Bounds ，或者在 某种约束下的 Bounds T. Nishikawa, et al ． Phys. Rev. Lett. 91, 014101(2003)

23 同步：最大介数扮演的角色 认为可以用最大介数刻画网络同步能力，或者 至少是最恰当的量【 H. Hong et al, Phys. Rev. E 69, 067105(2004) 】 认为最大介数能够在很大程度上表征网络的同 步能力【 T. Nishikawa, et al ． Phys. Rev. Lett. 91, 014101(2003) 】 认为最大介数只能在某些特定网络中反映网络 同步能力【 M. Zhao, T. Zhou, B.-H. Wang, arXiv: cond-mat/0510332 】

24 传播：相关性的影响 对于关联网络， Boguna 和 Pastor-Satorras 给出 了 SIS 模型传播的临界值为 1/Rmax, 其中 Rmax 为 邻接矩阵的最大特征值。 Boguna 等人进一步证 明了当度分布二阶矩发散时， Rmax 趋于无穷， 亦即在无尺度网络中，不管是关联网络还是非 关联网络，都不存在正的临界值。 Moreno 等人 分析了关联网络上的 SIR 模型，也得到了类似 的结论。 M. Boguna, et al, Phys. Rev. E, 66, 047104 (2002). M. Boguna, et al, Phys. Rev. Lett., 90, 028701 (2003) Y. Moreno,et al, Phys. Rev. E, 68, 035103(2003).

25 传播：集聚系数的影响 T. Zhou, G. Yan and B. –H. Wang, Phys. Rev. E 71, 046141(2005)

26 其他例子 集聚系数增大不利于网络同步【 M. Zhao, T. Zhou, B.-H. Wang, arXiv: cond-mat/0510332 ； X. Wu, B. –H. Wang, T. Zhou, et al, Preprint 】 网络在一定的相关性区间内比较容易同步 【陈关荣， 10 月会议报告】 群落结构会影响传播行为【刘宗华， 10 月会 议报告】 群落结构会影响网络同步【 Y. -C. Lai ， 10 月 会议报告】 权重的非均匀分布会使得网络传播变慢【 G. Yan, T. Zhou, et al, Chin. Phys. Lett. 22, 510(2005) 】

27 因理论兴趣或 具体应用背景 而改变动力学 规则或设计特 别的网络环境

28 传播：如果可以屠杀 Hayashi 等人考虑了线性增长的无标度网 络，发现如果想要控制疾病流行，就必 须控制种群数量的增长。这个结果对于 控制类似于禽流感、口蹄疫等动物疾病 有明显的指导意义。 Y. Hayashi, arXiv: cond-mat/0307135. Y. Hayashi,et al, Phys. Rev. E, 69, 016112(2004).

29 为了讨论同步专门采用的传播模型 Kuperman 和 Abramson 研究了 WS 网络上的 SIRS 模型，他们发现当断键重连概率很小 (p=0.01) 的时候，疾病可以在网络中长期存在，但患病 比率很小切波动不大，可以近似地看作收敛到 一个不动点；而当断键重连概率很大 (p=0.9) 的 时候，患病人数会出现周期性的波动。他们进 一步研究了 WS 网络上传播行为的同步效应， 发现了随着的增长，系统会出现从非同步相到 同步相的相变。 M. Kuperman and G. Abramson, Phys. Rev. Lett., 86, 2909(2001).

30 利用 HH 神经动力学方程讨论小世 界网络的快速响应和相干振荡 L.F. Lago-Fernández,et al,Phys. Rev. Lett. 84, 2758(2000)

31 考虑如何增强 或减弱某种动 力学的特征， 如同步能力交 通能力等。

32 在 Global Routing 框架下如何提高 无标度网络的交通能力 G. Yan, T. Zhou, et al, arXiv: cond-mat/0505366

33 在 Local Routing 框架下如何提高无 标度网络的交通能力 C. Y. Yin, B. H. Wang, W. X. Wang, T. Zhou, H. J. Yang Phys. Lett. A (In Press) (arXiv: physics/0506204)

34 能否通过接种疫苗控制传染病？ 熟识者免疫的策略 —— 从空白处挖掘信 息【 R. Cohen, S. Havlin and D. ben-Avraham, Phys. Rev. Lett., 91, 247901(2003). 】 目标免疫 —— 效果虽好要求过高【 Pastor- Satorras R et al, Phys. Rev. E 65, 036104(2002) 】 比例优先免疫【 Z. Dezsö and A-L. Barabási, Phys. Rev. E, 65, 055103(2002). 】

35 控制级联 —— 从边缘节点入手 A. E. Motter, Phys. Rev. Lett. 93, 098701(2004)

36 控制级联 —— 从中心节点入手 T. Zhou and B. -H. Wang, Chin. Phys. Lett. 22, 1072(2005)

37 通过调节耦合强度提高网络同步 能力 —— 同步与交通的内在联系 A.E. Motter et al ． Phys ． Rev ． E 71,016116(2005) See also M.Chavez et al,Phys. Rev. Lett. 94, 218701(2005)

38 通过结构微扰提高网络的同步能力 M. Zhao, T. Zhou, B. H. Wang, and W. X. Wang, Phys. Rev. E 72, 057102(2005)

39 研究局域动力 学，以及网络 中地位不同的 节点不同的局 域动力学性质

40 例子虽少，前景看好 高集聚性的网络局部同步能力很好，但 全局同步能力较差【 P.N. McGraw and M. Menzinger,Phys. Rev. E72 015101(2005) 】 Motif-Modular-Network 的多级结构可以 显著的改变网络的局域动力学性质【本 研究小组的观察事实，尚未成文】

41 动力学的鲁棒 性问题主要指 网络拓扑结构 变化对相应动 力学的影响。

42 无标度网络的同步鲁棒性 Wang X F and Chen G ． IEEE Trans ． Circuits Syst ． I ． 2002 ， 49(1) ： 54-62 ．

43 网络动力学的 运筹与优化问 题，采用优化 算法提高某种 动力学性质。

44 通过优化度分布熵改变 网络的鲁棒性 B. Wang, H. W. Tang, C. H. Guo, Z. L. Xiu, Physica A Doi: 10.1016/j.physa.2005.08.025

45 利用爬山算法优化网络效率， 保持平均度不变 比较优化的网络具有 少量的中心节点和整体的类星结构； 大的簇系数 模块化程度高 B. Wang, H. –W. Tang, Z. –L. Xiu, C. –H. Guo, and T. Zhou, arXiv: cond-mat/0509711

46 在平均度一定的情况下优化无标 度网络的鲁棒性 J. G. Liu, et al, Mod. Phys. Lett. B 19, 785(2005)

47 利用全局寻优算法优化网络同步 能力，保持各节点度不变 比较优化的网络具有 负相关性； 小的集聚系数； 低的模块化程度； 较少的低阶环； B. Wang, H. –W. Tang, T. Zhou, and Z. –L. Xiu, Preprint

48 无标度网络在随机攻击下的鲁棒 性优化，保持平均度不变 J. G. Liu, et al, Mod. Phys. Lett. B (In Press)

49 针对具体的工 程问题设计相 应的动力学， 关注网络拓扑 结构的影响

50 电力系统的级联故障 —— 一个典型的例子 最优潮流方法模型【 Carreras B A, et al. Chaos, 12, 985(2002) ;ibid 14, 643(2004) 】 点超载的级联故障模型【 Albert R, et al. Phys. Rev. E, 69, 025103(2004) 】 电力网络的演化模型【 Chassin D P and Posse C. Physica A, 355, 667(2005). 】 其他例子还有无线传感网络的路由策略，以及牵涉到 TCP/IP 协议，包括 IPv6 的网络交通动力学问题

51 ……

52 结束语 Mark Newman 在其综述中指出： “ 复 杂网络研究最重要的目标之一就是揭 示网络结构对动力学的影响 ” 。这种 研究的应用价值也是明显的，因为我 们可以通过这种研究找到改变网络结 构从而改变其上动力学行为的方法。 M. E. J. Newman, SIAM Review 45, 167(2003)

53 结束语 讨论网络静态结构对其上动力学的影 响，只是复杂网络动力学研究的第一 步，用 Newman 的话说叫做零阶近似。 进一步应该研究网络拓扑结构和其上 动力学的相互影响相互作用。 朱陈平等, Phys. Rev. Lett. 92, 218702(2004) 王文旭等, Phys. Rev. Lett. 94, 188702(2005)

54 王 婆 卖 瓜 周涛，柏文洁，汪秉宏，刘之景，严钢， ” 复杂网络研究概论 ” ， 物理, 34, 31-36, 2005 周涛，傅忠谦，牛永伟，王达，曾燕，汪秉宏，周佩玲， ” 复杂 网络上传播动力学研究综述 ”, 自然科学进展， 15(5) ， 513-518 ， 2005 汪秉宏，周涛，何大韧， ” 统计物理学与复杂系统研究最新发展 趋势分析 ” ，中国基础科学， 2005 （ 3 ）： 37-43 赵明，汪秉宏，蒋品群，周涛， “ 复杂网络上动力系统同步的研 究进展 ” ，物理学进展， 25 ， 273-295(2005) 柏文洁，汪秉宏，周涛， “ 从复杂网络的观点看大停电事故 ” ， 复杂系统与复杂性科学 T. Zhou, Z. –Q. Fu, and B. –H. Wang, “Epidemic Dynamics on Complex Networks”, Prog. Natl. Sci. (arXiv: physics/ 0508096)

55 谢