【作者】 刘媛妮；

【导师】 陈山枝；

【作者基本信息】 北京邮电大学 ， 计算机科学与技术， 2011， 博士

【摘要】 具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。自然界和社会中的系统复杂性可归因于一个个交织的网络的复杂性,通过这些复杂网络,系统的各个组成部分互相之间发生着各种显性的、非线性的作用。近年来,关于复杂网络的研究应运而生,它是刚刚兴起的一个研究方向,在对复杂网络的研究过程中,科学家们发现复杂网络的幂率分布特性,即复杂网络中节点的度值K相对于它的概率P(K)满足幂率关系,且幂指数多在大于2小于3的范围内。人们给具有这种性质的网络起了一个特别的名字：无标度网络。这里的无标度是指网络缺乏一个特征度值(或平均度值),即节点度值的波动范围相当大。复杂网络的幂率特性使得在对网络进行攻击时,只需要破坏少数关键节点即可造成网络的全面瘫痪,即对故意攻击表现出很强的脆弱性；而另一方面,复杂网络对于网络中出现的随机攻击具有很强的鲁棒性,这就是复杂网络的“鲁棒又脆弱”的特性。因此,越来越多的科研机构都把复杂网络抗毁性问题作为一个关注的热点问题进行研究。目前对于复杂网络抗毁性还有以下几方面的问题亟待解决：1)对网络呈现的拓扑特性本质的认识尚不够深入：对网络的抗毁性进行研究必须对网络的拓扑特性有深入的了解,即了解网络幂率特性的成因,从网络发展的内部规律来解决复杂网络中存在的问题。2)网络抗毁性的优化方法限于图论及数学的方法,不能从网络发展的内部规律进行研究,忽略了抗毁性作为影响网络成因的作用。3)针对网络中现有的级联失效现象建立的失效模型,不能从节点本身的属性去考虑；4)现有的网络抗毁性评估标准过于复杂,缺乏一种简单有效的抗毁性评估技术。本文围绕上述问题,开展了以下研究：1)对高优化权衡/容忍—HOT (Highly Optimized Tolerance/Tradeoff)理论进行研究,并从系统优化发展的角度研究了复杂网络中幂率特性的成因。幂率特性是复杂网络的普遍现象,对于其成因也有很多种解释,本文通过一个简单的森林防火模型阐述了HOT理论在系统优化过程中如何得到具有幂率分布特性的输出,并对HOT理论在系统优化以及建立网络模型等方面的应用进行总结。2)提出了一种基于HOT理论的网络抗毁性动态演化模型：HOT理论关于复杂系统方面研究的一个热点是系统的鲁棒性与脆弱性之间的关系,系统必须要对其所在的环境中面临的不确定因素有较强的鲁棒性,然而系统的复杂性又使得这种鲁棒性对外界的不确定因素具有一定的选择性。本文利用HOT理论,综合考虑网络中节点的演化过程,研究网络中影响节点加入网络中的一系列因素,并将抗毁性作为新结点加入网络过程中的一个衡量标准,最终建立了具有抗毁性的网络动态演化模型。理论分析表明建立的模型在拓扑特性上与现实的Internet相一致,另外仿真分析表明建立的模型能够有效的抵御网络中的攻击。3)提出了一种基于节点重要性的层次分析法--AHP(Analytic Hierarchy Process)网络级联失效模型：针对网络中出现的级联失效现象,提出了一种基于节点重要性的AHP网络级联失效模型。其中,节点的重要性IMP由节点的度K,节点的最短路径数S,以及节点邻居的最短路径数Ne三个因素决定,各种因素在决定节点重要性时所占的比例使用AHP层次分析法计算得出。仿真分析了ER和BA网络在这种级联失效模型下受到不同类型攻击的网络效率变化情况,证明了这种模型的有效性；另外仿真分析还研究了当各种因素所占比例变化时网络在受到攻击后效率的变化情况,最终表明该模型能够降低网络在受到攻击时网络效率的下降幅度。4)提出了一种基于节点重要性熵的网络抗毁性评估技术：网络的无标度特性实际上是一种非同质特性,无标度网络中大部分节点节点都只有很少量的连接,而少量节点却拥有很高的度,这种节点度不均匀分布的特性导致了网络难以有效的抵抗网络中的故意攻击,能够在一定程度上反映网络的抗毁能力。本文提出了一种基于节点重要性熵的网络抗毁性评估算法,其中节点的重要性由其介数决定,能够很好的衡量节点的重要性在网络中的变化情况。通过对不同规模下网络受到攻击后的熵的计算,可以验证这种方法能够有效的评估网络的抗毁能力。更多还原

【Abstract】 Network with some or all of the natures of self-organization, self-similarity, small world, scale-free is the complex network. The complexity of the nature and social can be attributed to the complexity of the network interwoven, through which, the various components of the system turn to be various dominant, nonlinear effect between them. In recent years, the reaearch on complex networks came into being, which is just the rise of a new direction. In the course of the study of complex networks, scientists have found that the degree of complex network follows the power law distribution, that is, the node degree K with respect to its probability P(K) meet the power law relationship, and the power exponent ranges from 2 to 3. Network with such properties has a special name:scale-free network. Here the scale-free means the network lakes a feature value (or an average value of degree), that is, the node degree range value flucted considerablely.The pawer law properties of complex network makes it is fragile to the deliberate attacks, that is when attack only a few key nodes can cause the network parlay, while it is very robust to the random attacks. The complex network has the properties of’Robust-yet-Fragile’, therefore, more and more research institution focus their attention on the network invulnerability.At present, many issues of the research on network invulnerability need to be investigated immediately, such as follows:1) there is no deeply understanding of the nature characteristics of the network topology:it needs to have a deeply understanding to study the problem of the complex network invulnerability. Learn the main cause of the pawer law and solve the problem in the complex network by the way of learning the development of the internal law of network.2) The present optimization of network invulnerability limited in the Picture Theory and the Mathematical, which can not seize the internal development laws of the network, which ignores the impact of the network invulnerability as the cause of the network.3) The present cascading models do not consider the attributes of the nodes.4) The existing network invulnerability evaluation criteria are too complex, lacking a simple and effective assessment of invulnerability technology.This thesis focuses on the issuses above and carries out the follows research:1) Researched the HOT(Highly Optimized Tolerance/Tradeoff) theory and the cause of the pawer law from the perspective of system optimization. Pawer law is a common phenomenon in complex networks, and there are many theories to explain its cause. This thesis explained how to get a power law distribution output by HOT optimization process through a simple model of fire forest, and summarized the applications of HOT thery on system optimization and modeling of the network.2) Porposed the invulnerable dynamic evoluation model of network based on HOT theory. A key aspect of complex systems that has been a main theme of HOT is the relationship between robustness and fragility. System should be robust to uncertainties in their environment, while the ensuing complexity makes these systems robust to the uncertainties for which such complexity was selected. This thesis solved the problem of building the invulnerable dynamic evolution model of the network as a HOT problem, and through the nodes preference attachment scheme, the invulnerability and self-recovery capabilities etc. of the system could evolve toward the optimal direction. Theoretical analysis shows that the node can adjust its properties to generate the invulnerable dynamic evolution model with power law distribution of node degree; simulation analysis indicates that the HOT model has a better invulnerability than that of BA model.3) Proposed a model for cascading network failures based on the nodes with different tolerance parameter. We proposed a simple model for cascading failures in the network to explore how the failures can have a great impact on the network performance, and allocated every node a Ci by the tolerance parameterαbased on the node importance IMP, and the IMP is determined by the node degree K, the number of the shortest paths S through a node, and the number of the shortest paths Ne through the neighbors of a node, then we fix every element a weight to compute the IMP by the AHP (Analytic Hierarchy Process) theory. Based on the model, we analyzed the influence of different types of attacks to the network performance, and also tabled some proposals for reducing the damage the networks suffered from the cascading failures.4) Proposed a network invulnerability assessment techniques based on the network entropy of node importance. The network scale-free characteristic is actually a non-homogeneous, which is, most of the nodes have a small number of connections while few of the nodes have a large number of connections. The uneven distribution of the node degree lead the network can not effectively resistant the deliberately attacks, which can reflect the ability of the network invulnerability in a certain extent. This thesis proposed a network invulnerability assessment techniques based on the network entropy of node importance, in which the node importance is consist of the constant and variable part, which can measure the node importance when the network changes. By comparing the network entropy after the attack with its initial entropy, this method can assess the network invulnerability effectively.更多还原