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

判断有向图上两个顶点之间是否存在一条路径是一个经典问题,而对于一些路由规划和图分析等实际应用,要求查找是否存在跳数受限的可达路径,这是一个变种的图可达查询问题.对于大图上跳数受限的查询算法,不仅仅要对大图查询的时间效率和空间效率进行权衡,而且还要利用跳数受限的特性进行优化.普通的可达查询算法存在小度数顶点索引项占用空间过多的问题,造成空间浪费严重.为此我们提出了一种面向跳数受限的2-hop部分索引方法,采用改进的索引方法并结合局部搜索,实现跳数受限的有效可达性查询.实验结果表明,在Orkut社交网络数据集上与已有算法相比,该算法索引空间节省了32％,同时查询时间略微增加,使得我们算法可以计算更大规模图的跳数受限可达问题.

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

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 hop-limited reachability problem of larger graphs.