面向复杂网络的节点重要性排序和级联失效研究

发布时间：2018-01-04 05:22

本文关键词：面向复杂网络的节点重要性排序和级联失效研究　出处：《重庆大学》2016年博士论文　论文类型：学位论文

【摘要】：20世纪90年代末期,随着小世界网络和无标度网络模型的提出,复杂网络的研究进入了一个崭新的阶段,越来越多的人开始关注复杂网络。作为复杂性科学的一个重要分支,复杂网络的理论研究得到飞速发展,并且已经渗透到数理学科、生命科学以及工程学科等各种领域。当今随着物联网的兴起和发展,智慧城市进程的加快,各种网络系统纷纷涌现并得到快速发展,人类社会生活已经越来越依赖这些基础设施网络系统,如电力网络、通信网络、Internet、航空网络以及物流网络等等。这些基础设施网络在为人类生活带来便利的同时也埋下了安全隐患,如交通网络的拥堵、大面积的停电事故等等。现实世界中的这些网络大都可以抽象成复杂网络,复杂网络为研究现实网络系统提供了一种新的途径。通过对基础设施系统灾难性事件的分析发现,重要节点以及级联失效现象对基础设施系统功能的影响非常大,因此,本文从网络节点重要性识别和级联失效两个方面对复杂网络进行研究,旨在减少基础设施系统中灾难性事件的发生避免不必要的经济损失。虽然现有的相关研究已经取得了一些理论成果,但仍存在很多问题有待进一步研究。复杂网络中节点的重要性排序一直是很多学者所关注的研究热点,现有的基于全局信息的方法,如介数中心性,能够较为有效地判断节点的重要性,但计算复杂度高;基于局域信息的方法,虽然降低了计算复杂度,但排序精度有待进一步提高。另外,目前关于复杂网络级联失效模型的研究也很多,但很多模型没有考虑网络负载的时变特性,负载重分配的不合理性很可能扩大网络级联失效的规模。鉴于此,本文从网络拓扑结构入手,基于网络的局域信息,考虑节点和边的相互影响提出了一种新的节点重要性排序方法,同时研究了时变负载对网络级联失效的影响,并提出了一种新的级联失效模型,减小负载时变网络级联失效的规模。另外,考虑人为干预对网络级联失效的影响,研究了过载节点崩溃概率对网络级联失效的影响,并提出了相应的保护资源分配策略,又考虑现实网络间的相互依赖关系,研究了耦合作用下网络级联失效的影响因素。具体工作如下:(1)考虑网络中节点和边的相互依存相互影响,提出了一种基于边重要性的节点重要性排序方法。该方法首先根据边的端节点的属性提出边的重要性计算方法,然后根据端节点对该边重要性的贡献率确定该边的重要性对端节点重要性的影响力,最后根据节点的连边数量和各连边对节点重要性的贡献值来判断节点的重要性。以节点移除后网络效率的下降率为评价指标兼顾方法的计算复杂度来综合评价节点重要性排序方法的优劣。(2)考虑网络负载的时变特性,基于节点的实时剩余容量,提出一种时变负载重分策略,并以此策略构建新的级联失效模型。以节点移除后导致的失效节点的比例的归一化指标作为网络抵御级联失效能力的评价指标,并通过算例分析、数值模拟和实例仿真研究了负载重分策略对网络抵御级联失效能力的影响。相比已有的基于固定负载重分策略的级联失效模型,新模型能够根据失效节点的邻节点的实时负载处理能力来对失效节点的负载进行重新分配,具有极强的抗干扰能力。在网络负载时变的情况下,新模型能够有效提高网络抵御级联失效的能力。(3)不同于现有的大多数研究,本文考虑过载节点由于保护机制的存在可能不会立刻失效的情况,基于现有研究提出了一种改进的带有崩溃概率的级联失效模型。同样地,以节点移除后导致的失效节点的比例的归一化指标作为网络抵御级联失效的能力的评价指标,通过算例分析、数值模拟和实例仿真研究了模型中的参数对网络级联失效规模的影响,并提出了相应的保护资源分配策略,为网络中保护机制的建立和保护资源的分配提供了依据。(4)考虑网络的负载特性,基于两种失效模式对不同条件下网络间耦合作用对网络抵御级联失效能力的影响进行研究,旨在找到能有效降低相依网络级联失效规模的途径和策略。数值模拟和实例分析结果显示,相似耦合比随机耦合更有利于降低耦合作用对网络抵御级联失效能力的影响,网络的容量阈值是影响相依网络级联失效规模的关键因素,直接决定其他因素对网络抵御级联失效能力的影响程度。另外,相比降序解耦,按照耦合节点度从小到大的升序解耦更有利于降低耦合作用对网络抵御级联失效能力的影响从而减少网络失效节点的规模。
[Abstract]:At the end of 1990s, with the small world network and scale-free network model was proposed, the study of complex networks has entered a new stage, more and more people begin to pay attention to complex networks. As an important branch of complexity science, complex network theory have developed rapidly, and has penetrated into the Mathematical Sciences, life science and engineering and other fields. With the rise and development of the Internet of things, the wisdom of the city to speed up the process, various network systems have emerged and got rapid development, human social life has been increasingly dependent on the network infrastructure system, such as power network, communication network, Internet network, aviation and logistics network and so on. These the infrastructure network brings to human life convenience also buried a security risk, such as traffic congestion, large area blackout etc. In the real world. Most of these networks can be abstracted into a complex network, complex network provides a new way for the study of the real network system. Through the analysis of the disaster infrastructure system events, important nodes and cascading failure phenomena influence the infrastructure system function is very large, therefore, this article from the network node the importance of identifying and cascading failures in two aspects of research on complex networks, to reduce the catastrophic events in the infrastructure system to avoid unnecessary economic losses. Although the existing research has made some achievements, but there are still many problems need to be further studied. The importance of nodes in complex networks has been a hot research topic ranking many scholars have paid close attention to the existing method based on global information, such as betweenness centrality, can effectively determine the node weight To, but high computational complexity; method based on local information, while reducing the computational complexity, but the sorting accuracy needs to be improved. In addition, the current research on complex network model of cascading failure are many, but many models do not consider the network load time-varying, unreasonable load redistribution is likely to expand the scale of cascading failure. In view of this, this article from the network topology of network based on local information, consider the interaction of nodes and edges presents a new node importance ranking method, and research the influence of time-varying load on the failure of cascade network, and proposes a new cascading failure model of cascading failure load decreases in size. In addition, consider the impact of human intervention on the failure of network cascade, studied the effect of overload node breakdown probability for cascading failure, and The protection of resource allocation strategies, and consider the relationship between the network reality, studies the factors that influence the coupling effects of cascading failure. The specific work is as follows: (1) considering the nodes and edges in the network depend on each other, this paper presents a ranking method based on the importance of edge node importance are calculated. First this method according to the attribute importance end node edge of the edge, and then according to the end node contribution to the edge of the importance of determining the importance of the edge rate of end node importance influence, according to the contribution to the importance of nodes and the number of edges with node boundary value to determine the importance of nodes to decrease node. After removing the network efficiency is one of the indicators for the evaluation of both the calculation method of quality comprehensive evaluation of node importance ranking method complexity. (2) considering the time-varying characteristics of the load of the network Real time, the residual capacity of nodes based on a time-varying load redistribution strategy, and the strategy of constructing the new model of cascading failure. The evaluation index to remove nodes leads to the normalized index as the proportion of the failure node network against cascading failure ability, and through the example analysis, numerical simulation and Simulation Study on the effect of load redistribution strategy on network against cascading failure ability. Compared with the existing fixed load redistribution cascade strategy based on failure model, the new model can according to the failure node node real-time load processing capacity to redistribute the load failure node, has strong anti-interference ability in the network. When the load change, the new model can effectively improve the ability to resist the network cascading failure. (3) different from most of the existing research, this paper considers the overload protection mechanism for node The problems may not immediately failure, the existing research puts forward a kind of improved with the breakdown probability of cascading failure model based on. Similarly, the evaluation to remove nodes leads to the normalized index proportion of failure nodes as the network ability to resist cascading failure, through the example analysis, numerical simulation and simulation research the parameters of the model scale effect on cascading failure, and puts forward some corresponding resource allocation strategy, provide the basis for the allocation of protection mechanism of the establishment and protection of resources in the network. (4) considering the load characteristics of the network, to study the effects of two kinds of failure modes under different conditions, the coupling between network resist cascade to network failure based on ability, in order to find can effectively reduce the dependence of cascading failure path and strategy scale. Numerical simulation and example analysis results show A similar effect, reduce the coupling effect on the network against cascading failures than random coupling coupling ability is more conducive to the threshold of the network capacity is a key factor affecting the scale dependence of cascading failure, directly determines the influence of other factors on the network against cascading failure ability. In addition, compared with the descending decoupling effect in ascending decoupling more coupling degree from small to large to reduce the coupling effect of the network against cascading failure ability so as to reduce the network node size.

【学位授予单位】：重庆大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【参考文献】