基于树分解的时序最短路径计数查询算法

Temporal shortest path counting query algorithm based on tree decomposition

最短路径计数是图计算中的一个重要研究问题,旨在查询顶点间的最短路径数,在路径规划与推荐、社交网络分析、介数中心性计算等领域中具有广泛应用。目前越来越多的网络可以建模为时序图,但少有针对时序图最短路径计数查询问题的研究工作。与静态图相比,时序图增加了时间信息,结构更复杂,在查询顶点间的路径数时必须考虑边的激活时间,因此静态图中最短路径计数方法不再适用于时序图,并且在大规模时序图上查询更具有挑战性。针对时序图最短路径计数问题,提出一种基于树分解构建TG-TL(Temporal Graph-Tree Label)索引的方法。该方法包含构建索引和在线查询两个阶段,构建索引阶段根据时序图的属性设计时序树分解算法,将时序图转化为树结构;然后根据树分解的结构信息以及凸路径定义提出高效构建索引算法;在线查询阶段基于TG-TL索引提出了高效的时序最短路径计数查询算法。在4个真实数据集上的实验结果表明,与基于TG-base(Temporal Graph-base)索引的查询算法相比,所提算法在查询效率上至少提升了61%,因此所提算法在时序图最短路径计数问题上具有高效性和有效性。

The shortest path counting is an important research problem in graph computing.It aims to query the number of shortest paths between vertices,which is widely used in path planning and recommendation,social network analysis,betweenness centrality calculation and so on.At present,more and more networks can be modeled as temporal graphs,but there is no research work on the shortest path counting query problem of temporal graphs.Compared with the static graph,the temporal graph increases the time information,the structure is more complex,and the activation time of the edge must be considered when querying the number of paths between vertices.Therefore,the shortest path counting method for the static graphs is no longer applicable to the temporal graphs,and querying on large-scale temporal graphs is more challenging.In order to solve the shortest path counting problem of temporal graphs,a method of TG-TL(Temporal Graph-Tree Label)index based on tree decomposition was proposed.The method consists of two stages:index construction and online query.In the index construction stage,the temporal tree decomposition algorithm was designed according to the attributes of the temporal graph,and the temporal graph was transformed into a tree structure.Then,according to the structure information of tree decomposition and convex path definition,an efficient index building algorithm was proposed.In the online query stage,an efficient temporal shortest path counting query algorithm was proposed based on TG-TL index.Experiments were carried out on 4 real datasets,and the experimental results showed that compared with the query algorithm based on TG-base(Temporal Graph-base)index,the proposed algorithm improved the query efficiency by 61%at least.Therefore,the proposed algorithm is efficient and effective for the shortest path counting problem of temporal graphs.