Source-linked AI summary
Modeling sequences and temporal networks with dynamic community structures
Tiago P. Peixoto, Martin Rosvall
TL;DR
Dynamic networks are difficult to analyze, and existing methods can impose timescales or overfit when identifying their community structure. This paper uses arbitrary-order Markov chains with nonparametric Bayesian inference to model dynamics on and of networks. The authors report meaningful temporal structures in real-world data and improved temporal-network prediction over static prediction.
Problem
Methods for dynamic community structure can impose arbitrary timescales, while data-driven higher-order models risk overfitting their high-dimensional data.
Source: INTRODUCTION · p. 1Method
The paper models event sequences with arbitrary-order Markov chains and uses nonparametric Bayesian inference to select parsimonious models for dynamics on and of networks.
Source: INTRODUCTION · p. 1, Temporal networks · p. 5Results
Temporal network models predicted edges better than the static DCSBM in all examined cases, and the best Markov order matched the minimum-description-length choice.
Source: Temporal prediction · p. 7Takeaways & Limitations
The authors report that the model finds meaningful large-scale temporal structures in real-world systems and predicts their temporal evolution.
Source: DISCUSSION · p. 7Inference for a fixed Markov order does not account for waiting-time distributions, although those distributions may influence the preferred order.
Source: Continuous time · p. 12
Abstract
from arXiv · showhide
In evolving complex systems such as air traffic and social organizations, collective effects emerge from their many components' dynamic interactions. While the dynamic interactions can be represented by temporal networks with nodes and links that change over time, they remain highly complex. It is therefore often necessary to use methods that extract the temporal networks' large-scale dynamic community structure. However, such methods are subject to overfitting or suffer from effects of arbitrary, a priori imposed timescales, which should instead be extracted from data. Here we simultaneously address both problems and develop a principled data-driven method that determines relevant timescales and identifies patterns of dynamics that take place on networks as well as shape the networks themselves. We base our method on an arbitrary-order Markov chain model with community structure, and develop a nonparametric Bayesian inference framework that identifies the simplest such model that can explain temporal interaction data.
INTRODUCTION
Existing approaches impose timescales or risk overfitting when inferring dynamic community structure. The paper introduces a data-driven Bayesian model for sequences and network dynamics that selects model complexity from evidence.
INTRODUCTION
- Higher-order methods either require an externally chosen memory order or aggregate network activity into time windows, imposing timescales that can obscure dynamic community structure.When timescales are inferred from high-dimensional data, random fluctuations can also be mistaken for structure, causing overfitting.Source: INTRODUCTION · p. 1
- The framework models event sequences with arbitrary-order Markov chains and describes network dynamics by treating edge occurrences as events, without aggregating time windows or imposing a priori timescales.The Markov model assumption remains; the model can represent higher-order memory of arbitrary order.Source: INTRODUCTION · p. 1
- Nonparametric Bayesian inference selects the most parsimonious model supported by the data, including its Markov order and number of communities, to counter overfitting.For random dynamics, the method concludes that the data lack structure rather than identifying spurious patterns.Source: INTRODUCTION · p. 1
Inference of Markov chains
- Maximum likelihood can favor ever-higher Markov orders and overfit, whereas Bayesian evidence accounts for model complexity when selecting an order.With enough statistics, this approach can identify the correct order for data sampled from Markov chains.Source: Inference of Markov chains · p. 2
- Adding community structure to the Bayesian sequence model connects sequence modeling to network communities and provides a basis for modeling temporal networks.The extension offers stronger explanatory power for sequences and a model in which the sequence represents a temporal network.Source: Inference of Markov chains · p. 2
Markov chains with communities
The model groups memories and tokens in an arbitrary-order Markov chain, using Bayesian inference to select model complexity from the data. It describes empirical sequences better than common Markov parametrization and captures higher-order memory patterns.
Markov chains with communities
- The model partitions both memories and tokens into groups, parameterizing transitions with token-selection weights and probabilities between memory and token groups.For n=1, tokens and memories can instead share a unified partition.Source: Markov chains with communities · pp. 2–3, Figure 2 · p. 3
- For undirected networks without higher-order memory, inferring structure from topology and from the dynamics on the network is equivalent in this model.The likelihood is almost the degree-corrected stochastic block model likelihood, differing only by constant terms that do not change the maximizing partition.Source: Markov chains with communities · p. 3
- Bayesian inference balances sequence fit against model complexity through description length, penalizing added groups or Markov order as their model likelihood decreases.The description length accounts for both data and model and is presented as an exact measure of model flexibility.Source: Markov chains with communities · pp. 3–4
- Hierarchical priors address underfitting from overly strong prior assumptions and allow multiple scales through hierarchical partitions of tokens and memories.Source: Markov chains with communities · p. 4
- Across empirical sequences, the model yields smaller description lengths than common Markov parametrization and identifies higher-order memory; shuffled data select a random n=1 model.The random model has one token group and one memory group, equivalent to a memoryless model.Source: Table I · p. 4, Markov chains with communities · p. 5
- In US itineraries, the model groups memories to distinguish Atlanta transit from Las Vegas destination patterns, while airport co-clustering identifies alternative destinations and exposes higher-order memory patterns conventional methods obscure.Source: Markov chains with communities · p. 5
Temporal networks
The temporal-network model combines Markov dynamics over edge labels with degree-corrected sampling of actual edges, allowing it to infer temporal and node-group structure. In empirical networks, it detects temporal patterns, including class-linked mixing in a high-school proximity network.
Temporal networks
- For sparse networks, node groups map edges to (c_i,c_j) labels, reducing the token space from O(N^2) to O(C^2) before Markov modeling.The reduced token space has a more controllable number of parameters suited to sparse data.Source: Temporal networks · p. 5
- The temporal-network likelihood combines edge-label sequence dynamics with degree-corrected sampling of actual edges conditioned on node groups.Setting BN=BM=1 recovers the static DCSBM; nonparametric priors are placed on node, token, and memory partitions.Source: Temporal networks · pp. 5–6
- The model infers node, token, and memory group counts; for fully random networks, it most probably infers BN=BM=C=1.That setting corresponds to a random network both in its aggregate structure and over time.Source: Temporal networks · p. 6
- Without the intermediary edge-label layer, direct edge-token fitting yields much larger description lengths and often misses Markov structure.The intermediary layer models edge labels rather than individual edges directly.Source: Temporal networks · pp. 5–6
- In the high-school network, inferred groups recover the nine classes except for PC, which splits in two, while edge-label clusters reveal class-based temporal mixing.The model uses 10 node groups and 9 groups each for memory and token labels.Source: Temporal networks · p. 6, Figure 4 · p. 7
Temporal prediction
The paper evaluates temporal-network predictions using held-out sequence data and compares predictive performance with description-length model selection. The temporal model predicts better than the static baseline in every case, and both criteria select the same Markov order.
Temporal prediction
- Each sequence is split into equal contiguous training and validation parts; the model is fit on training data and evaluated on validation likelihood.The held-out likelihood is bounded below using the description-length difference between training-only and full-data fits.Source: Temporal prediction · p. 7
- The temporal-network model predicts the validation set better than the static DCSBM in all cases, and its best Markov order matches the minimum-description-length choice.The reported agreement holds for the empirical datasets considered.Source: Temporal prediction · p. 7
- The lower bound on validation likelihood becomes tight as both training and validation sets grow, making it an asymptotic approximation to predictive likelihood.Source: Temporal prediction · p. 7
DISCUSSION
The model extends community detection to dynamic sequences and temporal networks, inferring Markov order and group counts from data. Bayesian model selection balances fit against complexity, while hierarchical priors address limitations of simpler priors.
DISCUSSION
- The model captures long pathways and large-scale structures in sequences and temporal networks, inferring Markov order and group counts rather than requiring them as inputs.The discussion also reports meaningful structures in real-world systems and prediction of their temporal evolution.Source: DISCUSSION · p. 7
Bayesian Markov chains with communities
- Bayesian inference integrates over model parameters, making inference nonparametric and allowing model order to be inferred from data without overfitting.The approach selects the most parsimonious model according to available statistical evidence.Source: Bayesian Markov chains with communities · p. 9
- Uniform priors assign probability 1/Ω to allowed configurations of token frequencies and group-transition counts.Ω is the number of possibilities under the imposed constraints.Source: Bayesian Markov chains with communities · p. 10
- The Dirichlet-prior formulation can underfit, with the maximum number of detectable groups scaling sub-optimally; nested-SBM priors replace that resolution limit with N/ln N.The nested prior also provides a multilevel data description while remaining unbiased.Source: Bayesian Markov chains with communities · p. 10
- A fast multilevel MCMC method minimizes description length with O(N log^2 N) complexity, independent of the number of groups.Here N counts memory and token nodes.Source: Bayesian Markov chains with communities · p. 10
The unified first-order model
For first-order chains, the model can use one shared partition for memories and tokens instead of co-clustering them separately. The paper uses this variant when it gives a smaller description length and simpler visualization for a dataset.
The unified first-order model
- For n = 1, memories and tokens can share an identical partition with the same number of groups, equivalent to clustering a directed transition-graph projection.The usual co-clustering likelihoods remain unchanged, with the two partitions constrained to be identical and one partition likelihood omitted.Source: The unified first-order model · p. 11
- This unified variant describes many datasets slightly better than co-clustering, though exceptions occur; it was used for Fig. 4 because it reduced description length and simplified visualization.Source: The unified first-order model · p. 11
Temporal networks
The temporal-network likelihood combines a static description of the aggregated graph with a dynamic model of edge-label sequences. The static degree-corrected stochastic block model is recovered when transitions are memoryless.
Temporal networks
- The temporal-network likelihood integrates over node parameters κ_i using noninformative priors to avoid overfitting.The likelihood is conditioned on node labels and community assignments.Source: Temporal networks · p. 11
- The temporal-network likelihood separates into a static term for the aggregated graph and a dynamic term for the Markov chain of edge labels.The static term is the nonparametric likelihood of the static DCSBM.Source: Temporal networks · p. 11
- The static DCSBM is recovered exactly by setting B_N = B_M = 1, which makes state transitions memoryless; equivalently, it is the n = 0 case of the temporal model.Source: Temporal networks · p. 11
Predictive held-out likelihood
The held-out likelihood calculation provides a lower bound that becomes tight as training and validation sets grow. In continuous time, waiting times inform memory groups and can change the inferred Markov order, as illustrated by Beethoven’s fifth symphony.
Predictive held-out likelihood
- The held-out predictive likelihood is lower-bounded by optimizing partitions for newly observed memories or tokens; this bound becomes tight as training and validation sets grow.The bound uses the change in description length between the training set and the full data.Source: Predictive held-out likelihood · pp. 11–12
Continuous time
- Continuous-time modeling represents observations as an embedded token sequence plus inter-event waiting times, which can separate memory groups with different delays.The inference assumes waiting times are sampled from the same distribution within each group.Source: Continuous time · p. 12
- n = 1 is favored by the discrete-time model and n = 2 by the continuous-time model for Beethoven’s fifth symphony, where timing reveals chord-associated delays and short- and long-pause groups.The discrete-time groups are only weakly correlated with actual waiting times, while the continuous-time groups are strongly correlated; these patterns appear in the higher-order model.Source: Continuous time · p. 13, Table III · p. 13, Figure 5 · p. 13
- For bursty processes with power-law waiting times, transforming the delays permits the same exponential-model inference procedure and algorithm.Source: Continuous time · p. 13
Nonstationarity and hidden contexts
Annotating tokens with covariates lets a stationary Markov chain represent nonstationary dynamics and changing group membership. In two concatenated novels, novel annotations separate language patterns and yield a shorter description length than a mixed model.
Nonstationarity and hidden contexts
- Adding an epoch or other covariate to each token lets a stationary Markov chain represent dynamics that would be nonstationary if the covariate were omitted.The model assumes the same transition probabilities throughout the sequence; augmenting tokens with a covariate can extend it without changing the model formulation.Source: Nonstationarity and hidden contexts · p. 13
- 7,146,465 for novel-annotated n = 3 versus 7,450,322 for unannotated n = 3: the separate description is shorter despite using more tokens and memories.The example concatenates an English translation of War and Peace with the French original of À la recherche du temps perdu; the separate model learns the French patterns differently from English.Source: Figure 6 · p. 14, Nonstationarity and hidden contexts · p. 14
- The same token can belong to different groups when associated with different covariate values, so group membership can vary over time.Source: Nonstationarity and hidden contexts · p. 14
- The approach can uncover change points when the rules governing dynamics change significantly between periods.Source: Nonstationarity and hidden contexts · p. 14
- Annotations can encode known spatial information on transitions in student-proximity networks, or help infer hidden contexts when that information is unavailable.Annotating transitions with spatial information yields a multilayer version of the model, similar to the layered SBM.Source: Nonstationarity and hidden contexts · p. 14
Equivalence between structure and dynamics
For random walks on connected undirected graphs, the n = 1 projected Markov model and the degree-corrected stochastic block model select the same node partition. This equivalence does not extend to directed graphs, higher-order memory, or model selection over the number of groups.
Equivalence between structure and dynamics
- For a random walk on a connected undirected graph at equilibrium, expected Markov-chain edge counts are proportional to graph edge counts under the same node partition, so the n = 1 model and DCSBM maximize at the same partition.Their likelihoods differ only by trivial additive and multiplicative constants; the Markov likelihood also omits memory degrees.Source: Equivalence between structure and… · p. 14
- The likelihood in Eq. 4 is almost the same as the DCSBM, and this connection links inference of network communities to modeling dynamics on the network.Source: Equivalence between structure and… · p. 14
- The equivalence breaks down for directed graphs, higher-order memory with n > 1, and cases where model selection chooses the number of groups.Source: Equivalence between structure and… · p. 14
Comparison with the map equation for network flows with memory
The community-based Markov model and the map equation both seek compression but optimize different aspects of network dynamics. Their differing assumptions and model-selection procedures mean the problem at hand should determine which approach to use.
Comparison with the map equation for network flows with memory
- The map equation minimizes an encoding of transitions projected onto a node partition, whereas this model uses a Bayesian generative model and description length for the entire sequence.The map equation describes transitions between physical nodes through internal and external flows among memory-state groups.Source: Comparison with the map equation for… · pp. 14–15
- The map equation identifies assortative modules with long flow persistence and uses bootstrap or cross-validation for Markov-order selection, while this model supports disassortative chains and unsupervised selection of order and group count.The approaches can therefore give different results, so the task should guide method choice.Source: Comparison with the map equation for… · p. 15
- This model can also generate new data and make predictions from past observations, unlike heuristic methods designed only to find network or time-series partitions.Source: Comparison with the map equation for… · p. 15
Datasets
The study draws on temporal networks, event sequences, and text datasets spanning social contact, communication, transport, games, music, literature, and passwords.
Datasets
- The dataset inventory also includes high-school proximity measurements and time-stamped Internet autonomous-system connections.Source: Datasets · p. 15
- Social-contact datasets cover high-school students, hospital patients and staff, museum visitors, and university students and faculty.The high-school dataset tracks 327 students for five days; the hospital dataset tracks 75 people for four days; the museum dataset tracks 10,972 participants for three months; and the university dataset tracks 96 people for an academic year.Source: Datasets · pp. 15–16
- The datasets comprise 1,148,072 Enron emails, 500,106 directed AS connections, time-stamped APS citations among 425,760 articles over 100 years, and 3,394,979 directed Prosper loan relationships.Source: Datasets · pp. 15–16
- Additional movement and interaction sequences come from chess games and taxi GPS logs discretized into geographic cells.The chess dataset converts games into a bipartite temporal network of pieces and positions; the taxi dataset concatenates rides with separator tokens.Source: Datasets · pp. 15–16
- Sequence datasets also include a Beethoven symphony represented as notes, War and Peace as text tokens, and a concatenated list of RockYou passwords.War and Peace has 3,226,652 tokens; the password list has 289,836,299 tokens.Source: Datasets · pp. 15–16