Using Motif Transitions for Temporal Graph Generation
arXiv:2306.11190 · doi:10.1145/3580305.3599540
Abstract
Graph generative models are highly important for sharing surrogate data and benchmarking purposes. Real-world complex systems often exhibit dynamic nature, where the interactions among nodes change over time in the form of a temporal network. Most temporal network generation models extend the static graph generation models by incorporating temporality in the generation process. More recently, temporal motifs are used to generate temporal networks with better success. However, existing models are often restricted to a small set of predefined motif patterns due to the high computational cost of counting temporal motifs. In this work, we develop a practical temporal graph generator, Motif Transition Model (MTM), to generate synthetic temporal networks with realistic global and local features. Our key idea is modeling the arrival of new events as temporal motif transition processes. We first calculate the transition properties from the input graph and then simulate the motif transition processes based on the transition probabilities and transition rates. We demonstrate that our model consistently outperforms the baselines with respect to preserving various global and local temporal graph statistics and runtime performance.
arXiv commentAccepted by 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD2023)
References in corpus (24)
- Temporal Networks
- Mixed membership stochastic blockmodels
- Modeling bursts and heavy tails in human dynamics
- Motifs in Temporal Networks
- A Poissonian explanation for heavy-tails in e-mail communication
- Temporal motifs in time-dependent networks
- Dynamical Patterns of Cattle Trade Movements
- Temporal motifs reveal homophily, gender-specific patterns and group talk in mobile communication networks
- A Scalable Generative Graph Model with Community Structure
- A state-space mixed membership blockmodel for dynamic network tomography
- Random graph models for dynamic networks
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
- Random graph models for directed acyclic networks
- Epidemiologically optimal static networks from temporal network data
- A dynamic model of time-dependent complex networks
- Randomized reference models for temporal networks
- Dynamic stochastic blockmodels: Statistical models for time-evolving networks
- Statistically validated mobile communication networks: Evolution of motifs in European and Chinese data
- DYMOND: DYnamic MOtif-NoDes Network Generative Model
- Nonparametric Multi-group Membership Model for Dynamic Networks
- Temporal Motifs in Patent Opposition and Collaboration Networks
- Temporal Network Motifs: Models, Limitations, Evaluation
- Temporal Motifs for Financial Networks: A Study on Mercari, JPMC, and Venmo Platforms