PaperlayerView exact revision on arXiv

Source-linked AI summary

Modern temporal network theory: A colloquium

Petter Holme

arXiv:1508.01303v3physics.soc-phcs.SI

TL;DR

Temporal networks add interaction timing to network representations, potentially improving prediction and mechanistic understanding, but require methods beyond those for static networks. This colloquium reviews methods, models, and applications for temporal networks, while identifying future challenges and research directions.

  • Problem

    Static network representations omit interaction timing, although including temporal information can improve predictive accuracy and mechanistic understanding while making existing methods inapplicable or requiring non-trivial generalizations.

  • Method

    The colloquium provides a general overview of temporal-network methods, modeled systems, and research questions, focusing on developments after a prior review and excluding several adjacent network topics.

  • Results

    The review synthesizes temporal-network representations, analysis methods, randomization techniques, epidemic and contagion models, and findings on how temporal structure affects spreading and social balance.

  • Takeaways & Limitations

    Temporal-network analysis remains data-driven and computationally challenging, with meaningful future opportunities in discovering empirical temporal structures and extending results to larger populations.

  • Takeaways & Limitations

    Results from empirical temporal-network data may not generalize reliably to larger populations because available background networks can be coarsely modeled and extrapolation methods remain unevaluated.

Abstract

from arXiv · show

The power of any kind of network approach lies in the ability to simplify a complex system so that one can better understand its function as a whole. Sometimes it is beneficial, however, to include more information than in a simple graph of only nodes and links. Adding information about times of interactions can make predictions and mechanistic understanding more accurate. The drawback, however, is that there are not so many methods available, partly because temporal networks is a relatively young field, partly because it more difficult to develop such methods compared to for static networks. In this colloquium, we review the methods to analyze and model temporal networks and processes taking place on them, focusing mainly on the last three years. This includes the spreading of infectious disease, opinions, rumors, in social networks; information packets in computer networks; various types of signaling in biology, and more. We also discuss future directions.

1 Introduction

Temporal networks extend static graphs by recording when interactions occur, potentially improving prediction and mechanistic understanding while making analysis substantially harder. This colloquium surveys the field’s methods, applications, terminology, and scope.

  • 1 Introduction: Temporal networks encode interaction times in addition to pairwise connectivity, preserving information that can improve prediction and mechanistic understanding.The added temporal information also makes many static-network methods inapplicable or requires non-trivial generalization.
  • 1 Introduction: Temporal-network mathematics differs fundamentally from static-network mathematics because contacts are time-ordered and need not compose transitively.A temporal network therefore cannot be represented as a simple graph without losing information or changing node meanings.
  • 1 Introduction: The field is highly interdisciplinary, spanning computer science, physics, mathematics, engineering, social science, medicine, biology, and systems ranging from farms to scientific citations.This breadth has accelerated development but also encouraged parallel invention and terminological inconsistency.
  • 1 Introduction: The colloquium provides a general overview of temporal-network methods, modeled systems, and research questions, focusing on developments after the authors’ earlier review.It excludes network-evolution studies, purely algorithmic papers aimed outside real-system understanding, and gives limited attention to adaptive networks.

2 Systems that can be modeled as temporal networks

Temporal-network models apply wherever pairwise interactions have meaningful timing, encompassing human and animal proximity, communication, transport, biology, economics, neuroscience, and distributed computing. Their practical usefulness depends on temporal and topological structure affecting dynamics on comparable timescales.

  • Systems that can be modeled as temporal networks: Any system with pairwise interactions and time information can in principle be modeled as a temporal network.Practical usefulness generally requires structure in time and topology that affects dynamics on the network.
  • Human proximity networks: Human proximity networks trade measurement precision against population scale: high-resolution sensing is costly, whereas WiFi, Bluetooth, bus, and taxi data cover larger populations more coarsely.The cited examples include RFID and infrared sensing, campus WiFi, Bluetooth scanners, Singapore buses, and Shanghai taxis.
  • Applications: Temporal-network applications include animal populations, human communication, collaboration, citation, economic, and neuroscience networks.Examples range from livestock, zebras, and ants to mobile calls, email, trade, Bitcoin, credit cards, ship chartering, and fMRI-derived correlations.
  • Distributed computing: Distributed-computing studies use temporal-network concepts to analyze computation, network construction, and desirable properties under device dynamics or churn.The reviewed work is predominantly theoretical, and the authors identify empirical studies of distributed systems as an interesting direction.

3 Representations of temporal networks

Temporal networks admit multiple representations whose suitability depends on the data, temporal resolution, and process being studied. Lossless forms preserve all information, while lossy reductions simplify analysis by discarding or aggregating temporal detail.

  • Representations of temporal networks: Representation choice depends on data meaning, accuracy, supported dynamics, and the researcher’s conceptualization of the system.The choice encodes assumptions that are often insufficiently motivated, so the paper distinguishes multiple graphical and data-structural approaches.
  • Lossless representations: Lossless representations are theoretically equivalent and preserve all temporal-network information, while shaping how researchers conceptualize the network.Examples include graph sequences, time-node graphs, contact timelines, and other equivalent encodings.
  • Contact sequences: Contact sequences are computationally practical lists of node pairs and timestamps but provide little visual intuition about system function or network processes.They typically use three or four columns and are common in empirical datasets.
  • Graph sequences or multilayer networks: Graph sequences can reuse static-network tools, but high-resolution or instantaneous contacts can make them sparse, misleading, or incompatible with direct static-network reasoning.For disease spreading, assuming multiple contacts can be traversed within one time step may be unreasonable.
  • Lossy representations: Lossy representations aggregate or transform contacts into weighted, time-windowed, reachability, or link-turnover graphs, with usefulness depending on the process studied.For weighted graphs, contact contributions may be exponentially weighted according to their timing relative to spreading and a process-timescale parameter.

4 Temporal network structure

Temporal-network structure is defined by information carried in time-dependent interactions, not simply by static topology. The field adapts static-network measures while confronting the absence of universally established temporal structures.

  • Temporal network structure: Temporal-network structure comprises information that can reveal network evolution and the behavior of systems operating on the network.The paper treats measuring this structure as a central network-science task.
  • Temporal network structure: Topology usually denotes static structure, so temporal-network analysis instead examines how topology measures function when interactions are time resolved.The colloquium positions this work alongside established static-network theory.
  • Temporal structures: Unlike static networks’ widely studied scale-free degree distributions, ubiquitous temporal structures have not yet been identified and may not exist.This uncertainty has directed temporal-network research along a somewhat different path from static network theory.
  • Connections to static theory: Many studies generalize static topology measures or explain accumulated-contact structure through temporal mechanisms.The paper identifies distance, centrality, and community methods as major areas where static-network theory enters temporal-network research.

4.2 Temporal structure

Temporal structure can be characterized across multiple time scales, from interevent intervals and burstiness to node or link lifetimes and whole-network growth or decay. Empirical temporal networks often exhibit heterogeneous activity patterns that complicate aggregation and estimation.

  • Interevent time distributions measure the frequency of elapsed times between successive events, with exponential distributions arising from independent uniformly distributed events.
  • Burstiness and interevent time statistics: Link-level burstiness is difficult to estimate because links often have few contacts, while contact counts per link can be fat-tailed.
  • Burstiness and interevent time statistics: Concatenating interevent times does not resolve the problem that individual nodes and links can follow distinct temporal patterns.
  • Burstiness and interevent time statistics: Node-level burstiness is most informative when contacts identify distinct senders and receivers, such as in email data.
  • Temporal structure also includes the elapsed time between first and last contact, which can represent the observed lifetime of a link or node.
  • At the network scale, temporal data sets may remain broadly active throughout sampling or exhibit overall growth in nodes, links, and activity.

4.3 Paths and generalized distances

Temporal networks generalize paths and distances by enforcing contact order and timing, producing measures such as latency, temporal distance, and contact-based path length. These measures support temporal centrality, but reachability gaps and time projection create important interpretive choices.

  • Paths and generalized distances: Latency looks backward from time t, whereas temporal distance τ(i, j, t) measures the earliest arrival from i to j along a time-respecting path starting at t.
  • Paths and generalized distances: Temporal distances can become infinite near the ends of an empirical observation window, requiring boundary conditions or separate treatment of reachability and travel time.
  • Paths and generalized distances: Temporal path length may be defined by the number of contacts rather than elapsed time.
  • Paths and generalized distances: Generalized distances can be computed by simulating SI spreading with 100% transmission probability or by processing contacts chronologically for hop counts.
  • Centrality measures: Static centrality measures can be adapted by following contacts instead of links or replacing graph distance with latency or temporal distance, making centrality time-dependent.
  • Centrality measures: Closeness centrality is aggravated by unreachable node pairs, while averaging inverse distances offers a workaround with less intuitive interpretation.The workaround combines component size and within-component temporal distance in an arbitrary statistic.
  • Centrality measures: Other temporal centralities include random-walk and communicability measures, control centrality, activity participation, temporal coverage, and contact importance.
  • Centrality measures: Temporal ranking methods can incorporate incomplete time-annotated match data while weighting newer results more heavily in ordering players or teams.

4.5 Controllability

Structural controllability extends a static-network concept to temporal networks under simple node dynamics and assumptions that exclude delays and memory effects.

  • Controllability: Structural controllability assumes input and output terminals connected through a network whose node dynamics are proportional or monotonically related to inputs.
  • Controllability: The framework assumes no time delays and no more complex dynamic effects, such as memory.

4.6 Other graph invariants

Graph invariants map network structure to a single label-independent number; temporal-network work has introduced comparatively few measures combining topology and time. Examples include reachability and betweenness preference, which characterize temporal accessibility and time-respecting paths.

  • Other graph invariants: A graph invariant is a function that maps a graph, regardless of node labeling, to one number.
  • Other graph invariants: Static graph invariants include node and link counts, clustering coefficient, and assortativity.
  • Other graph invariants: Temporal-network studies have proposed relatively few functions that characterize topology and timing jointly.
  • Other graph invariants: Reachability measures the average number of nodes reachable from a random node at a random time within the sampling interval.
  • Other graph invariants: Betweenness preference uses information-theoretic manipulations of time-respecting paths to quantify their temporal predictability.

4.7 Entropy measures

Entropy measures quantify randomness in temporal-network contacts and signals, with lower entropy indicating greater regularity and easier prediction.

  • Entropy measures capture the randomness of contacts in a temporal network.
  • Low entropy indicates substantial signal regularity and greater predictability.
  • Knowing a current face-to-face conversation partner can reduce uncertainty about the next partner.

4.8 Persistent patterns

Persistent patterns in temporal networks are studied through link and node stability, temporal connectivity, and recurring or cyclic activity patterns.

  • Link persistence can be measured with the autocorrelation function of links in temporal networks.
  • Node loyalty is the Jaccard index between a node’s neighborhoods at consecutive time steps and helps characterize roles in disease dynamics.
  • Loyalty in socio-economic systems has been linked to heavy-tailed durations of business contacts.
  • Studies of empirical temporal networks examine cyclic patterns, their strength, and methods for removing them when changing background activity is undesirable.

4.10 Motifs

Temporal-network motif methods extend static motif analysis by incorporating time windows, event ordering, and the assembly of motifs across time.

  • Temporal motif analyses consider contacts connecting groups of individuals within a time window of size ∆t.
  • Temporal graphlets are equivalence classes of ∆t-causal subgraphs defined by the order of events.
  • Other approaches study how static network motifs are assembled or define motifs between consecutive time steps in bipartite networks.
  • Temporal graphlets are proposed as building blocks for temporal networks.

4.11 Mesoscale structures

Mesoscale methods divide temporal networks into evolving groups, using community tracking, persistence, factorization, or stochastic block models, while important challenges remain for sparse networks.

  • Mesoscale structures: Mesoscale analysis partitions a network into groups covering all nodes without requiring a particular relative group shape.
  • Temporal communities: Temporal community detection can separate time slices and merge communities across consecutive times using overlap-based matching.
  • Temporal communities: Index-matching approaches can produce pathological interpretations when community sizes change sharply between time steps.
  • Temporal communities: Temporal group-dynamics methods include time-decayed links and costs for leaving, changing, or starting groups.
  • Temporal communities: Alternative approaches use persistence across time-sliced networks, tensor factorization, or dynamic stochastic block models to identify temporal communities.
  • Future directions: A remaining direction is community detection directly on dynamic-system flows without aggregating sparse temporal networks into time windows.

4.12 Time scales

Temporal-network timescales are harder to reason about than static-network timescales because network evolution and processes on the network can interact. Researchers therefore define them using community structure, dynamics, information-theoretic windows, or node waiting times.

  • Temporal-network timescale reasoning becomes more complex than ordinary decay-based reasoning because network evolution interacts with processes occurring on the network.
  • A temporal network typically evolves on timescales comparable to or shorter than dynamic processes such as epidemics or Internet traffic.
  • Social-media spreading can mingle with network-activity timescales when the follower network changes in response to the spreading dynamics.
  • Temporal community detection defines timescales through windows containing dense within-community and sparse between-community connectivity.
  • Researchers also infer timescales from random walks, spreading processes, compressibility, link prediction, or comparisons between node waiting times and edge dynamics.

5 Manipulating, predicting and generating temporal networks

The paper presents randomization, boundary-condition, and generative approaches for analyzing and modeling temporal networks. These methods isolate temporal or topological structures, but their interpretation and extrapolation depend on preserved features, sampling assumptions, and model limitations.

  • 5.1 Randomization: Randomization compares dynamics on empirical data with dynamics after destroying selected temporal structures, revealing whether those structures accelerate or slow processes.
  • 5.1 Randomization: Shuffled timestamps preserve node-pair contact counts and overall temporal activity while randomizing event order; random-time schemes additionally remove periodic patterns.
  • 5.1 Randomization: In one data set, event order speeds SI spreading, whereas mobile-phone data show that contact-order structure slows spreading.
  • 5.1 Randomization: Randomized rewiring can remove topological structure except the accumulated degree sequence while preserving contact times and interevent-time statistics.
  • 5.1 Randomization: Some poor-man's reference models produce one transformed temporal network rather than an ensemble, and may violate the maximum-entropy basis of randomized models.
  • 5.2 Boundary conditions and extrapolations: Extending empirical results to larger populations remains difficult because survey-based backgrounds are coarse and naive finite-size scaling becomes increasingly biased for smaller subnetworks.

6 Dynamic systems on temporal networks

Temporal networks support dynamic processes whose outcomes depend on both topology and contact timing, including epidemics, walks, threshold adoption, social balance, and percolation. The reviewed studies show that temporal structure can alter spreading thresholds and rates, while effects depend on the dynamical model.

  • Temporal-network dynamics include walks, infectious-disease spreading, threshold adoption, social balance, and percolation.These processes use contact timing as part of the system dynamics or its analysis.
  • Epidemic models: Constant-duration epidemic stages are more realistic than exponentially distributed durations, while also making programs faster and sometimes more compact.The traditional alternative assumes independent time steps and exponential state durations.
  • Epidemic models: Temporal-network studies find that structure does not have a general relationship with spreading statistics across different compartmental models.Memory can increase the epidemic threshold for SIR but lower it for SIS, and strong links can impede SIR spreading while prolonging SIS outbreaks.
  • Epidemic models: For epidemic spreading, the observation window should begin near outbreak onset and end on the spreading time scale.Temporal information also affects how predictable outbreak sizes are as a function of when the outbreak is observed.
  • Opinion and information spreading: Threshold models use recent contacts through moving windows or exponential decay, and burstiness can slow epidemic-type spreading while accelerating threshold spreading.The reviewed threshold studies attribute acceleration to bursts helping contagion overcome adoption thresholds.
  • Opinion and information spreading: Temporal fluctuations slow the time to global social balance in a model where interaction timing is given and link signs evolve.The model concerns positive and negative social links and their evolution toward a more balanced state.
  • Percolation, error tolerance and attack vulnerability: Percolation research on temporal networks remains limited, with studies mapping SIS or spreading processes to percolation problems.One study tests an SIS-to-percolation mapping on a generative temporal-network model.

7 Discussion and future outlook

The field has expanded rapidly but still lacks a settled set of temporal structures, intuitive visualization methods, and mature ways to scale empirical findings. The authors anticipate divergence from static network science and growth into new application areas and richer network settings.

  • Discussion: Temporal-network research has evolved tremendously, while meaningful structures beyond static-network patterns remain to be identified.The authors specifically point to possible mesoscopic structures that are neither cohesive subgraphs, core-periphery structures, nor bursts.
  • Future outlook: The field is expected to diverge further from static network science because no fundamental temporal statistic is yet obvious.Interevent times have received substantial attention, but the authors do not identify an equivalent universal statistic.
  • Future outlook: Temporal-network methods are anticipated to spread into neuroscience, animal behavioral science, and ecology.The authors note that neuroscience has already begun adopting these methods and expect more work in the other areas.
  • Future outlook: Future research may add link types or spatial information, producing temporal multiplex, multilayer, or spatiotemporal networks.The authors describe these extensions as natural ways to generate new research questions.
  • Future outlook: Visualization remains a priority because temporal networks lack static networks' intuitive visual component.The authors expect better methods to preserve at least some time-respecting paths, potentially without placing time on the horizontal axis.
  • Future outlook: A further open problem is extrapolating spreading results from empirical networks to larger populations.Suggested directions include resampling original data or scaling up study results.
Loading 1508.01303v3…