【作者】 郑建风；

【导师】 高自友；

【作者基本信息】 北京交通大学 ， 系统分析与集成， 2010， 博士

【摘要】 在过去的几年中,有关与网络刻画和理解的研究工作非常活跃。事实上,在许多自然和人造系统中都存在着大量的大规模复杂网络。本论文运用统计物理、运筹学以及计算机模拟等方法,从复杂网络建模和典型复杂网络(即随机网络、小世界网络和无标度网络)上的动力学过程这两个方面进行了相关的分析与研究。重点研究了典型复杂网络上的流量分布与阻塞、级联失效行为以及基于离散时间和离散状态的同步行为。本论文的主要工作和创新点如下：(1)在复杂网络建模方面,首先介绍了三个典型的复杂网络模型,即Erdos-Renyi随机网络模型、Watts-Strogatz小世界网络模型和Barabasi-Albert无标度网络模型。然后,提出了非对称演化网络模型和基于交通流演化的加权网络模型。在非对称演化网络模型中,引入了节点效用的概念,并且新节点在选择网络中已有节点进行连结时遵从效用偏好的机制,对建立连结的两个节点的效用值以不同概率增长来表征网络的非对称特性。理论分析和数值模拟均表明网络中节点的效用分布服从幂律分布,而度分布则介于指数分布和幂律分布之间。在基于交通流演化的加权网络模型中,交通流的状态被认为是网络中的节点,如果某一个交通流状态能够在一个时间步演化成另一个交通流状态,则在这两个交通流状态(即节点)之间建立连边,而交通流状态在演化过程中传输的交通流量被认为是边上的权重。从理论分析和数值模拟的角度,研究了节点强度和度之间的非线性相关关系。(2)基于用户均衡模型,研究典型复杂网络(特别是无标度网络)上流量分布的规律,研究发现无标度网络上的流量分布在这种情况下可以呈现出指数分布或者幂律分布的形式。基于元胞传输模型,分析了梯度网络上的阻塞特性,研究发现,随着网络中阻塞程度的增加,阻塞程度在随机网络和无标度网络之间的差值呈现出先增加,后减小,最后又增加的趋势。此外,基于一定的流量演化规则,类似于拥挤条件下的随机游走行为,研究了典型复杂网络上的阻塞消散和流量波动特性,并引入了截流以及截流和诱导两种拓展方式来缓解网络中的局部阻塞,研究发现这两种拓展方式并不会加重网络中的全局阻塞；截流和诱导的方式可以在一定程度上缓解无标度网络(即异质网络)中的全局阻塞,并且可以减少网络中流量的波动特性。(3)在级联失效方面,本论文将一个基于简单网络的光纤束模型拓展到无标度网络,研究了网络上的边失效行为。理论分析表明,当节点流量和度之间的幂律指数大于度分布的幂律指数时,网络中的平均边失效比例与网络规模之间存在幂律关系,且幂律指数为-1,与度分布的幂律指数无关。基于用户均衡模型,研究了拥挤效应和网络结构对级联失效的影响。研究发现,拥挤效应对级联失效具有一定的正效应,而网络的异质结构对级联失效是负效应。即：适当地增加网络中的拥挤,可以提高网络抗级联失效的能力；度分布指数较小的无标度网络上的级联失效将更加严重。最后,提出了一个较符合城市交通网络中拥堵传播消散特性的级联失效模型,并探讨了反馈效应对级联失效的影响。研究表明,反馈效应可以减少随机网络和无标度网络在抗级联失效方面的差异。(4)提出了基于离散时间和离散状态的同步模型。为了刻画网络中节点状态的自驱动函数,引入了节点的状态转移矩阵。通过针对典型复杂网络上的数值研究表明,同步指标把耦合强度划分为四个区：递增区、最大区、递减区和振荡区,为复杂网络上同步行为的研究提供了新的视角。更多还原

【Abstract】 The last few years have witnessed tremendous activities devoted to the characterization and understanding of networked systems. Indeed many large complex networks arise in a vast number of natural and artificial systems. In this thesis, complex network modeling and dynamical processes in typical complex networks (i.e., random networks, small-world networks and scale-free networks) are studied by using statistics physics, operational research and computer simulation. This thesis focuses on investigating load distributions, traffic jamming, cascading failures and synchronization with discrete time and discrete state in typical complex networks. The main contents of this thesis are summarized as follows:(1) On the issue of complex network modeling, firstly, three typical complex network models, i.e., Erdos-Renyi random network model, Watts-Strogatz small-world network model and Barabasi-Albert scale-free network model are simply introduced. Then, an asymmetrical evolving network model and a weighted model evolution with traffic flow are presented. In the asymmetrical evolving network model, the concept of utility is introduced. The probability for the new node chosing old nodes to be connected is proportional to the utility of the old node. Moreover, the utilities of the connected nodes update asymmetrically. Both theoretical analysis and simulation results show that the distribution of utility follows a power law, and the degree distribution is between the exponential distribution and power law distribution,In the weighted model evolution with traffic flow, the state of traffic flow is considered as a node, an edge between two nodes is created if one state of traffic flow can evolve into another at one time step, and the transferred traffic volume is considered as the weight of the edge. Non-linear relationship between the strength and degree of the node is studied theoretically and by numerical tests.(2) Based on user equilibrium model, this thesis discusses load distribution in typical complex networks (especially in scale-free networks) under the effect of congestion. It is found that load distribution may follow as exponential distribution or power law distribution in scale-free networks. Based on cell transmission model, traffic jamming in gradient networks is analyzed. The difference of the jamming factor between random networks and scale-free networks is found to increase firstly, and then decrease and finally increase, with the increase of the degree of traffic jamming. In terms of the traffic evolving rule, which is similar to random walks under the condition of congestion, the diffusion of congestion and flow fluctuations in typical complex networks are studied. And two extended cases, i.e., stopping traffic flows and stopping and guiding traffic flows are presented to relieve local congestion. Simulation results show that the two extended cases can not aggravate global congestion, and the second extended case can be used to relieve global congestion and flow flunctions in scale-free networks (i.e., heterogeneous networks).(3) On the issue of cascading failures, a simple fiber bundle model is extended to scale-free networks to study the behavior of edge failures. Theoretical analysis and simulation results show that, when the exponent of the scaling between the load and degree of the node is larger than the exponent of the degree distribution, there is a scaling relationship between the average rate of failed links and the network size, where the exponent is-1, independent of the exponent of degree distribution. Based on user equilibrium model, the effects of congestion and network structure on cascading failures are investigated. Simulation results show that the effect of congestion has an active effect and the effect of network heterogeneity has a negative effect on influencing the behavior of cascading failures. In other words, the performance of the network against cascading failures can be improved by properly increasing the congestion of the network, and scale-free network with larger value of the exponent of degree distribution is more prone to suffer from cascading failures. Finally, a model for cascading failures fitting urban traffic networks is proposed, and the effect of feedback is also studied. We find that the effect of feedback can reduce the discrepancy between random networks and scale-free networks against cascading failures.(4) In this thesis, a synchronization model with both discrete time and discrete state is presented. A transfer matrix for the node’s state is introduced to determine its self-driven function. Simulation results in typical complex networks show that, according to the synchronization index, the coupling strength is divided into four regions:the increasing region, the maximum region, the decreasing region and the oscillation region. It may shed new insights on investigating synchronization behavior in complex networks.更多还原