论文标题
时间间隔的算法方面
Algorithmic Aspects of Temporal Betweenness
论文作者
论文摘要
The betweenness centrality of a graph vertex measures how often this vertex is visited on shortest paths between other vertices of the graph.在对许多现实图形或网络的分析中，顶点的间隔用作其在网络中相对重要性的指标。 In particular, it is among the most popular tools in social network analysis.近年来，越来越多的现实世界网络被建模为时间图，我们有一组固定的顶点，并且存在有限的离散时间步骤集，并且只有在某些时间步骤中才会出现每个边缘。尽管最短的路径在静态图中很简单，但对于许多不同的标准，包括长度，到达时间和整体旅行时间（最短，最重要，最重要，最快，最快的路径）可以将时间路径视为“最佳”。这导致了时间间隔的不同概念，我们根据最佳时间路径的各种概念提供了对时间间隔变体的系统研究。 Computing the betweenness centrality for vertices in a graph is closely related to counting the number of optimal paths between vertex pairs.我们表明，计数最初和最快的路径在计算上是棘手的（＃p-hard），因此计算相应的时间间隔值也很棘手。 For shortest paths and two selected special cases of foremost paths, we devise polynomial-time algorithms for temporal betweenness computation.此外，我们还探索了时间路径中严格（上升时间标签）和非刻板时间（非延期时间标签）时间标签之间的区别。在我们既定的现实时间网络的实验中，我们证明了算法的实际有效性，比较各种中间概念，并就其实际使用提出了建议。
The betweenness centrality of a graph vertex measures how often this vertex is visited on shortest paths between other vertices of the graph. In the analysis of many real-world graphs or networks, betweenness centrality of a vertex is used as an indicator for its relative importance in the network. In particular, it is among the most popular tools in social network analysis. In recent years, a growing number of real-world networks is modeled as temporal graphs, where we have a fixed set of vertices and there is a finite discrete set of time steps and every edge might be present only at some time steps. While shortest paths are straightforward to define in static graphs, temporal paths can be considered "optimal" with respect to many different criteria, including length, arrival time, and overall travel time (shortest, foremost, and fastest paths). This leads to different concepts of temporal betweenness centrality and we provide a systematic study of temporal betweenness variants based on various concepts of optimal temporal paths. Computing the betweenness centrality for vertices in a graph is closely related to counting the number of optimal paths between vertex pairs. We show that counting foremost and fastest paths is computationally intractable (#P-hard) and hence the computation of the corresponding temporal betweenness values is intractable as well. For shortest paths and two selected special cases of foremost paths, we devise polynomial-time algorithms for temporal betweenness computation. Moreover, we also explore the distinction between strict (ascending time labels) and non-strict (non-descending time labels) time labels in temporal paths. In our experiments with established real-world temporal networks, we demonstrate the practical effectiveness of our algorithms, compare the various betweenness concepts, and derive recommendations on their practical use.
