标题： 使时间介于计算更快和不安宁 显示英文标题

标题： Making Temporal Betweenness Computation Faster and Restless

摘要： 该{\ss }等人[KDD 2020]最近证明，在首要路径和最快路径的情况下，计算时间图中所有节点的介数问题是计算上困难的，而在最短路径和最短首要路径的情况下，可以在时间O(n 3 T 2 )内解决，其中n是节点数，T是不同时间步数。 本文介绍了一种新的时间介数计算算法。 在最短路径和最短首要路径的情况下，它需要O(n + M )的空间，并在时间运行，其中M是时间边的数量，因此在时间复杂度方面显著改进了{\ss }等人算法（注意T通常很大）。 实验证据表明，我们的算法比{\ss }等人算法快两倍到近250倍。 此外，我们能够计算出具有超过一百万条时间边的几个大型时间图的精确时间介数值。 对于这种规模，只能使用Santoro和Sarpe[WWW 2022]的算法进行近似计算。 也许更重要的是，我们的算法扩展到了休息行走的情况（即每个节点有等待约束的行走），从而为几种不同的最优标准情况下的时间介数计算提供了一个多项式时间算法（复杂度为O(nM )）。 这种休息计算仅在最短标准下已知（Rymar等人[JGAA 2023]），复杂度为O(n 2 M T 2 )。 我们通过比较不同的等待约束和不同的优化标准进行了广泛的实验验证。 此外，作为案例研究，我们研究了包括柏林、罗马和巴黎在内的六个公共交通网络。 总体而言，我们发现不同版本的介数中心性之间有一致性。 然而，我们测量到等待约束有明显的影响，并注意到某些网络中某些标准对之间的相关性较低。 显示英文摘要

摘要： Bu{\ss} et al [KDD 2020] recently proved that the problem of computing the betweenness of all nodes of a temporal graph is computationally hard in the case of foremost and fastest paths, while it is solvable in time O(n 3 T 2 ) in the case of shortest and shortest foremost paths, where n is the number of nodes and T is the number of distinct time steps. A new algorithm for temporal betweenness computation is introduced in this paper. In the case of shortest and shortest foremost paths, it requires O(n + M ) space and runs in time where M is the number of temporal edges, thus significantly improving the algorithm of Bu{\ss} et al in terms of time complexity (note that T is usually large). Experimental evidence is provided that our algorithm performs between twice and almost 250 times better than the algorithm of Bu{\ss} et al. Moreover, we were able to compute the exact temporal betweenness values of several large temporal graphs with over a million of temporal edges. For such size, only approximate computation was possible by using the algorithm of Santoro and Sarpe [WWW 2022]. Maybe more importantly, our algorithm extends to the case of restless walks (that is, walks with waiting constraints in each node), thus providing a polynomial-time algorithm (with complexity O(nM )) for computing the temporal betweenness in the case of several different optimality criteria. Such restless computation was known only for the shortest criterion (Rymar et al [JGAA 2023]), with complexity O(n 2 M T 2 ). We performed an extensive experimental validation by comparing different waiting constraints and different optimisation criteria. Moreover, as a case study, we investigate six public transit networks including Berlin, Rome, and Paris. Overall we find a general consistency between the different variants of betweenness centrality. However, we do measure a sensible influence of waiting constraints, and note some cases of low correlation for certain pairs of criteria in some networks.