Predicting Sequences of Traversed Nodes in Graphs using Network Models with Multiple Higher Orders
arXiv:2007.06662 · doi:10.1007/s41109-023-00596-x
Abstract
We propose a novel sequence prediction method for sequential data capturing node traversals in graphs. Our method builds on a statistical modelling framework that combines multiple higher-order network models into a single multi-order model. We develop a technique to fit such multi-order models in empirical sequential data and to select the optimal maximum order. Our framework facilitates both next-element and full sequence prediction given a sequence-prefix of any length. We evaluate our model based on six empirical data sets containing sequences from website navigation as well as public transport systems. The results show that our method out-performs state-of-the-art algorithms for next-element prediction. We further demonstrate the accuracy of our method during out-of-sample sequence prediction and validate that our method can scale to data sets with millions of sequences.
arXiv comment18 pages, 5 figures, 2 tables; changes with v2: updated broken figure and MSNBC data
References in corpus (14)
- Maps of random walks on complex networks reveal community structure
- Memory in network flows and its effects on spreading dynamics and community detection
- Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
- Representing higher-order dependencies in networks
- Modeling sequences and temporal networks with dynamic community structures
- Detecting Memory and Structure in Human Navigation Patterns Using Markov Chain Models of Varying Order
- When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
- Inferring Markov Chains: Bayesian Estimation, Model Comparison, Entropy Rate, and Out-of-class Modeling
- The Spacey Random Walk: a Stochastic Process for Higher-order Data
- HONEM: Learning Embedding for Higher Order Networks
- HYPA: Efficient Detection of Path Anomalies in Time Series Data on Networks
- Personalized Purchase Prediction of Market Baskets with Wasserstein-Based Sequence Matching
- An Interdisciplinary Comparison of Sequence Modeling Methods for Next-Element Prediction
- The likelihood-ratio test for multi-edge network models