大图上跳数受限的可达查询算法研究与优化  

Research and Optimization of Reachability Query Algorithm with Limited Hop on Big Graph

作　　者：邢耕源 徐云[2] XING Geng-Yuan;XU Yun(School of Data Science,University of Science and Technology of China,Hefei 230026,China;Key Laboratory of High Performance Computing of Anhui Province,Hefei 230026,China)

机构地区：[1]中国科学技术大学大数据学院,合肥230026 [2]安徽省高性能计算重点实验室,合肥230026

出　　处：《计算机系统应用》2021年第10期164-170,共7页Computer Systems & Applications

基　　金：国家自然科学基金面上项目(61672480)。

摘　　要：判断有向图上两个顶点之间是否存在一条路径是一个经典问题,而对于一些路由规划和图分析等实际应用,要求查找是否存在跳数受限的可达路径,这是一个变种的图可达查询问题.对于大图上跳数受限的查询算法,不仅仅要对大图查询的时间效率和空间效率进行权衡,而且还要利用跳数受限的特性进行优化.普通的可达查询算法存在小度数顶点索引项占用空间过多的问题,造成空间浪费严重.为此我们提出了一种面向跳数受限的2-hop部分索引方法,采用改进的索引方法并结合局部搜索,实现跳数受限的有效可达性查询.实验结果表明,在Orkut社交网络数据集上与已有算法相比,该算法索引空间节省了32%,同时查询时间略微增加,使得我们算法可以计算更大规模图的跳数受限可达问题.It is a classic problem to judge whether there is a path between two vertices in a directed graph. For some practical applications such as routing and graph analysis, it is required to find whether there is a reachable path with limited hops, which is a variant of reachability query in graphs. For the query algorithm with limited hops on a large graph, it is necessary to balance the time and space efficiency of large-graph query and optimize the algorithm with the characteristics of limited hops. The common reachability query algorithm takes up too much space for small-degree vertex index entries, which leads to serious space waste. Therefore, we propose a hop-limited 2-hop partial index method, which combines an improved index method with local search to achieve hop-limited effective reachability query. The experimental results show that, compared with the existing algorithms, the proposed algorithm can save 32% index space and slightly increase query time on the Orkut social network dataset. Thus, the proposed algorithm can calculate the hoplimited reachability problem of larger graphs.

关 键 词：图论算法 可达性查询 索引优化 网络流优化 

分 类 号：O157.5[理学—数学]