Source-linked AI summary
Motifs in Temporal Networks
Ashwin Paranjape, Austin R. Benson, Jure Leskovec
TL;DR
Temporal network motifs are poorly characterized by existing approaches that discard or oversimplify timestamped interactions. This paper defines δ-temporal motifs, develops counting algorithms, and finds domain-specific and time-scale-specific motif patterns, with fast counting up to 56 times faster than a baseline.
Problem
Existing methods either treat temporal networks as permanently growing or aggregate them into snapshots, failing to fully capture temporal information.
Method
The paper defines δ-temporal motifs as induced temporal subgraphs whose edges are ordered and occur within a δ-time window, then develops general and faster counting algorithms.
Results
Motif counts distinguish communication patterns across domains and reveal motifs occurring at different time scales; fast temporal triangle counting is up to 56 times faster than a competitive baseline.
Takeaways & Limitations
Temporal motif counts provide structural information about communication behavior and the time scales at which temporal patterns develop.
Takeaways & Limitations
The faster algorithms are designed for 3-node, 3-edge star and triangle motifs and count instances without enumerating them.
Abstract
from arXiv · showhide
Networks are a fundamental tool for modeling complex systems in a variety of domains including social and communication networks as well as biology and neuroscience. Small subgraph patterns in networks, called network motifs, are crucial to understanding the structure and function of these systems. However, the role of network motifs in temporal networks, which contain many timestamped links between the nodes, is not yet well understood. Here we develop a notion of a temporal network motif as an elementary unit of temporal networks and provide a general methodology for counting such motifs. We define temporal network motifs as induced subgraphs on sequences of temporal edges, design fast algorithms for counting temporal motifs, and prove their runtime complexity. Our fast algorithms achieve up to 56.5x speedup compared to a baseline method. Furthermore, we use our algorithms to count temporal motifs in a variety of networks. Results show that networks from different domains have significantly different motif counts, whereas networks from the same domain tend to have similar motif counts. We also find that different motifs occur at different time scales, which provides further insights into structure and function of temporal networks.
1. INTRODUCTION
Temporal network motifs extend motif analysis to timestamped interactions by preserving edge order and timing. The paper defines these motifs, develops efficient counting algorithms, and uses them to identify domain- and timescale-specific communication patterns.
- Existing methods either model networks as permanently growing or aggregate time into snapshots, failing to capture the richness of temporal information.
- δ-temporal motifs are induced temporal patterns whose edges follow a specified order and occur within a δ-unit time window.The framework focuses on directed edges with timestamps and can generalize to durations, colors, and undirected edges.
- The general counting algorithm avoids enumerating temporal-edge subsets and runs in O(m) time for constant-edge motifs between two nodes.Its complexity depends on the static graph induced by the motif.
- Up to 56 times faster than a competitive baseline, the specialized triangle-counting algorithm runs in O(τ 1/2m) worst-case time.The algorithm is designed for temporal triangle motifs with three temporal edges.
- Text messaging and Facebook wall posting show mostly blocking communication, email mostly non-blocking communication, and private messaging a mixture of both.
- Temporal motif counts reveal timescale-specific patterns, including Stack Overflow question-and-answer motifs requiring at least 30 minutes to develop.Outgoing-message star motifs in private messaging rise from 1 to 20 minutes before declining.
2. RELATED WORK
Prior temporal-motif definitions and analyses omit edge ordering, rely on heuristic counting, or impose restrictive consecutiveness assumptions. The paper positions δ-temporal motifs as a broader way to retain short-burst temporal structure.
- Static-network motif research has used motifs to study mechanisms driving complex systems and characterize classes of static networks.
- Prior definitions either omit edge ordering, use heuristic counting algorithms, or require motif edges to be consecutive events for a node.
- The consecutiveness requirement enables fast counting but misses important structures, such as multiple related edges occurring in a short burst at one node.
- Temporal edge ordering in this work is related in spirit to motif-like patterns used to describe how growing networks develop.
3. PRELIMINARIES
The paper formalizes temporal graphs and δ-temporal motifs as ordered timestamped-edge structures, then frames motif counting as identifying ordered edge sequences that match a pattern within a time window.
- A temporal graph is a collection of timestamped directed edges, potentially containing many edges between the same ordered pair of nodes.Ignoring timestamps and duplicate edges yields an induced static graph.
- A δ-temporal motif specifies an edge pattern whose timestamps induce an ordering, with all motif edges constrained to a δ time window.
- An instance must match the motif's edge pattern under a vertex bijection and satisfy the temporal ordering and window condition.
- The counting task seeks the number of ordered length-l edge sequences in the temporal graph that instantiate a given k-node, l-edge motif.
- Enumerating all ordered edge subsets is impractical for large datasets, including one analyzed dataset with over two billion edges.
4. ALGORITHMS
The paper presents a general framework for counting δ-temporal motifs and specialized linear-time algorithms for 3-node, 3-edge stars and faster triangle counting. These methods use time-windowed summary counts and reduce the worst-case dependence on the number of static triangles.
- General counting framework: The general algorithm counts any k-node, l-edge temporal motif by combining static motif structure, temporal edge ordering, and a δ-wide time window.It maintains prefix-pattern counts while streaming through edges and counts instances rather than enumerating them.
- General counting framework: O(|H|^l|S′|) is the general runtime, reducible to O(l^2|S′|) when only contiguous motif subsequences are updated; for fixed small motifs, this is linear in input size.The analysis assumes timestamp-sorted temporal edges and constant-time access to sorted edges between node pairs.
- General counting framework: O(2lm) is the runtime for counting 2-node δ-temporal motifs, making the methodology optimal up to constant factors for small constant l.Here m denotes the number of temporal edges.
- Faster algorithms: O(m) is the runtime for counting 3-node, 3-edge star motifs by processing each center’s adjacent edges in one pass and subtracting 2-node motif counts.Each temporal edge is used twice, once for each endpoint as the center node.
- Faster algorithms: The star and triangle procedures maintain direction-sensitive counts for edges before, after, and around the currently processed edge within the δ time window.The pre_sum, post_sum, and mid_sum counters represent ordered edge pairs used to form motif instances.
- Faster algorithms: The triangle method assigns each triangle to its densest node pair and simultaneously counts adjacent triangles, reducing worst-case dependence from O(mτ) to O(m√τ).The resulting worst-case bound is O(TriEnum + m√τ), where τ is the number of static triangles.
5. EXPERIMENTS
The experiments apply temporal-motif counting across communication and other datasets, revealing domain-specific communication patterns, time-scale effects, and scalable algorithm performance.
- Empirical observations of motif counts: Motif counts distinguish communication domains: blocking behavior dominates Facebook wall posts and SMS, whereas non-blocking behavior prevails in email.Blocking motifs involve repeated exchanges between two nodes; non-blocking motifs involve messages from one source to different destinations.
- Empirical observations of motif counts: 90% of relative motif-count variance is explained with fewer principal components for datasets from the same domain.This indicates that datasets within the same domain have more similar motif-count profiles.
- Empirical observations of motif counts: Switching among non-blocking motifs is least common on Stack Overflow and most common in email.The passage attributes this contrast to differences in the cost of switching targets and peer engagement.
- Empirical observations of motif counts: On Stack Overflow, some motif patterns become relatively more common after 30 minutes, while others increase only after 30 minutes or 1800 seconds.Counts are compared across the intervals [0, 60], (60, 300], (300, 1800], and (1800, 3600] seconds.
- Empirical observations of motif counts: In COLLEGEMSG, outgoing-message star motif counts rise from roughly 1 to 20 minutes and then decline.After 5 minutes, motifs with one target switch grow faster than the motif with two target switches.
- Algorithm scalability: Triangle-counting speedups range from 1.29x to 56.5x over the general method, while 2-node motifs and 3-node stars scale linearly with input size.On PHONECALL-ME, all methods finish in less than 3.5 hours for two billion edges when executed sequentially.
6. DISCUSSION
The paper presents δ-temporal motifs and counting algorithms as tools for analyzing temporal networks, while identifying extensions needed for more complex motifs, enumeration, theory, and null-model analysis.
- δ-temporal network motifs provide a tool for analyzing temporal networks and reveal structural patterns across diverse datasets.
- The general framework counts instances of any temporal motif, while faster algorithms target 3-node, 3-edge star and triangle motifs.
- The fast algorithms count motif instances but do not enumerate them, leaving temporal motif enumeration as an additional algorithmic challenge.
- The authors expect their techniques to extend to more complex temporal motifs and identify lower bounds for temporal motif counting as an open theoretical question.
- Motif counts can be evaluated against null models, and the algorithms can accelerate these computations across many randomized networks.