Source-linked AI summary
Graph Metrics for Temporal Networks
Vincenzo Nicosia, John Tang, Cecilia Mascolo, Mirco Musolesi, Giovanni Russo, Vito Latora
TL;DR
Temporal interactions make static adjacency inadequate because reachability and causality depend on link timing. This chapter formalizes time-varying representations and extends graph metrics to temporal connectivity, distances, centrality, motifs, and modularity, while noting that temporal community metrics remain open and definitions are not fully unified.
Problem
Static graph concepts and metrics must be redefined or extended because temporal ordering affects adjacency, reachability, and causality.
Method
The chapter reviews time-varying graph representations and develops definitions and extensions for walks, components, distances, centralities, motifs, and modularity.
Results
The chapter presents fundamental metrics for characterising time-varying graphs, including temporal connectivity, distance, centrality, motifs, and modularity.
Takeaways & Limitations
Temporal-network metrics provide an alternative framework for studying time-evolving systems while preserving information about temporal correlations and causality.
Takeaways & Limitations
Definitions and approaches for temporal communities and modularity remain not fully consistent, and suitable metrics remain an open research area.
Abstract
from arXiv · showhide
Temporal networks, i.e., networks in which the interactions among a set of elementary units change over time, can be modelled in terms of time-varying graphs, which are time-ordered sequences of graphs over a set of nodes. In such graphs, the concepts of node adjacency and reachability crucially depend on the exact temporal ordering of the links. Consequently, all the concepts and metrics proposed and used for the characterisation of static complex networks have to be redefined or appropriately extended to time-varying graphs, in order to take into account the effects of time ordering on causality. In this chapter we discuss how to represent temporal networks and we review the definitions of walks, paths, connectedness and connected components valid for graphs in which the links fluctuate over time. We then focus on temporal node-node distance, and we discuss how to characterise link persistence and the temporal small-world behaviour in this class of networks. Finally, we discuss the extension of classic centrality measures, including closeness, betweenness and spectral centrality, to the case of time-varying graphs, and we review the work on temporal motifs analysis and the definition of modularity for temporal graphs.
1 Introduction
Real network relationships often fluctuate over time, making static adjacency an oversimplification. This chapter therefore develops concepts and metrics for time-varying graphs that account for temporal correlations and causality.
- Chapter scope: Temporal-network analysis extends classic graph concepts because interactions among elementary units can change across time.Graph nodes represent units and edges represent interactions.
- Motivation: Real network relationships are rarely persistent, with social, brain, communication, and transportation interactions fluctuating over time.These dynamics include finite, intermittent, recurrent, bursty, and task-dependent interactions.
- Motivation: Static adjacency can oversimplify temporal systems because it ignores the ordering and fluctuation of interactions.Temporal information is needed to analyze causality and temporal correlations.
- Chapter scope: The chapter introduces representations, reachability, connectedness, temporal components, distance, efficiency, clustering, and small-world behavior for time-varying graphs.It also addresses temporal extensions of centrality, motifs, and modularity.
2 Representing Temporal Networks
Temporal networks can be represented through contacts, aggregated static graphs, or time-varying sequences of snapshots. Static aggregation preserves selected contact summaries but loses temporal ordering, whereas snapshot windows retain temporal structure at a chosen scale.
- Contact representation: A contact is represented as c = (i, j,t,δt), recording its endpoints, start time, and duration within [0,T].Contacts may recur between the same nodes, and the example contains seven contacts among five nodes over T = 240 minutes.
- Aggregated static graphs: Aggregated static graphs flatten all contacts between each node pair into one edge, using binary adjacency or weights based on contact number, duration, or frequency.Figure 2 contrasts unweighted aggregation with weights for contact counts and total durations.
- Aggregated static graphs: Binary aggregation discards contact number, frequency, and duration, while assigning identical weights can misrepresent heterogeneous real interactions.The text notes that call counts and durations can fluctuate substantially and follow power-law-like distributions.
- Aggregated static graphs: Both unweighted and weighted aggregations treat links as persistently available, overestimating walks and paths while underestimating effective distances.For example, an interaction limited to the observation period’s beginning cannot support direct communication later, despite appearing as an edge.
- Time-varying graphs: Time-varying graphs include time as an additional dimension by constructing snapshots from contacts overlapping finite windows [t,t + ∆t].Successive non-overlapping windows produce a time-ordered graph sequence, with window size controlling temporal resolution.
- Time-varying graphs: As ∆t decreases, snapshots become more temporally resolved but are more likely to contain no edges; setting ∆t = T recovers an unweighted aggregated graph.The example uses four snapshots at ∆t = 60min and eight at ∆t = 30min.
3 Reachability, Connectedness and Components
Temporal reachability depends on edge ordering, so walks, connectedness, and components must be reformulated for time-varying graphs. These temporal definitions reveal structural differences that aggregated graphs can conceal, while component identification introduces computational difficulty.
- 3.1 Time-respecting Walks and Paths: Temporal walks require an ordered sequence of edges traversed at strictly increasing times, making reachability time-dependent.A static path may fail temporally when the necessary contacts occur in the wrong order.
- 3.2 Temporal Connectedness and Node Components: Temporal connectedness from i to j is generally directional because a time-respecting path from i to j does not guarantee one from j to i.Strong connectedness requires temporal reachability in both directions.
- 3.2 Temporal Connectedness and Node Components: Temporal strong and weak connectedness are reflexive and symmetric but not transitive, so pairwise relations do not directly define components.Temporal components are instead defined as sets whose nodes are mutually connected, enforcing transitivity by construction.
- 3.2 Temporal Connectedness and Node Components: Strong connectedness persists when the temporal window is enlarged, but the reverse implication does not generally hold.At the limiting window ∆t = T, temporal connectedness is consistent with the corresponding aggregated static graph.
- 3.2 Temporal Connectedness and Node Components: Temporal node components can be heterogeneous and much smaller than components in aggregated graphs, which may misleadingly make all nodes mutually reachable.In the example, node 3 cannot reach node 5 temporally, whereas the corresponding aggregated graph gives every node the same out-component containing all nodes.
- 3.3 Graph Components and Affine Graphs: Finding temporal strongly connected components is equivalent to partitioning the affine graph into a minimum number of disjoint maximal cliques, an NP-complete problem.For large graphs, exact solution is therefore generally impractical; aggregated representations can also yield substantially larger components.
4 Distance, Efficiency and Temporal Clustering
Temporal distance in time-varying graphs depends on both path topology and link ordering, while efficiency and persistence measures address disconnectedness and evolving edge structure.
- Temporal Distance and Efficiency: Temporal paths have distinct topological length and temporal duration, so geodesic distance must account for link ordering.Topological length counts traversed edges; temporal length spans the interval between the first and last contact.
- Temporal Distance and Efficiency: Temporal distance is the duration of the shortest temporal path, and the characteristic temporal path length averages it over node pairs.The temporal shortest path minimizes temporal length, rather than necessarily minimizing hops.
- Temporal Distance and Efficiency: Many temporally disconnected pairs make characteristic temporal path length diverge, motivating temporal global efficiency as a finite alternative.Temporal global efficiency generalizes static global efficiency and has been used to quantify temporal-graph robustness.
- Edge Persistence and Clustering: Temporal clustering measures whether edges persist across consecutive time windows, extending local clustering with temporal information.The average topological overlap estimates the probability that an edge from a node to a neighbor persists between windows.
- Edge Persistence and Clustering: The temporal-correlation coefficient summarizes the average probability that an edge persists across two consecutive snapshots.It equals 1 when every snapshot has the same edge configuration and 0 when no edge recurs in adjacent snapshots.
- Edge Persistence and Clustering: Table 1 compares temporal correlation, characteristic temporal path length, and efficiency with values from snapshot-reshuffled graphs across brain, interaction, and Facebook networks.The reshuffling removes temporal correlations while retaining average node connectivity and snapshot configurations.
5 Betweenness, Closeness and Spectral Centrality
Temporal centrality measures adapt shortest-path and communicability ideas to time-varying graphs, capturing timing, waiting, and temporal walks in identifying influential nodes.
- Betweenness and Closeness Centrality: Waiting time can refine temporal betweenness because longer intervals before forwarding increase the probability that a message is lost if an intermediary is removed.Temporal betweenness at a time accounts for paths whose next edge becomes available later.
- Betweenness and Closeness Centrality: Temporal closeness replaces static distance with temporal shortest-path length, while temporal betweenness counts temporal shortest paths traversing a node.These extensions preserve the shortest-path basis of the corresponding static centrality measures.
- Betweenness and Closeness Centrality: In ENRON communication data, traders ranked highly by temporal centrality, whereas aggregated-graph centrality favored a secretary and managing director.The different rankings were important for information-spreading outcomes.
- Betweenness and Closeness Centrality: Starting spreading processes from nodes with highest temporal closeness reached more nodes and took less time than starting from nodes with highest static closeness.This comparison shows that temporal ordering changes which nodes are identified as effective spreaders.
- Spectral Centrality and Communicability: Temporal Katz-style communicability sums products of adjacency matrices over increasing snapshot sequences to count temporal walks.The construction requires α < min_tm ρ(A(tm)) for convergence.
- Spectral Centrality and Communicability: Broadcast centrality measures how well a node reaches others, while receive communicability measures how well it is reached from others.Both have been reported as useful for locating influential spreaders in time-evolving communication networks.
6 Meso-scale Structures
The chapter extends meso-scale structures from static graphs to temporal networks by requiring motifs and communities to respect temporal ordering. It also presents multi-slice modularity while identifying time-inversion invariance as a limitation for temporal community metrics.
- 6.1 Temporal Motifs: Δτ-adjacency links feasible contacts sharing a node when the gap between the first contact’s end and the second’s start is at most Δτ.For contacts ordered by start times, the condition is 0 ≤ t_b − t_a − δt_a ≤ Δτ.
- 6.1 Temporal Motifs: The temporal-motif construction restricts analysis to valid subgraphs, excluding cases where an intervening contact breaks consecutiveness.Figure 5 contrasts an invalid three-node subgraph with a valid one and its associated motif.
- 6.1 Temporal Motifs: Temporal motifs are classes of isomorphic valid temporal subgraphs that share both topology and the same contact order.Validity requires all Δτ-adjacent contacts involving a node to be consecutive.
- 6.2 Temporal Communities and Modularity: A time-varying graph can be represented as a multi-slice graph by connecting each node’s instances in neighboring snapshots with inter-slice edges.This representation supports extending modularity through the connection between modularity and random-walk stability.
- 6.2 Temporal Communities and Modularity: Multi-slice modularity combines within-slice modularity with inter-slice connections, and standard modularity-optimisation methods can search for the best partition.Within-slice terms use adjacency and resolution parameters, while inter-slice weights account for links between node instances across slices.
7 Final Remarks
Temporal-network analysis has produced encouraging results, but the field remains early and lacks unified notation and fully consistent definitions. Important open problems include temporal-community detection and analytical links between temporal structure and dynamics.
- 7 Final Remarks: Temporal-network descriptions and structural analyses remain in their infancy despite encouraging results across different real systems.The chapter presents complex-network theory as a flexible framework for characterising time-evolving systems.
- 7 Final Remarks: Open problems include defining appropriate methods for detecting temporal communities and assessing how time-varying structure affects spreading, synchronisation, and evolutionary games.The chapter identifies analytical methods connecting graph structure to processes occurring on the graph as an unresolved need.
- 7 Final Remarks: The field lacks unified notation and a fully consistent set of definitions and approaches, although existing metrics provide an alternative to standard methods.The chapter presents these concepts as a contribution to understanding complex systems more generally.