# Temporal Scale Estimation for Oversampled Network Cascades: Theory, Algorithms, and Experiment

arXiv: https://arxiv.org/abs/2109.10937 · HTML: https://mlsanity.com/paper/2109.10937/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 22 Sep 2021.

## Builds on (most cited first, 6 of 6)

- [Can Cascades be Predicted?](https://mlsanity.com/paper/1403.4608/) (2014)
- [Learning and Forecasting Opinion Dynamics in Social Networks](https://mlsanity.com/paper/1506.05474/) (2015)
- [On the Fairness of Time-Critical Influence Maximization in Social Networks](https://mlsanity.com/paper/1905.06618/) (2019)
- [The Effects of Evolutionary Adaptations on Spreading Processes in Complex Networks](https://mlsanity.com/paper/1810.04545/) (2018)
- [Information Evolution in Social Networks](https://mlsanity.com/paper/1402.6792/) (2014)
- [Network Clocks: Detecting the Temporal Scale of Information Diffusion](https://mlsanity.com/paper/1709.04015/) (2017)

## Abstract (arXiv)

Spreading processes on graphs arise in a host of application domains, from the study of online social networks to viral marketing to epidemiology. Various discrete-time probabilistic models for spreading processes have been proposed. These are used for downstream statistical estimation and prediction problems, often involving messages or other information that is transmitted along with infections caused by the process. It is thus important to design models of cascade observation that take into account phenomena that lead to uncertainty about the process state at any given time. We highlight one such phenomenon -- temporal distortion -- caused by a misalignment between the rate at which observations of a cascade process are made and the rate at which the process itself operates, and argue that failure to correct for it results in degradation of performance on downstream statistical tasks. To address these issues, we formulate the clock estimation problem in terms of a natural distortion measure. We give a clock estimation algorithm, which we call FastClock, that runs in linear time in the size of its input and is provably statistically accurate for a broad range of model parameters when cascades are generated from the independent cascade process with known parameters and when the underlying graph is ErdHos-R'enyi. We further give empirical results on the performance of our algorithm in comparison to the state of the art estimator, a likelihood proxy maximization-based estimator implemented via dynamic programming. We find that, in a broad parameter regime, our algorithm substantially outperforms the dynamic programming algorithm in terms of both running time and accuracy.