基于k-core分区域的复杂网络最短路径近似算法研究

发布时间：2018-04-13 04:31

本文选题：复杂网络 + 最短路径　；参考：《辽宁大学》2017年硕士论文

【摘要】：最短路径计算一直以来是复杂网络中重要的研究内容,近年来,随着研究的日益深入,复杂网络中许多特征量的计算及问题的解决越来越多的依赖于最短路径的计算。经典算法无论是在算法复杂度还是在效率上都已不适用于计算具有大规模节点和连边的复杂网络,而目前一些常见近似计算算法也因其适用性受限、算法效率与准确率不理想等因素而不能满足复杂网络最短路径计算的应用需求,因此,近似算法要如何在计算延迟、内存占用率和准确性之间做到最好的平衡及其如何增强网络适用性已经成为算法研究者们追逐的重要目标。本文在相关算法研究的基础上,提出了基于k-core分区域的最短路径近似算法。算法在真实的大规模社会网络、Web社交平台网络及互联网络中保持了较高的计算效率和准确率。算法首先基于k-core将网络水平划分成若干个k-shell子网络,然后根据节点k-shell值将包含不同节点重要性的k-shell子网络划分为高层、边缘层和中间层三个区域,最后在计算最短路径时,对于高层区域,由于节点规模较小且连边比较密集,故精确计算其所有节点对的最短路径;对于边缘层区域,节点度比较小,依据k-shell作为节点重要性,每次搜索只搜索k-shell值大于等于当前节点的邻居节点,达到限制节点搜索区域的目的;对于中间层区域,由于所包含k-shell子图之间的连边密集,故对k-shell子网内部节点进行超点聚合,搜索时只利用超点的中心节点与其它区域节点的连边关系已达到提高搜索效率的目的,其搜索过程同边缘层区域。算法使用k-core作为网络划分及搜索目标引导依据更具一般性,利用超点聚合处理k-shell子网大幅降低了路径搜索中遍历节点的规模,并且合理使用预处理、双向搜索树和优先队列技术对路径搜索过程进行优化和加速,大大提高了算法的计算效率和准确率。本文使用现实中不同规模大小的网络数据集,对所述算法进行了实验和分析,实验数据表明算法在网络适用性、计算效率和准确率上明显优于CDZ算法。例如,在com-DBLP社区网络中(规模为约30万节点、100万连边的无向图),节点对最短路径的平均计算时间只需几十毫秒,正确率能够达到99%;在不同幂律指数的无标度网络仿真模型中,算法也表现出了非常好的适用性和效率。
[Abstract]:The calculation of the shortest path has always been an important research content in the complex network. In recent years, with the deepening of the research, the calculation of many characteristic variables and the solution of the problem in the complex network are more and more dependent on the calculation of the shortest path.The classical algorithms are no longer suitable for the computation of complex networks with large nodes and connected edges in terms of complexity and efficiency. However, some common approximate algorithms are limited by their applicability.The efficiency and accuracy of the algorithm are not ideal and can not meet the needs of the application of the shortest path calculation in complex networks. Therefore, how to calculate the delay of the approximate algorithm,How to achieve the best balance between memory occupancy and accuracy and how to enhance the applicability of the network has become an important goal pursued by algorithmic researchers.In this paper, the shortest path approximation algorithm based on k-core sub-region is proposed based on the research of relevant algorithms.The algorithm maintains high computational efficiency and accuracy in real large-scale social networks such as Web social platform networks and Internet networks.The algorithm first divides the network level into several k-shell subnetworks based on k-core, and then divides the k-shell subnetwork which contains different node importance into three regions: high layer, edge layer and middle layer according to the node k-shell value. Finally, when calculating the shortest path, the algorithm divides the k-shell subnetwork into three regions: the upper layer, the edge layer and the middle layer.For the high level region, because the node size is small and the connected edges are dense, the shortest path of all the node pairs is calculated accurately, and for the edge layer area, the node degree is relatively small, according to the importance of k-shell as the node,Each search only searches neighbor nodes whose k-shell value is greater than or equal to the current node, so as to limit the search area of the nodes. For the middle layer region, because of the dense edges between the included k-shell subgraphs, the nodes in the k-shell subnet are hyper-aggregated.The search efficiency can be improved by using only the connection between the center node of the superpoint and the nodes of other regions, and the search process is the same as that of the edge layer region.Using k-core as the basis of network partition and search target guidance is more general. Using hyper-point aggregation to deal with k-shell subnet greatly reduces the scale of traversal nodes in path search and uses preprocessing reasonably.The bidirectional search tree and priority queue technology optimize and accelerate the path search process, which greatly improves the computational efficiency and accuracy of the algorithm.In this paper, the experimental results show that the proposed algorithm is superior to the CDZ algorithm in network applicability, computational efficiency and accuracy using the network datasets of different sizes in reality.For example, in a com-DBLP community network (an undirected graph with about 300000 nodes in scale and 1 million connected edges), the average computing time for the shortest path is only several tens of milliseconds, and the accuracy can reach 99. In the scaleless network simulation model with different power law exponents, the mean computing time of the node is only several tens of milliseconds.The algorithm also shows very good applicability and efficiency.
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP301.6;O157.5

【参考文献】