论文标题
ONBRA：时间网络中时间间隔的严格估计
ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks
论文作者
论文摘要
在网络分析中，节点的中间性非正式地捕获了访问该节点的最短路径的比例。在分析现代网络的分析中，中间性措施的计算是一项基本任务，可以识别此类网络中最中心的节点。除了大规模的现代网络外，现代网络还包含有关其事件发生时间的信息。这样的网络通常称为时间网络。时间信息使得对时间网络中的中间性（即时间间隔中心性）的研究比静态网络（即没有时间信息的网络）更具挑战性。此外，鉴于其非常高的计算成本，在中间的网络上，时间中心的确切计算在甚至中度的网络上通常是不切实际的。降低这种计算成本的一种自然方法是获得对时间间隔的确切值的高质量估计。在这项工作中，我们提出了ONBRA，这是第一个基于抽样的近似算法，用于估计时间网络中节点的时间间隔中心值，从而为其输出质量提供了严格的概率保证。 ONBRA能够计算出时间网络最短路径的两个不同最佳标准下的时间间隔中心值的估计值。此外，ONBRA以敏锐的理论保证在\ emph {经验性伯恩斯坦绑定}（一种高级浓度不平等）上利用高质量的估计值。最后，我们的实验评估表明，ONBRA大大减少了几个现实世界网络上时间间隔的确切计算所需的计算资源，同时以严格的保证报告了高质量的估计。
In network analysis, the betweenness centrality of a node informally captures the fraction of shortest paths visiting that node. The computation of the betweenness centrality measure is a fundamental task in the analysis of modern networks, enabling the identification of the most central nodes in such networks. Additionally to being massive, modern networks also contain information about the time at which their events occur. Such networks are often called temporal networks. The temporal information makes the study of the betweenness centrality in temporal networks (i.e., temporal betweenness centrality) much more challenging than in static networks (i.e., networks without temporal information). Moreover, the exact computation of the temporal betweenness centrality is often impractical on even moderately-sized networks, given its extremely high computational cost. A natural approach to reduce such computational cost is to obtain high-quality estimates of the exact values of the temporal betweenness centrality. In this work we present ONBRA, the first sampling-based approximation algorithm for estimating the temporal betweenness centrality values of the nodes in a temporal network, providing rigorous probabilistic guarantees on the quality of its output. ONBRA is able to compute the estimates of the temporal betweenness centrality values under two different optimality criteria for the shortest paths of the temporal network. In addition, ONBRA outputs high-quality estimates with sharp theoretical guarantees leveraging on the \emph{empirical Bernstein bound}, an advanced concentration inequality. Finally, our experimental evaluation shows that ONBRA significantly reduces the computational resources required by the exact computation of the temporal betweenness centrality on several real world networks, while reporting high-quality estimates with rigorous guarantees.
