Network interpolation
arXiv:1905.01253 · doi:10.1137/19M1268380
Abstract
Given a set of snapshots from a temporal network we develop, analyze, and experimentally validate a so-called network interpolation scheme. Our method allows us to build a plausible, albeit random, sequence of graphs that transition between any two given graphs. Importantly, our model is well characterized by a Markov chain, and we leverage this representation to analytically estimate the hitting time (to a predefined distance to the target graph) and long term behavior of our model. These observations also serve to provide interpretation and justification for a rate parameter in our model. Lastly, through a mix of synthetic and real-world data experiments we demonstrate that our model builds reasonable graph trajectories between snapshots, as measured through various graph statistics. In these experiments, we find that our interpolation scheme compares favorably to common network growth models, such as preferential attachment and triadic closure.
arXiv commentfinal preprint
References in corpus (13)
- Emergence of scaling in random networks
- Multilayer Networks
- Temporal Networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Connectivity of Growing Random Networks
- Simplicial Closure and higher-order link prediction
- Temporal Link Prediction using Matrix and Tensor Factorizations
- Dynamic stochastic blockmodels for time-evolving social networks
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Network Archaeology: Uncovering Ancient Networks from Present-day Interactions
- Inferring the interplay of network structure and market effects in Bitcoin
- Change Point Estimation in a Dynamic Stochastic Block Model
- A sampling framework for counting temporal motifs