Online Sampling of Temporal Networks
Online Sampling of Temporal Networks
复制标题
DOI：
10.1145/3442202
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Nesreen K. Ahmed;N. Duffield;Ryan A. Rossi
中科院分区：
文献类型：
--
作者：
Nesreen K. Ahmed;N. Duffield;Ryan A. Rossi
表示时间戳边缘流的时间网络在真实的世界中似乎无处不在。然而，这些网络的巨大规模和连续性使其在分析和利用描述性和预测性建模任务方面具有根本性的挑战。在这项工作中，我们提出了一个通用的框架，时间网络采样无偏估计。我们开发在线，单通采样算法，和无偏估计的时间网络采样。所提出的算法能够快速，准确，和内存效率的时间网络模式和属性的统计估计。此外，我们提出了一个时间衰减采样算法与无偏估计研究网络的发展在连续的时间，其中的链接的强度是一个函数的时间，和图案的时间加权。与先前的△ t-时间基序概念相反，所提出的计算时间加权基序的公式和算法对于预测网络中的任务是有用的，例如预测未来的链路，或节点和链路的未来时间序列变量。最后，在不同领域的各种时态网络上的实验证明了所提出的算法的有效性。提供了详细的消融研究，以了解拟议框架的各个组成部分的影响。
Temporal networks representing a stream of timestamped edges are seemingly ubiquitous in the real world. However, the massive size and continuous nature of these networks make them fundamentally challenging to analyze and leverage for descriptive and predictive modeling tasks. In this work, we propose a general framework for temporal network sampling with unbiased estimation. We develop online, single-pass sampling algorithms, and unbiased estimators for temporal network sampling. The proposed algorithms enable fast, accurate, and memory-efficient statistical estimation of temporal network patterns and properties. In addition, we propose a temporally decaying sampling algorithm with unbiased estimators for studying networks that evolve in continuous time, where the strength of links is a function of time, and the motif patterns are temporally weighted. In contrast to the prior notion of a △ t-temporal motif, the proposed formulation and algorithms for counting temporally weighted motifs are useful for forecasting tasks in networks such as predicting future links, or a future time-series variable of nodes and links. Finally, extensive experiments on a variety of temporal networks from different domains demonstrate the effectiveness of the proposed algorithms. A detailed ablation study is provided to understand the impact of the various components of the proposed framework.