周涛 网络传播动力学.ppt

1、复杂网络动力学的一般方法论,中国科学技术大学 近代物理系 周 涛 ,复杂网络的动力学问题,复杂网络上的动力学，是指发生在复杂网络上的动力学过程，例如传播与渝渗、交通流与信息流、级联问题、网络同步、自旋动力学等。而网络自身结构随着时间变化的过程有时候也被称作网络的演化动力学，它与本报告所指的网络动力学隶属不同范畴。,将动力学问题推广到网络上，或者从随机或规则网络推广到一般网络上,讨论动力学在不同网络类上的差别（开始多以定性为主），以及最重要的拓扑量 （平均距离，度分布特征）对动力学的影响（相变点，临界指数等的定量计算）,更细致 的拓扑 量,如簇 系数,相 关性,群 落

2、结构, 权重分 布对动 力学的 影响。,因理论 兴趣或 具体应 用背景 而改变 动力学 规则或 设计特 别的网 络环境,考虑如 何增强 或减弱 某种动 力学的 特征， 如同步 能力交 通能力 等。,研究局 域动力 学，以 及网络 中地位 不同的 节点不 同的局 域动力 学性质,针对具 体的工 程问题 设计相 应的动 力学， 关注网 络拓扑 结构的 影响,动力学 的鲁棒 性问题 主要指 网络拓 扑结构 变化对 相应动 力学的 影响。,网络动 力学的 运筹与 优化问 题，采 用优化 算法提 高某种 动力学 性质。,将动力学问题推广到网络上，或者从随机或规则网络推广到一般网络上,同 步 的 例 子,

3、惠更斯钟摆，青蛙齐鸣，萤火虫的同步发光，心肌细胞和大脑神经网络的同步，剧场中观众鼓掌频率的逐渐同步； 两个动力学系统的耦合同步； 规则网络（完全连通网络）上的动力学同步,目前最前沿和系统的专著：郑志刚，耦合非线性系 统的时空动力学与合作行为，北京，高等教育出版社,同步 on 小世界网络,Gade P M and Hu C-KPhysRevE 2000，62(5)：6409-6413,同步 on 小世界网络,Barahona M and Pecora L MPhysRevLett 2002，89(5)：054101(4),同步 on 无标度网络,Wang X F and Chen GIEEE T

4、ransCircuits SystI 2002，49(1)：54-62,传 播 的 例 子,经典传播模型，对象如流行病、计算机病毒、谣言、恐慌情绪等。 模型如SIR（腮腺炎，艾滋病），SIS（感冒），SI（SARS传播早期）等 方法：微分方程 网络观点：完全图,H. W. Hethcote, SIAM Review, 42, 599(2000).,SIR on General Networks,最早提出应该讨论网络上的SIR问题，并证明该问题与键渝渗等价【P.Grassberger, Math. Biosci., 63, 157(1983) 】 SIR在小世界网络上【C. Moore and

5、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) 】,SIS/SI on General Networks,利用平均场理论得到一般网络上SIS过程的临界传播强度，将其应用于无标度网络，解决了困惑已久的问题 【 R. Pastor-Satorras and A. Vespignani, Phys. Rev, Lett., 86, 3200(2001)； Phys. Rev. E, 63,

6、 066117(2001)】 SI模型在无标度网络上的动力学特性【M. Barthelemy, A. Barrat, R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett, 92, 178701 (2004) 】,Sandpile on scale-free networks 节点异质,K. -I. Goh, et al, Phys. Rev. Lett. 91, 148701(2003),Sandpile on scale-free networks 节点同质,T. Zhou and B. -H. Wang, Chin. Phys. Le

7、tt. 22, 1072(2005),其 他 例 子,交通动力学【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)】,研究最重要的拓扑特征量对动力学的影响相变点位置，临界指数计算，有限尺度效应,同

8、步：小世界网络中重连概率的影响,Hong H，Choi M Y，and Kim B JPhysRevE 2002，65(2)：026139,同步：无标度网络度分布指数对同步能力的影响,T. Nishikawa, et alPhys. Rev. Lett. 91, 014101(2003),同步：平均距离与度分布方差对网络同步能力的影响,M. Zhao, T. Zhou, B.-H. Wang, arXiv: cond-mat/0510332,布尔动力学：度分布方差越大系统总收益越小,T. Zhou, et al, Phys. Rev. E 72, 046139(2005),有限尺度效应,有限大

9、的无标度网络存在正的传播强度临界值【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) 】,更细致的拓扑量,如簇系数,相关性,群落结构,权重分布对动力学的影响。,同步：网络同步能力的上下界,这个上下界是平凡而稀疏的，有兴趣的研究者可以考虑更好的Bounds，或者在某种约束下的Bounds,T. Nishi

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

11、性的影响,对于关联网络，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, P

12、hys. Rev. E, 68, 035103(2003).,传播：簇系数的影响,T. Zhou, G. Yan and B. H. Wang, Phys. Rev. E 71, 046141(2005),其他例子,簇系数增大不利于网络同步【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，

13、10月会议报告】 权重的非均匀分布会使得网络传播变慢【G. Yan, T. Zhou, et al, Chin. Phys. Lett. 22, 510(2005)】,因理论兴趣或具体应用背景而改变动力学规则或设计特别的网络环境,传播：如果可以屠杀,Hayashi等人考虑了线性增长的无标度网络，发现如果想要控制疾病流行，就必须控制种群数量的增长。这个结果对于控制类似于禽流感、口蹄疫等动物疾病有明显的指导意义。,Y. Hayashi, arXiv: cond-mat/0307135. Y. Hayashi,et al, Phys. Rev. E, 69, 016112(2004).,为了讨论同步

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

15、rnndez,et al,Phys. Rev. Lett. 84, 2758(2000),考虑如何增强或减弱某种动力学的特征，如同步能力交通能力等。,在Global Routing框架下如何提高无标度网络的交通能力,G. Yan, T. Zhou, et al, arXiv: cond-mat/0505366,在Local Routing框架下如何提高无标度网络的交通能力,C. Y. Yin, B. H. Wang, W. X. Wang, T. Zhou, H. J. Yang Phys. Lett. A (In Press) (arXiv: physics/0506204),能否通过接种疫

16、苗控制传染病？,熟识者免疫的策略从空白处挖掘信息【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. Barabsi, Phys. Rev. E, 65, 055103(2002). 】,控制级联从边缘节点入手,A. E. Motter, Phys. Rev. Lett. 93, 098701(2004),控

17、制级联从中心节点入手,T. Zhou and B. -H. Wang, Chin. Phys. Lett. 22, 1072(2005),通过调节耦合强度提高网络同步能力同步与交通的内在联系,E. Motter et alPhysRevE 71,016116(2005) See also M.Chavez et al,Phys. Rev. Lett. 94, 218701(2005),通过结构微扰提高网络的同步能力,M. Zhao, T. Zhou, B. H. Wang, and W. X. Wang, Phys. Rev. E 72, 057102(2005),研究局域动力学，以及网络中地

18、位不同的节点不同的局域动力学性质,例子虽少，前景看好,高集聚性的网络局部同步能力很好，但全局同步能力较差【P.N. McGraw and M. Menzinger,Phys. Rev. E72 015101(2005)】 Motif-Modular-Network的多级结构可以显著的改变网络的局域动力学性质【本研究小组的观察事实，尚未成文】,动力学的鲁棒性问题主要指网络拓扑结构变化对相应动力学的影响。,无标度网络的同步鲁棒性,Wang X F and Chen GIEEE TransCircuits SystI 2002，49(1)：54-62,网络动力学的运筹与优化问题，采用优化算法提高某种

19、动力学性质。,通过优化度分布熵改变网络的鲁棒性,B. Wang, H. W. Tang, C. H. Guo, Z. L. Xiu, Physica A Doi: 10.1016/j.physa.2005.08.025,利用爬山算法优化网络效率，保持平均度不变,比较优化的网络具有 少量的中心节点和整体的类星结构； 大的簇系数 模块化程度高,B. Wang, H. W. Tang, Z. L. Xiu, C. H. Guo, and T. Zhou, arXiv: cond-mat/0509711,在平均度一定的情况下优化无标度网络的鲁棒性,J. G. Liu, et al, Mod. Phys

20、. Lett. B 19, 785(2005),利用全局寻优算法优化网络同步能力，保持各节点度不变,比较优化的网络具有 负相关性； 小的簇系数； 低的模块化程度； 较少的低阶环；,B. Wang, H. W. Tang, T. Zhou, and Z. L. Xiu, Preprint,无标度网络在随机攻击下的鲁棒性优化，保持平均度不变,J. G. Liu, et al, Mod. Phys. Lett. B (In Press),针对具体的工程问题设计相应的动力学，关注网络拓扑结构的影响,电力系统的级联故障 一个典型的例子,最优潮流方法模型【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的网络交通动力学问题,结束语,Mark Newman 在其综述中