复杂网络中节点重要度评估算法的研究

发布时间：2018-03-13 23:05

本文选题：复杂网络　切入点：识别重要节点　出处：《西南大学》2015年硕士论文　论文类型：学位论文

【摘要】：近年来,复杂网络系统已经融入到人们生产生活的方方面面。作为一个新兴且活跃的科学研究领域,复杂网络早已引入到在现实世界网络的实证研究。目前,在计算机科学、社会科学、生物科学、管理科学等众多领域得到了越来越多的人的重视。一方面,伴随着复杂网络的不断发展,人类的生产生活质量有了大幅度的提高和升华,并且为之带来了极大的便利。但是另一方面,复杂网络系统的运行也对人类的生产生活带来了一定的负面冲击,比如疾病的快速传播、大面积的停电事故、以及交通运输的瘫痪等等。因此,我们需要对各种复杂网络系统有着更为深刻的认识和分析,以便对可能造成的负面影响进行预测、避免、控制等等。在众多复杂网络研究方向中,节点重要度评估已经成为其研究发展中一个较为深远的方向。虽然目前已经许多的中心性方法被提出来度量节点的重要度,但不同的中心性在各个方面或多或少都存在着一定的不足和局限性。由于不同的中心性的机制不同,而且有着不同的不足,因此,当对同一个网络使用不同的中心性进行节点重要度评估时,往往会得到不同的结果。为此,我们有必要对现有的中心性进行改进,从而能全面有效的对复杂网络节点重要度进行评估。本文主要提出了三种不同的中心性算法对节点进行重要度评估。首先将有效距离引入节点最短路径的应用中,用其代替传统的测地线和地理距离来衡量网络节点的距离,并利用改进后接近中心性对节点进行重要度评估。然后提出了一种基于TOPSIS算法的多属性决策模型的中心性算法,该算法将多个中心性作为多属性进行融合来评估节点重要度。最后,我们基于失效模式及影响分析模型,将复杂网络的节点信息进行建模来刻画发生频度、严重程度、检测难易程度,并通过风险顺序数来对节点进行重要度评估。为了体现出本文提出的算法的有效性和实用性,我们都将这些算法应用到真实的网络中进行对比实验。本文的工作主要包括以下几个方面：(1)提出基于有效距离的接近中心性算法在真实的网络中,往往会有孤立节点和单向边,这会导致部分节点对的距离是无穷大,在此情况下则利用传统接近中心性来评估节点重要度是无效的。针对此问题,我们引入有效距离,来代替传统的测地线和地理距离来度量网络节点的距离。该模型不但解决了传统接近中心性失效的问题,还能广泛应用于加权网络中,而且更加合理的表示了网络节点信息流的传输过程。(2)提出基于TOPSIS模型的中心性算法TOPSIS算法是一种被广泛应用的多属性决策算法,它能有效地融合多个有差异的属性,并得出一组接近理想最优解的排序。由于各种中心性算法都存在着种种缺点,并且不同中心性会产生不同的评估结果,因此我们认为有必要提出一种折衷的算法来融合这些差异以及克服单一中心性所存在的缺点。我们将度中心性、接近中心性和介数中心性这三个最为基础的中心性作为多个属性引入到TOPSIS多属性决策模型中,将融合后的中心性作为网络节点的重要度评估算法。该算法不仅解决了这三个中心性各自存在的缺陷,还有效地将它们的差异进行折衷融合。并且首次将工程评估中的TOPSIS算法引入到复杂网络系统中,对跨学科领域研究有着积极的影响。(3)提出基于失效模式及影响分析模型的中心性算法失效模式及影响分析是一种可靠性设计的重要方法,它通过由发生频度、严重程度、检测难易程度得出的风险顺序数来对模式进行评估。我们利用网络的结构和节点的信息进行建模来刻画发生频度、严重程度、检测难易程度。我们认为如果一个节点的入度越大,则表明其他节点发生故障时影响到该节点的机会就越大,那么这个节点发生“失效”的概率就越高。同时,倘若一个节点到其他所有节点的有效距离越短,则表明该节点失效后影响的传播就越广,那么这个节点失效的严重程度就越大。在此模型中,我们定义了网络节点的熵的概念。因为信息熵表示的是系统或者个体的不确定性,因此我们认为如果一个节点的熵值越大,则这个节点在网络中所处的结构也就越复杂,那么对这个节点进行失效探测的难易程度也就越难。最后,我们根据新的模型得出的风险顺序数对节点进行重要度评估。风险顺序数值越大,则节点越重要。
[Abstract]:In recent years, the complex network system has been integrated into people's lives. As a new and active field of scientific research, has been introduced into the empirical research of complex networks in the real world network. At present, in computer science, social science, biological science, management science and other fields has been more and more people attention. On the one hand, with the development of complex network, the production of human life quality has been greatly improved and sublimation, and brings great convenience to them. But on the other hand, the complex network system for the production of human life has brought certain negative impact, such as the rapid spread of the disease the large area blackout, and paralyzed transportation etc.. Therefore, we need to have a more profound understanding and analysis of the complex network system, so as to possible The negative effects of prediction, avoid, control and so on. In many directions in the study of complex networks, node importance evaluation has become a more profound direction of its research and development. Although the central approach has been proposed to measure many important node, but not the same center in all aspects are more or less shortcomings and limitations. Because of the different mechanism, but also have different problems, therefore, when the center of different use on the same network node importance evaluation, tend to get different results. Therefore, it is necessary for us to improve the existing center thus, comprehensive and effective on the node importance evaluation. This paper presents three different centrality algorithm on node importance evaluation. The effective distance of nodes is introduced The application of the shortest path, to replace the traditional wire and geographic distance measurement to measure the distance of network nodes, and using the improved close centrality of node importance evaluation. Then put forward a central algorithm of multi attribute decision making model based on TOPSIS algorithm, this algorithm will be more as the center multi attribute fusion to evaluate the node importance. Finally, we model the failure mode and effect analysis based on the node information of complex network model to describe the frequency, severity, detection of the degree of difficulty, and the number of order through risk assessment on the node. In order to demonstrate the validity and practicality of the proposed in the algorithm, we will apply these algorithms to real network experiments. The main work of this paper includes the following aspects: (1) proposed to effectively based on distance The center of algorithm in real network, often isolated nodes and one side, this will cause the distance on the part of the node is infinite, in this case is close to the center of the traditional evaluation of node importance is invalid. To solve this problem, we introduce the effective distance, to replace the ground and geographic distance measurement the traditional network node to measure the distance. This model not only solves the problem of the traditional center close to failure, but also widely used in the weighted network, and more reasonable representation of the transmission process of the network node information flow. (2) the center of TOPSIS algorithm based on TOPSIS model is a widely used the algorithm of multi attribute decision making, it can effectively combine multiple different attributes, and draw a set close to the ideal optimal solution sorting algorithm. Due to the variety of center there are many shortcomings, and in different The mind will produce different results, so we think it is necessary to put forward a compromise algorithm to fuse these differences and overcome the shortcomings of a single center. We will degree centrality, closeness centrality and betweenness centrality of the three most basic center for multiple attribute into TOPSIS multi attribute decision making model, the center of fusion as an important evaluation algorithm of network nodes. The algorithm not only solves the defects of the three centers of their existence, but also effectively will compromise their differences and fusion. For the first time in the TOPSIS project evaluation algorithm is introduced to the complex network system, a a positive impact on the interdisciplinary field. (3) put forward the algorithm analysis model of failure mode and effect of failure mode and effect analysis is an important method of reliability design based on it through The frequency of occurrence, severity, detection of the degree of difficulty that the risk assessment of the number of sequential patterns. We use the structure and node of the network information modeling to describe the occurrence, severity, degree of difficulty detection. We think that if a node degree is bigger, that other node failures influence to the node of the greater the chance, then the node failure probability is higher. At the same time, if a node to all other nodes of the effective distance is shorter, indicates that the propagation effect after node failure is bigger, the severity of the node failure in this model is greater., we define the concept of network node entropy. Because information entropy represents the system or individual uncertainty, so we think that if a node of the greater entropy of the nodes in the network The more complex the structure is, the harder it is to detect the failure of the node. Finally, we evaluate the importance of the node according to the number of risk sequence obtained by the new model. The greater the risk order value is, the more important the node is.

【学位授予单位】：西南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】