Temporal Network Sampling
arXiv:1910.08657
Abstract
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 -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.
References in corpus (11)
- The origin of bursts and heavy tails in human dynamics
- Higher-order organization of complex networks
- The fundamental advantages of temporal networks
- The dynamical strength of social ties in information spreading
- Temporal motifs in time-dependent networks
- Role Discovery in Networks
- Persistence and periodicity in a dynamic proximity network
- Epidemic Threshold in Continuous-Time Evolving Networks
- Learning Role-based Graph Embeddings
- Dynamic Node Embeddings from Edge Streams
- Influential User Subscription on Time-Decaying Social Streams