复杂网络中节点重要性排序的研究

《复杂网络中节点重要性排序的研究》由会员分享，可在线阅读，更多相关《复杂网络中节点重要性排序的研究（59页珍藏版）》请在金锄头文库上搜索。

1、 摘 要 现实生活中很多错综复杂的关系都可以转化为复杂网络的模型，通过对复杂网络的研究，可以发掘实际网络中存在的特点及规律，从而为现实生活中的众多领域服务。而研究复杂网络的重要任务之一就是对节点重要性进行排序，因为网络中各节点之间存在一定的差异性，所以如何有效的评估节点在网络中的重要性是研究复杂网络亟待解决的问题。本文在对节点重要性排序算法上主要做了以下二项工作： 1. 根据传统的网络节点测度定义了新的节点重要性测度，并提出了一种复杂度为O( + )的基于排除思想的剥落排序算法，对网络中的节点按重要性测度进行排序。最后通过实验验证，该算法不仅能克服度排序、接近度排序及介数排序算法的缺陷，还能在

2、较短的时间内找出网络中的重要节点； 2. 提出了一个稳定的权重函数及稳定的接近度排序算法。分析了接近度排序算法存在的不足之处，在此基础上改进了接近度排序算法，为接近度排序算法设计了一个权重函数，以此来增加不同距离节点对所求节点重要性影响的差异，实验结果表明，权重函数的不同，所得节点重要性排序结果也不相同，从而满足了科研人员多样性的研究目的需求。最后提出了一个稳定的权重函数及稳定的接近度排序算法，在稳定状态下，即使再增大不同距离节点对所求节点重要性的影响的差异，也不会影响最后节点的排序。通过对实际例子的分析证明了该带稳定权重函数的接近度排序算法的稳定性及有效性。 关键词：复杂网络 节点重要性 剥

3、落排序算法 接近度 权重 Abstract Many complicated relationship in real life can be modeled by complex networks. We can discover the characteristics and regulations of the existing networks through the research on complex networks. One of the most important tasks for complex networks is to evaluate the importan

4、ce of nodes. As different nodes have different characteristics, it is of high practical values to evaluate the performance of different nodes. The main contributions of this thesis are summarized as follows: 1. A peeling off sorting algorithm based on elimination technique is proposed. We first peel

5、 off the least important nodes until all of the nodes are peeled off, then we reverse the order and get the final order of all the nodes. The simulation results show that the proposed algorithm can address the limitations of the existing sorting algorithms, e.g., degree sorting and closeness sorting

6、 algorithms. The results also show that our algorithm is more effective than the compared ones. 2. We analyzed the limitations of the closeness sorting algorithm, and then based on this analysis, an improved closeness sorting algorithm is proposed. In this method, we design a weight function for clo

7、seness sorting. The results indicate that with different weight functions, different nodes importance sequences are obtained. Finally, a stable weight function and a stable closeness sorting algorithm are proposed. The main idea is that the final sequence of nodes is unchanged even if we enlarge the

8、 differences among nodes. The experimental results show that the closeness sorting algorithm with weight function is effective. Key Words: Complex Networks Nodes Importance Peeling Off Sorting Algorithm Closeness Weight Function 目录 第一章 绪论 . 1 1.1 引言 . 1 1.2 复杂网络的研究背景 . 1 1.3 复杂网络的研究意义 . 3 1.4 本文章节及内

9、容安排 . 4 第二章 复杂网络的基本理论及模型的演化 . 7 2.1 引言 . 7 2.2 复杂网络中的基本概念 . 7 2.3 复杂网络的模型概述 . 10 2.3.1 规则网络. 10 2.3.2 随机网络. 11 2.3.3 小世界网络 . 12 2.3.4 无标度网络 . 14 2.4 本章小结 . 16 第三章 基于排除思想的剥落排序算法 . 19 3.1 经典的节点重要性排序算法 . 19 3.1.1 度排序算法 . 19 3.1.2 接近度排序算法 . 20 3.1.3 介数排序算法 . 21 3.2 三种经典的重要性排序算法的对比 . 23 3.3 一种基于排除思想的剥落(Peeling off)排序算法 . 24 3.3.1 复杂网络模型 . 24 3.3.2 “剥落”(Peeling off)排序算法 . 26 3.3.3 算例 . 27 3.3.4 算法性能分析 . 28 3.4 实验结果与分析 .