【作者】 冯立雪；

【导师】 于双元；

【作者基本信息】 北京交通大学 ， 计算机科学与技术， 2011， 硕士

【摘要】 复杂网络中的搜索问题涉及网络中指定文件或数据的寻找及网络节点间最短路径的确定,具有重要的现实意义和较高的研究价值。复杂网络搜索策略通常可用一个消息传递的过程来描述,多采用局部搜索方式,其性能将直接影响到能否快速有效地搜索到所需要的目标,以及找到目标所花费的代价能否被接受。实际的复杂网络中普遍同时存在多种拓扑特征,本文从兼顾无标度和小世界特性的角度出发,对局部搜索策略进行了深入的分析、研究和改进。本文研究了基本的复杂网络拓扑特征、拓扑模型和搜索策略,比较了各种复杂网络搜索策略的优劣,分析了最大度搜索策略的缺陷成因,指出存在一分界值,可使得对于该范围内的节点的搜索过程符合“按度序列搜索”的设想,保证最大度搜索策略的高效。基于分界值,本文提出了将复杂网络中的节点按其度的大小分为两部分的思想,对度小于分界值的那一部分节点采用最大度搜索策略,而对度不小于分界值的那一部分节点采用最小聚类系数搜索策略,并设计了结合最大度与最小聚类系数的复杂网络搜索策略。本文完成了对现有的实际复杂网络数据集的分析和处理工作,将包含着网络邻接矩阵的数据集转换成为了存储着网络全部节点的数组,并抽取和计算了节点的相关局部信息,之后实现了最大度搜索策略、最小聚类系数搜索策略、最大—最小度搜索策略及本文提出的结合最大度与最小聚类系数的复杂网络搜索策略的具体搜索过程。本文使用具有不同复杂网络拓扑特征的数据集,完成了相关的仿真测试工作,并依据平均搜索步数和平均搜索时间这两大有效性指标,比较、分析和评价了各个复杂网络搜索策略的搜索效果,验证了结合最大度与最小聚类系数的复杂网络搜索策略的正确性和有效性。更多还原

【Abstract】 Search problem in the complex network involved in finding the specified file or data and determining the shortest path between nodes, has important practical significance and research value. Complex network search strategy, adopted the local search methods, is described as a message transfer process. Its performance will directly affect the ability to search quickly and efficiently and the cost can be accepted. Real complex network generally has a variety of topological characteristics. This paper takes into account the scale-free and small world properties, conducted in-depth analysis, research and improvement of the local search strategies.In this paper, introduce the basic topological characteristics, topological models and search strategies in the complex network, and then compare them. Analyze the defect causes of high degree seeking. Point out that there is a dividing value, makes the search process conform to imagine of search by degree sequence, to ensure the efficient of high degree seeking. Based on it, propose that divide the complex network into two parts according to node degree. Adopt the maximum degree search strategy for the nodes that degree less than it, and adopt the minimum clustering coefficient search strategy for the nodes that degree not less than it. And then design the complex network search strategy combined with Max degree and Min clustering coefficient. In this paper, complete task that analyze and dispose the existing data sets about real complex network, convert a data set contained adjacency matrix into a array, extract and calculate the relevant local information of node, and then achieve the search process of the maximum degree search strategy, the minimum clustering coefficient search strategy, the maximum-minimum degree search strategy and the complex network search strategy combined with Max degree and Min clustering coefficient.This article completes the relevant simulation test, used certain data sets with the various complex network topological characteristics. According to the average search steps and the average search time, compare, analyze and evaluate search effect of these complex network search strategy. Verify the correctness and validity of the complex network search strategy combined with Max degree and Min clustering coefficient.更多还原