【作者】 殷传洋；

【导师】 汪秉宏；

【作者基本信息】 中国科学技术大学 ， 理论物理， 2008， 博士

【摘要】 复杂网络是近年来兴起的一门新兴交叉学科,由于其研究对象的普遍性和多样性,受到国内外众多学科研究人员的广泛关注。在我们周围,网络无处不在,遍及自然界和人类社会。任何一个复杂系统都可以抽象成为由相互作用的个体组成的网络,其中个体抽象为网络节点,个体间的相互作用抽象为网络连边。其中广为人们熟知并具有代表性的网络包括互联网、万维网、铁路网、航空网、电力网、蛋白质相互作用网、新陈代谢网、基因调控网、神经网、人际关系网等等。深入研究这些网络不仅对人们的工作和生活具有现实意义,而且对了解自然界和社会的发展具有深远的科学和社会意义。复杂网络研究关注个体之间的微观相互作用导致的系统的宏观现象。和传统还原论方法不同,复杂网络把整个系统作为研究对象,专注于系统中个体的相互作用,预言复杂系统丰富的整体行为,包括自组织特性,涌现等。在科学高度发展的今天,以整体的、网络的观点研究各种复杂现象已经成为科学研究的必然趋势。复杂网络的研究已经渗透到自然科学和社会科学的各个方面,突破了学科之间界限,极大地推动了数学、物理、化学、生物学、信息工程和其它社会科学等多学科的交叉和发展。因此,复杂网络研究具有重大的理论价值。研究复杂网络的最终目标是理解网络结构如何影响发生于网络上的各种动力学过程。网络上的信息传播和网络上的耦合现象研究是其中非常重要的研究内容。文献中大量的传播动力学和网络同步的论文,包括网络上的病毒传播、信息传播、博弈过程和同步现象等,从各自不同的角度研究复杂系统的特性。根据当前国内外复杂网络的研究动态和发展趋势,我们在网络上的信息流传播和网络的耦合同步现象的动力学过程方面做了比较系统的工作,本文的主要工作如下:比较系统地研究了无标度网络上的信息传播动力学,首次提出了基于局域拓扑信息路由策略的概念。随着互联网等大型通讯网络的广泛应用,网络规模变得越来越庞大,网络结构也越来越复杂,网络拥塞变得越来越普遍,特别是网络的拓扑结构也在不断的变化之中,这使得基于网络全局拓扑信息的传统路由策略遭受日益紧迫的存储和计算能力的压力。不同于过去的基于网络全局拓扑信息的数据包路由规则,我们提出了基于局域拓扑信息的数据包路由规则,研究了系统中信息流从自由流态到阻塞流态的相变特性,并以此特性为标准来刻画网络的总体通讯能力;研究了这些算法的各种时间和空间特性。我们还发现适当地增加网络结构的拓扑信息量,比如考虑网络节点次近邻信息,可以极大地提高通讯网络的总体通讯能力。在实际设计网络路由算法时可以在开销和性能之间取舍,以便可以获得一个最优的解决方案。我们的研究对于目前网络路由协议算法的优化以及新一代路由协议的设计有一定的指导意义。相关的研究论文发表在Physical Review E、European Physics Journal B、Physics LettersA等杂志上。研究了无标度网络上的同步,提出通过去耦合过程来提高网络的同步能力。我们从网络体系拓扑结构出发,对网络结构作一个微扰,研究了网络的特征参量,如平均最短距离、网络的最大介数等参量,对网络同步能力的影响,发现网络的最大介数和网络同步能力存在某种线性关系,因而网络的最大介数在某种情况下(比如网络结构相似),是表征网络同步能力大小的一个最适宜的参量。由于该方法简单易行,在工程实践中可能有很大的潜在应用价值,相关的研究论文发表在Physical Review E上。此外,我们研究了地理约束因素对小世界网络上的同步现象影响。实际的网络很多都是嵌入到一定的空间里的,即网络中的节点占据着一维、二维或者三维空间的一个确定的位置,它们的连边是某种实际的相互作用。典型的实例包括神经网络、信息通讯网络、电力网络、交通网络(包括河流、机场、街道、铁路和公路)等等。我们研究了一维和二维格子上由于地理约束所引起的耦合强度变化对网络同步能力的影响,发现网络的同步能力不仅和空间距离而且和耦合强度都不是一个平凡的关系。我们的研究表明,空间距离的限制在网络的集体同步过程中起到非常重要的作用。由于这类网络在国民经济和人民生活中占据着十分重要的位置,对它们的研究不但是必要的而且是必须的,相关的研究论文发表在Physical Review E上。我们发现网络上的信息传播和网络的耦合同步存在内在的联系,通讯性能表现良好的网络,其网络的同步能力也同样比较强。我们分析了网络上信息传播和同步的关系,同步的过程同时也是耦合信息传播的过程。因此这两个看似无关的研究课题,本质上是相关的过程,分别从不同的方面反映了网络拓扑结构的影响。更多还原

【Abstract】 Complex network modeling has been considered as an important interdiscipline approach for describing and understanding complex systems.Because of universality and diversity of its research objects,it has attracted broad attentions of researchers in many fields all over the world.Complex networks are ubiquitous around our lives, ranging from nature to human socity.Any complex network system can be viewed as a graph of interacted individuals,where nodes denote individuals and links denote interactions between them.The well-known and extensively studied networks include Internet,World Wide Web,railway networks,airport networks,the power grid,proteinprotein interaction networks,metabolic networks,gene regulatory networks,neuron networks,human relationship networks,etc.Extensive researches of these networks in the past a few years have completely changed the traditional view about the real world networks and spurred the rapid development of the interdisciplinary scientific fields.Complex network modeling approach focus on macroscopical phenomena result from the interactions of individuals.Apart from traditional reductionism usually used by physicists,by complex network modeling approach point of view,the investigating system is seen as a whole,the interactions of individuals inside the system are focused on and rich overall behaviors of the system are predicted including self-organised properties, emergence and other phenomena.So far,the investigation of complex networks has covered many fields,including mathmatics,physics,chemistry,biology,technology and social sciences.The ultimate goal of studying complex networks is to understand how topological properties affect the dynamical processes taking place on them.Researches on information propagation and coupling phenomena over complex networks are of the greatest importance.There are many papers concerning propagation dynamics and synchronization over complex networks in the literature,including epidemic spreading, information propagation,game,synchronization and so on.Inspired by the current international research interests,we focused on the information propagation dynamics and synchronization phenomena over the complex networks.The works we do in these fields are following:We have systematically investigated the dynamics of information propagation over scale-free networks.Because the sizes of modern communication networks are becoming bigger and bigger,even worse,the topology of the networks is everchanging,the traditional routing strategies,which based on the global topological information,suffer lack of storage and computational power.Considering this situation,we have proposed several routing strategies of sending data packets only based on local information.We can quantify the capacity of a network by the phase transition from free flow state to congestion state,and we have found the optimal parameter values,resulting in the highest efficiency of scale-free networks.Moreover,we found appropriately increasing information of network topology can greatly increase the capacity of the network,for example,next nearest-neighbor searching strategy.In the practical design of the routing strategy,we can trade off cost against capability of the system in order to find an optimal solution.Our results may be useful for designing next generation routing protocol.We have studied the collective synchronization behavior over scale-free networks and proposed a decoupling process to enhance the synchronizability of scale-free networks. With perturbation on the network structure,we investigated how th characteristic parameters,for example the average shortest path,the maximum betweenness and so on,affect the synchronizability of the networks.We find that the maximum betweenness have a linear-like relation with synchronizability of the network.The results indicate that the maximum betweenness is a best token of network synchronizability among similar network structure so far.We also investigated geographical effect on small-world network synchronization. Many real world networks are embeded in some specific space,nodes have coordinets and links denote some real interactions.We have explored the effects of coupling strength, which coming from geographical restriction,on network synchronizability on one- and two- dimensional lattices.It is found that network synchronizability is a nontrivial function of distance and coupling strength.Our findings shed some light on the collective dynamics of real coupled systems.We find information propagation on a complex network have some relations with synchronization on the network:Networks with high system capacity often show high network synchronizability.Actually,synchronization process is also a process of transmission of coupling information.The two seemingly irrelevant research subjects have the same underlying dynamical nature,reflecting different aspects of the properties of the system.更多还原