大规模复杂网络近似最短路径算法研究

发布时间：2018-04-29 07:10

本文选题：最短路径问题 + 近似算法　；参考：《辽宁大学》2017年硕士论文

【摘要】：最短路径算法作为图论研究和算法设计中的经典问题之一,旨在寻找图中两个节点之间的最短路径,已经在现实生活中的诸多领域得到了广泛的应用,例如应用在社会网络、交通地理信息系统、路径规划、生物医学、生物信息网络及军事综合运输等。最短路径算法不仅是计算机科学技术领域研究的热点问题,也得到了其他各个领域研究人员的密切关注。随着近些年大数据时代的到来,数据规模不断增加,数据的拓扑结构也愈来愈复杂,目前的最短路径算法已经无法满足日益增长的数据规模和查询速度的需求,因此需要设计一个更加快速有效的最短路径算法。本文深入研究了现有的最短路径算法,发现无论是精确的最短路经算法还是目前热门研究的近似最短路径算法,都已经无法满足数据量不断增长、结构越来越复杂的大规模网络图,针对复杂网络具有的小世界模型特征和无标度的特点,目前最短路径算法的研究方向一般都从两阶段查询法入手,第一阶段对数据进行预处理工作,建立标签索引信息,第二阶段利用预处理数据的结果对目标问题进行在线搜索。因此,如何均衡预处理代价、在线查询速度和查询结果的精确度这三者之间的关系,将是两阶段查询法的关键问题,也是本文研究的主要内容和方向。本文针对现实生活中复杂网络结构的拓扑特性,提出一种适用于大规模复杂网络图的近似最短路径算法,基于区域枢纽点建立快速干道的近似最短路径算法(Hub Vertex of area and Core Expressway,HEA-CE)。该算法首先计算节点的度和平衡值,在图中选取少量的区域枢纽点,利用区域枢纽点将复杂网络分割成一定数量的子图区域,其中在每个子图区域中,度最大的区域枢纽点称为该子图的区域核心点。利用区域枢纽点为每个子图区域内部构建Core Expressway快速干道图,用区域核心点为子图区域间建立Freeway高速公路图。根据预处理工作得到的区域枢纽点、区域枢纽点、Core Expressway快速干道图和Freeway高速公路图,本文提出了近似最短路径的查询算法,并给出了相应的查询策略。根据以上数据预处理的结果,及节点所在子图区域的不同,通过区域枢纽点间、区域核心点间、区域枢纽点和区域核心点之间的最短路径来近似计算大规模复杂网络中两个节点之间的最短路径,能够有效的减少搜索空间,提高了在线查询效率。最后,通过和其他三种近似最短路径算法的实验结果进行对比分析,证明本文提出的近似最短路径算法在大规模复杂网络分析中能够良好的降低算法的复杂性,提高了在线查询效率,并且具有较高的精准度,验证了本文算法的有效性。
[Abstract]:As one of the classical problems in graph theory research and algorithm design, the shortest path algorithm is aimed at finding the shortest path between two nodes in the graph. It has been widely used in many fields in real life, such as social network. Transportation geographic information system, path planning, biomedicine, biological information network and military integrated transportation. The shortest path algorithm is not only a hot topic in the field of computer science and technology, but also received close attention by researchers in other fields. With the arrival of big data era in recent years, the scale of data is increasing, and the topology of data is becoming more and more complex. The shortest path algorithm can not meet the increasing demand of data scale and query speed. Therefore, it is necessary to design a faster and more effective shortest path algorithm. In this paper, the existing shortest path algorithm is deeply studied, and it is found that neither the accurate shortest path algorithm nor the most popular approximate shortest path algorithm can meet the increasing amount of data. In view of the small world model and scale-free characteristic of complex network, the research direction of shortest path algorithm generally starts with two-stage query method. In the first stage, the data is preprocessed and the label index information is established. In the second stage, the target problem is searched online using the results of the preprocessing data. Therefore, how to balance the cost of preprocessing, the speed of online query and the accuracy of query results will be the key problem of two-stage query, and the main content and direction of this paper. In view of the topological characteristics of complex network structure in real life, this paper presents an approximate shortest path algorithm suitable for large-scale complex network graphs. The approximate shortest path algorithm based on regional hub points to establish fast trunk roads is Hub Vertex of area and Core express approach to HEA-CEE. The algorithm first calculates the degree and balance of nodes, selects a small number of regional hub points in the graph, and divides the complex network into a certain number of subgraph regions by using the regional hub points. The maximum degree of regional hub point is called the regional core of the subgraph. The Core Expressway fast trunk road map is constructed by using the regional hub point as the interior of each sub-map area, and the Freeway expressway map is built by using the regional core point as the sub-map area. According to the regional hub point, the regional hub point Expressway fast trunk road map and the Freeway highway map, this paper puts forward the query algorithm of approximate shortest path, and gives the corresponding query strategy. According to the results of the data preprocessing above, and the different regions of the sub-graph where the nodes are located, through the regional hub points, between the regional core points, The shortest path between the regional hub point and the regional core point to approximate calculate the shortest path between the two nodes in the large-scale complex network can effectively reduce the search space and improve the efficiency of online query. Finally, by comparing the experimental results with other three approximate shortest path algorithms, it is proved that the proposed approximate shortest path algorithm can reduce the complexity of the algorithm well in the large-scale complex network analysis. The efficiency of online query is improved, and the accuracy is high. The validity of this algorithm is verified.
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】