论文部分内容阅读
最短路径算法作为图论研究和算法设计中的经典问题之一,旨在寻找图中两个节点之间的最短路径,已经在现实生活中的诸多领域得到了广泛的应用,例如应用在社会网络、交通地理信息系统、路径规划、生物医学、生物信息网络及军事综合运输等。最短路径算法不仅是计算机科学技术领域研究的热点问题,也得到了其他各个领域研究人员的密切关注。随着近些年大数据时代的到来,数据规模不断增加,数据的拓扑结构也愈来愈复杂,目前的最短路径算法已经无法满足日益增长的数据规模和查询速度的需求,因此需要设计一个更加快速有效的最短路径算法。本文深入研究了现有的最短路径算法,发现无论是精确的最短路经算法还是目前热门研究的近似最短路径算法,都已经无法满足数据量不断增长、结构越来越复杂的大规模网络图,针对复杂网络具有的小世界模型特征和无标度的特点,目前最短路径算法的研究方向一般都从两阶段查询法入手,第一阶段对数据进行预处理工作,建立标签索引信息,第二阶段利用预处理数据的结果对目标问题进行在线搜索。因此,如何均衡预处理代价、在线查询速度和查询结果的精确度这三者之间的关系,将是两阶段查询法的关键问题,也是本文研究的主要内容和方向。本文针对现实生活中复杂网络结构的拓扑特性,提出一种适用于大规模复杂网络图的近似最短路径算法,基于区域枢纽点建立快速干道的近似最短路径算法(Hub Vertex of area and Core Expressway,HEA-CE)。该算法首先计算节点的度和平衡值,在图中选取少量的区域枢纽点,利用区域枢纽点将复杂网络分割成一定数量的子图区域,其中在每个子图区域中,度最大的区域枢纽点称为该子图的区域核心点。利用区域枢纽点为每个子图区域内部构建Core Expressway快速干道图,用区域核心点为子图区域间建立Freeway高速公路图。根据预处理工作得到的区域枢纽点、区域枢纽点、Core Expressway快速干道图和Freeway高速公路图,本文提出了近似最短路径的查询算法,并给出了相应的查询策略。根据以上数据预处理的结果,及节点所在子图区域的不同,通过区域枢纽点间、区域核心点间、区域枢纽点和区域核心点之间的最短路径来近似计算大规模复杂网络中两个节点之间的最短路径,能够有效的减少搜索空间,提高了在线查询效率。最后,通过和其他三种近似最短路径算法的实验结果进行对比分析,证明本文提出的近似最短路径算法在大规模复杂网络分析中能够良好的降低算法的复杂性,提高了在线查询效率,并且具有较高的精准度,验证了本文算法的有效性。