Source-linked AI summary
Temporal motifs in time-dependent networks
Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, Jari Saramäki
TL;DR
Temporal motifs address the need to analyze mesoscale structure in temporal networks without discarding event timing. The paper defines order-sensitive temporal motifs, maps them to colored directed graphs for efficient identification, and finds that mobile-call motifs reveal burstiness and causality.
Problem
Static aggregation can discard temporal inhomogeneities that affect network dynamics, motivating mesoscale structures that capture both topology and time.
Method
The paper defines temporal motifs as classes of isomorphic valid event subgraphs and maps them to colored directed graphs whose canonical forms support efficient identification.
Results
Mobile-call data show that temporal motifs are common enough to affect dynamics and too complex to be explained by simple temporal correlations, highlighting burstiness and causality.
Takeaways & Limitations
Temporal motifs provide a way to study mesoscopic building blocks of temporal networks and their possible roles in network function and underlying mechanisms.
Takeaways & Limitations
The temporal-subgraph definition assumes that each node participates in at most one event at a time, while realistic temporal distributions also make null-model choice difficult.
Abstract
from arXiv · showhide
Temporal networks are commonly used to represent systems where connections between elements are active only for restricted periods of time, such as networks of telecommunication, neural signal processing, biochemical reactions and human social interactions. We introduce the framework of temporal motifs to study the mesoscale topological-temporal structure of temporal networks in which the events of nodes do not overlap in time. Temporal motifs are classes of similar event sequences, where the similarity refers not only to topology but also to the temporal order of the events. We provide a mapping from event sequences to colored directed graphs that enables an efficient algorithm for identifying temporal motifs. We discuss some aspects of temporal motifs, including causality and null models, and present basic statistics of temporal motifs in a large mobile call network.
1. Introduction
Temporal networks preserve time-stamped interactions that static aggregation discards, enabling analysis of mesoscale structures shaped by both topology and temporal order.
- Temporal-network motivation: Temporal inhomogeneities can strongly affect information spreading, epidemics, and brain-signal processes beyond what weighted static networks capture.Static link weights summarize activation frequencies but do not represent all temporal correlations relevant to dynamics.
- Temporal-network motivation: Temporal network models represent interactions as time-limited events rather than continuously active edges.Events may be directed and include start time and duration; the framework assumes nodes do not participate in simultaneous events.
- Research gap: Temporal mesoscale structures may reflect system function and clarify social interaction, group information processing, and spreading dynamics.Prior work examined temporal components and related motif-like structures, but some approaches project away temporal information or focus on time-respecting paths.
- Paper contribution: The paper defines temporal motifs as isomorphic connected temporal subgraphs whose similarity includes the temporal order of events.It also presents an efficient algorithm for identifying all such motifs in time-stamped event sequences.
- Paper contribution: Temporal motifs group similar event sequences across different sets of nodes, such as repeated call patterns in social communication networks.The same framework is also motivated by event sequences representing regulatory interactions in genetic data.
2. Temporal motifs
Temporal motifs are built from valid event sets that are connected in topology and time, include consecutive relevant events, and preserve temporal ordering; the definition assumes non-overlapping node events.
- Temporal connectivity: Two events are ∆t-adjacent when they share a node and the gap from the first event’s end to the second’s start is at most ∆t.∆t-connectedness extends adjacency through sequences of such event pairs.
- Temporal connectivity: Connected temporal subgraphs require every event pair to be ∆t-connected, ensuring both topological and temporal connectivity.Allowing all such subgraphs can produce unintuitive counts, including combinatorial growth in an n-star.
- Valid temporal subgraphs: Valid temporal subgraphs include all consecutive ∆t-connected events of each node, preventing skipped events and reducing an n-star to n−k +1 subgraphs with k events.Temporal motifs are isomorphic valid subgraphs whose event order is also identical, unless a weaker order criterion is chosen.
- Special motifs: Unit event sets and maximal ∆t-connected subgraphs are valid, and motifs based only on maximal subgraphs are called maximal motifs.Each event belongs to a unique maximal subgraph, and every valid subgraph is contained in one.
- Scope boundary: The definition is meaningful only when each node participates in at most one event at a time.Allowing overlapping events creates many situations that make temporal subgraphs harder to define and interpret.
3. Algorithm for identification of temporal motifs
The identification algorithm decomposes the task into maximal-subgraph discovery, valid-subgraph enumeration, and motif classification through colored directed-graph canonicalization.
- Algorithm outline: All temporal motifs are found by first locating maximal connected subgraphs, then enumerating valid subgraphs within them, and finally identifying each motif.Because maximal subgraphs are temporally separated, every valid subgraph lies within one maximal subgraph.
- Maximal-subgraph discovery: Maximal subgraphs are discovered by recursively traversing ∆t-adjacent events forward and backward from each event.Assuming constant-time adjacency queries, the total complexity of this stage is O(|E|).
- Valid-subgraph enumeration: Within a maximal subgraph, valid temporal subgraphs correspond to connected vertex sets in a graph linking events that are consecutive and ∆t-adjacent for a node.The algorithm finds induced subgraphs and checks that each node’s events remain consecutive.
- Motif classification: Motif identification maps nodes and events into a colored directed graph that encodes topology and event order, then compares canonical forms.Canonical labeling is identical for isomorphic graphs, allowing equivalent valid subgraphs to share a motif identity.
4. Flow motifs and partial order of events
Flow motifs retain only event-order constraints that affect possible journeys, and a compact pair-based notation represents partial orders without forcing irrelevant comparisons.
- Partial orders: Event-order edges support partial orders, allowing one event to precede two others while leaving those latter events unordered.This represents distinctions that integer labels for total orders cannot encode.
- Flow motifs: For mobile phone calls, two subgraphs differing only in the order of non-consequential events can permit identical information flows.These flows are time-respecting paths through adjacent events.
- Algorithmic representation: The identification algorithm encodes event order as directed edges and computes a canonical labeling before presenting the motif compactly.Figure 2 illustrates the sequence using event times t1 = 3, t2 = 5, t3 = 9, and t4 = 17.
- Flow motifs: A flow motif restricts the order of adjacent events only when reversing them would create or remove a journey.For undirected flow, all adjacent-event orders relevant to preserving journeys are constrained; directed flow restricts head-to-tail cases.
- Compact notation: Partial event orders are represented by labels (r, s), where r is an integer and s is a set, ordered through the set relation.When possible, empty sets reduce the notation to ordinary integer comparisons; otherwise labels such as 2a encode additional ordering information.
5. Evaluation of motif statistics
Temporal motif evaluation requires reference comparisons that preserve realistic temporal structure, while relative-frequency and rank-based statistics capture complementary differences between motif distributions.
- Null-model interpretation is non-trivial because unrealistic randomized references can make structurally significant motif counts misleading.The standard z-score additionally assumes Gaussian null-model variation without a priori justification.
- Time-shuffling is especially problematic for temporal motifs because real temporal distributions contain strong non-Poissonian temporal correlations.Parametrized null models can restore the empirical situation in a limit and reveal correlation structure through parameter dependence.
- Time-reversed references can highlight motifs whose occurrence is at least partly associated with causality rather than correlation alone.Correlation-driven motifs should occur equally often in the data and time-reversed reference; explicit reversal construction is unnecessary because reversed-motif counts in the actual data are equivalent.
- Within-data comparisons across node or event types and times estimate relative motif occurrence without relying on arbitrary null models.These comparisons provide relative motif weights while avoiding an external randomized reference.
- Relative motif frequencies should be compared because motif counts are trivially correlated with average activity and adjacent-event correlations.For empirical and reference counts, the ith motif is represented by relative frequencies p_i and q_i, with motifs absent from either sequence excluded.
- Kullback–Leibler divergence emphasizes common motifs, whereas Kendall’s τ weights all motifs equally by comparing their count orderings.Kendall’s τ equals 1 for identical orderings and −1 for opposite orderings.
6. Results
The mobile-call analysis shows that temporal-motif frequencies reflect burstiness and causality, while biased time-shuffled references reproduce some aggregate trends without matching motif sequences. Motif distributions also vary substantially with temporal-window size and motif scale.
- Mobile-call data: 320 million calls from nearly 9 million customers were analyzed over 120 days using a 10-minute temporal window.The data were mutualized by removing events on unidirectional edges; motifs entirely on the first or last day were excluded.
- Empirical versus shuffled motifs: 35% of events are Δt-adjacent at Δt = 10 min, whereas only 8.6% of events are adjacent in the unbiased time-shuffled reference.The lower adjacency in the reference produces fewer non-trivial motifs.
- Empirical versus shuffled motifs: The most common empirical 3-event motif comprises 27% of all 3-event motifs, compared with 6.3% in the time-shuffled reference.The empirical distribution is more concentrated, while the shuffled distribution is more balanced; triangles are among the least common empirical motifs.
- Biased reference: A biased shuffle with m = 32 raises motif counts but reaches only 60% of the empirical total for 3-event motifs.The bias favors shorter inter-event times through candidate selection, while m = 1 recovers ordinary unbiased randomization.
- Triangle motifs: The six directed-triangle motifs differ by a 4-fold empirical count range, with burstiness and causality favoring motifs whose event order is consecutive and potentially informative.For another triangle pair, the causally consistent triangle is three times as common as the other one; time reversal maps the two motif kinds into each other.
- Motif size: Maximal-motif distributions are broad, and comparison of Δt = 1200 and 2400 suggests that a giant temporal component begins forming between these values.At Δt = 1200, the density and cumulative distributions are described as close to power-law behavior.
- Reference-model comparison: Increasing bias strength makes aggregate motif counts, symmetrized KL divergence, and Kendall’s τ approach the empirical data, but motif sequences remain qualitatively different.At m = 32 some motifs are already more common in the reference, and motifs with more events remain relatively more common empirically regardless of bias.
7. Conclusions
The paper introduces temporal motifs and an efficient identification algorithm, then reports initial mobile-call-network findings linking motif structure to burstiness and causality. The authors note unresolved extensions for overlapping events and richer occurrence measures.
- Temporal motifs and a colored directed-graph mapping enable efficient identification and statistics of mesoscopic building blocks in temporal networks.The framework is designed to capture topological-temporal structure rather than only aggregated topology.
- In the mobile-call network, the most common three-event motifs involve only two nodes, consistent with burstiness being primarily a link property.
- Motifs permitting causal interpretations are more common, while maximal-motif distributions are fat-tailed and align with observed network correlations.
- Temporal motifs are common enough to affect dynamics and too complex to be explained by simple temporal correlations alone.Their occurrence highlights burstiness and causality in human communication.
- The framework currently excludes simultaneous multiple events at a node, and further work is needed to measure motif occurrence patterns.Both the definition and identification algorithms require extension for overlapping events.
- The presented examples do not cover the full richness of phenomena accessible through temporal motifs.
Appendix A. Finding temporal subgraphs
The appendix reduces valid temporal-subgraph discovery to connected-subgraph enumeration in an event graph, followed by a consecutiveness check. A recursive search returns each connected vertex set once and all possible connected sets.
- Each event in a maximal temporal subgraph is represented as a vertex in an undirected graph, with edges linking relevant adjacent events.Valid temporal subgraphs contained in the maximal subgraph correspond to connected subgraphs of this event graph.
- Every valid temporal subgraph corresponds to a connected subgraph of the event graph because its events are temporally connected and node events are consecutive.
- Connected event-graph subgraphs are not sufficient by themselves: each candidate must be checked for consecutiveness of every node’s events.A connected graph subgraph can fail validity when an intermediate event for a node is omitted.
- The consecutiveness check adds little extra cost because constructing the colored graph already requires processing all events.
- Distinct search subtrees ensure that each connected set is returned at most once, while the connectivity argument establishes that every connected set can be reached.
- The algorithm enumerates connected vertex sets recursively, using ordered search trees with excluded smaller nodes and expandable larger neighbors.The size parameter nmax can limit the returned vertex sets.
Appendix B. Event labels with partial order
The appendix presents an algorithm for assigning labels that encode partial ordering among events in a directed acyclic graph. Labels propagate along directed paths to distinguish required ordering from unconstrained event pairs.
- Label propagation: The algorithm initializes labels at roots and propagates them forward along directed paths, increasing r and pushing label sets to children.Branches with multiple children receive new unique set elements when necessary.
- Validity: For a required ordering e_i before e_j, label-set inclusion and rank increase encode the relation: s_i ⊆ s_j and r_i < r_j.The set s_i is pushed along the path from e_i to e_j, while r increases along that path.
- Algorithm setup: The input graph is a directed acyclic graph whose vertices represent events, with paths encoding required precedence.For events e_i and e_j, a directed path from e_i to e_j means e_i must occur before e_j.
- Validity: When no mutual order is required, the algorithm prevents either label set from containing the other by using distinct roots or uniquely labeled branches.The cases include disjoint sets for distinct roots and incomparable sets after branch convergence.
- Special case: When the input graph contains a total event order, the resulting labels are plain integers.