Source-linked AI summary
Time-Varying Graphs and Dynamic Networks
Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro
TL;DR
Research on dynamic communication, mobility, and real-world networks has produced related concepts and fragmented formalisms for systems whose topology changes over time. The paper unifies these ideas as time-varying graphs (TVGs), classifies TVGs, and develops ways to study evolving network properties, including results under specific connectivity conditions.
Problem
Related insights across dynamic networks are expressed through fragmented formalisms despite sharing concepts and time-varying topology.
Method
The paper integrates existing models, concepts, and results into the TVG formalism, develops a hierarchical classification, and represents temporal interactions through footprints.
Results
The framework expresses both shared and area-specific concepts, organizes TVGs by significant properties, and derives network-property implications for different classes.
Takeaways & Limitations
Using a common TVG formalism should enable results to transfer between application areas and support analysis of network-property evolution at suitable temporal scales.
Takeaways & Limitations
Some results depend on specific connectivity assumptions, such as time-bounded edge recurrence or T-interval connectivity.
Abstract
from arXiv · showhide
The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems -- delay-tolerant networks, opportunistic-mobility networks, social networks -- obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe; and the formal models proposed so far to express some specific concepts are components of a larger formal description of this universe. The main contribution of this paper is to integrate the vast collection of concepts, formalisms, and results found in the literature into a unified framework, which we call TVG (for time-varying graphs). Using this framework, it is possible to express directly in the same formalism not only the concepts common to all those different areas, but also those specific to each. Based on this definitional work, employing both existing results and original observations, we present a hierarchical classification of TVGs; each class corresponds to a significant property examined in the distributed computing literature. We then examine how TVGs can be used to study the evolution of network properties, and propose different techniques, depending on whether the indicators for these properties are a-temporal (as in the majority of existing studies) or temporal. Finally, we briefly discuss the introduction of randomness in TVGs.
1 Introduction
The paper unifies related concepts from dynamic-network research into the TVG framework. It uses this framework to classify network dynamics and study distributed computing and evolving network properties.
- Research on delay-tolerant, opportunistic-mobility, and complex networks has produced closely related concepts despite differing application areas.
- TVGs integrate existing models, concepts, and results into one formalism covering both cross-area and area-specific concepts.The framework is intended to support transfer of results between application areas.
- The paper presents a hierarchical classification of TVGs based on network-dynamics properties relevant to distributed computing.The classification relates class inclusion to feasibility, protocols, impossibility results, and lower bounds.
- TVGs support dynamic-network analysis through trace verification, temporal concepts, and techniques for studying coarse-grain evolution.The proposed techniques distinguish a-temporal indicators from temporal indicators such as journeys, temporal distance, and connectivity.
- The paper also discusses randomness in TVGs and integrates the reviewed material within a unified formalism.
2 Contexts
The paper situates TVGs across communication, mobility, and complex-network research. These settings share temporal concerns involving paths, distance, connectivity, and the analysis of evolving network structure.
- 2.1 Delay-Tolerant Networks: Delay-tolerant networks may lack end-to-end routes at any instant but can support communication over time through store-carry-forward mechanisms.
- 2.1 Delay-Tolerant Networks: Research on delay-tolerant networks has developed routing and broadcast techniques based on schedules, probabilities, delays, and encounters.
- 2.2 Opportunistic-Mobility Networks: Opportunistic-mobility networks use mobile carriers or ferries to transport external agents over mobility-created networks.
- 2.2 Opportunistic-Mobility Networks: Deterministic periodic carrier trajectories support routing, route design, exploration, and broadcast-structure construction.Examples include public transport, low Earth orbit satellites, and security-guard tours.
- 2.3 Real-World Complex Networks: Complex-network research seeks mathematical models that capture and reproduce properties observed in real dynamic networks.Examples include shrinking diameter, community formation, and inequalities.
- 2.3 Real-World Complex Networks: Across these areas, temporal definitions of paths, distance, and connectivity recur as common research concepts.
3 Time-Varying Graphs
A time-varying graph represents dynamic systems whose relations evolve over time, using time-dependent edge presence and latency. The formalism spans domains such as transportation, communication, and social networks, while allowing domain-specific restrictions.
- A TVG models entities, time-varying relations, and relation properties through node and edge sets, a label alphabet, a lifetime, presence, and latency functions.The presence function indicates edge availability, while latency gives traversal time from a starting date.
- Node presence and latency functions extend the model to systems where node availability or local processing time varies over time.
- TVGs can describe transportation, communication, complex, and social-network scenarios despite differences in what an edge represents.
- Transportation edges may be directed or multiple, have punctual availability, and exhibit edge- and date-dependent latency.
- Communication-history edges between moving nodes may be undirected and carry media-specific properties such as range, bandwidth, latency, or energy consumption.
- The formalism supports restrictions such as constant latency or simplified relations when a context requires a narrower model.
4 Definitions of TVG concepts
This section unifies independently developed dynamic-network concepts within TVGs and describes several complementary views of network evolution. The underlying graph captures possible relations while temporal structure records when those relations appear and disappear.
- The section transposes and generalizes dynamic-network concepts that emerged independently across scientific areas into the TVG framework.
- The underlying graph is a static footprint formed by flattening time and retaining node pairs that have relations at some point in the lifetime.
- A TVG may have a connected underlying graph without being connected over time, because temporal ordering can prevent some nodes from reaching one another.
- Edge-centric, vertex-centric, and graph-centric views examine evolution from the perspective of relations, entities, and the entire network.
- An edge’s evolution is represented by its availability dates, appearance dates, disappearance dates, and intervening characteristic dates.
- Node evolution appears as changes in neighborhood sequences at dates when incident edges appear or disappear.
- Global evolution can be represented as a sequence of static graphs at topological-event dates or at discrete time snapshots.
- The underlying graph equals the union of the static graphs in the evolution sequence, and evolving graphs provide a related combinatorial representation.
4.3 Subgraphs of a time-varying graph
TVG subgraphs can restrict vertices or edges classically, or restrict the system’s lifetime to obtain a temporal subgraph. The restricted graph preserves the relevant presence and latency behavior on the new time interval.
- A temporal subgraph restricts the lifetime of a TVG while retaining edges that can be available and completed within the restricted interval.
- The temporal subgraph inherits the original presence and latency functions on its restricted edge and time sets.
- The notation G[ta,tb) denotes restriction to T ∩ [ta,tb), with analogous forms for intervals extending to the beginning or end of the lifetime.
4.4 Journeys
A journey is a time-respecting walk whose edges are available at specified traversal dates and whose successive departures respect traversal latency. Journeys characterize reachability and distinguish topological hops from elapsed time.
- A journey is a sequence of edge-date couples forming a walk, with each edge available at departure and each next departure no earlier than the previous traversal’s completion.
- Communication networks may additionally require an edge to remain present throughout message delivery.
- A journey has departure and arrival dates, a topological length measured in hops, and a temporal length measured by end-to-end duration.
- Reachability is directional in time: a journey from u to v does not imply a journey from v to u, and the reachable nodes form u’s horizon.
4.5 Distance
The paper distinguishes topological, temporal, foremost, fastest, and shortest journey measures for time-varying graphs, linking them to temporal views and prior network applications.
- The section frames distance as a choice between hop-based and time-based measurements of journeys in a time-varying graph.Both definitions restrict candidate journeys to those departing at or after the reference time t.
- Topological distance minimizes journey hops, while temporal distance minimizes arrival time for journeys departing no earlier than t.A journey achieving topological distance is shortest; one achieving temporal distance is foremost.
- A fastest journey minimizes temporal length over all possible departure times at or after t.Fastest differs from foremost because its departure time may be later than t if that reduces total journey duration.
- Centralized algorithms have been provided for computing shortest, fastest, and foremost journeys in delay-tolerant networks with complete knowledge of G.Temporal distance and related concepts have also been used in social-network analysis and vehicular warning delivery.
- Temporal view records the latest time at which a message received by v at time t could have been emitted by u.The concept was introduced in social-network analysis and is renamed temporal view here to avoid confusion with distributed-computing terminology.
4.6 Other temporal concepts
Beyond distance, the paper introduces temporal concepts for reachability, propagation, and journey structure, extending static-graph notions to dynamic settings.
- The paper limits its list because definitions built from temporal concepts could grow indefinitely, selecting concepts broad enough for multiple analytical contexts.
- Temporal eccentricity is the maximum temporal distance from a node to any other node, and temporal diameter is the maximum temporal eccentricity.These concepts measure the longest foremost journey durations across nodes at a given time.
- Dynamic expansion measures how many nodes outside a set V′ can be reached by journeys from V′ during a time interval.It is presented as a dynamic counterpart of node expansion and as the collective horizon of V′.
- Journeys are direct when every next edge is immediately available after the preceding edge's latency, and indirect otherwise.This distinction was exploited by a distributed algorithm for computing temporal distances.
5 TVG Classes
The paper organizes time-varying graphs into a hierarchy based on temporal connectivity and recurrence properties, relating each class to distributed-computing feasibility and complexity.
- TVG Classes: TVG classes are ordered from general to specific assumptions, yielding necessary conditions and impossibility results for distributed computations.The hierarchy unifies existing work on how network dynamics affect distributed-problem feasibility and complexity.
- Connectivity and recurrence: Class 5 requires recurrent connectivity: from every time onward, every node can eventually reach every other node.This class models networks where routing can always be achieved over time and is central to much delay-tolerant-network research.
- Connectivity and recurrence: Underlying-graph connectivity alone does not guarantee connectivity over time because the ordering of topological events matters.Temporal connectivity is necessary for global computation, motivating explicit assumptions in several classes.
- Connectivity and recurrence: Class 6 permits foremost broadcast but not shortest or fastest broadcast, despite recurrent edge connectivity.The three broadcast variants therefore require different temporal-network properties.
- Connectivity and recurrence: Class 7 bounds each edge's recurrence within Δ time units, enabling bounded temporal diameter and shortest broadcast when Δ is known.A Δ-rounded breadth-first strategy minimizes the topological length of journeys.
- Connectivity and recurrence: Class 8 specializes bounded recurrence to periodic edges, supporting reusable foremost broadcast trees modulo the period p.Periodic mobility includes satellites, guards' tours, subways, and buses.
- Connectivity and recurrence: T-interval connectivity provides the same spanning connected subgraph for every T-consecutive time steps and can speed computation by a factor T over Class 9.It has been studied for counting, token dissemination, and distributed functions under adversarial edge schedules.
- Hierarchy and scope: The class inclusions are strict, so each parent class contains TVGs absent from its child class; Class 5 contains all classes with substantial prior work.The unified hierarchy enables comparison of properties, solutions, and algorithms across application contexts.
6 TVG and Network Analysis
TVGs support a posteriori analysis of network traces, including connectivity recognition, temporal reinterpretations of network properties, and coarse-grained evolution of atemporal and temporal indicators.
- Recognizing TVGs: Connected components in evolving graphs require journeys between every node pair, even when contributing edges involve nodes outside the component.The paper also discusses strongly connected, in-components, and out-components as related variants.
- Recognizing TVGs: Transitive closure converts journey reachability into a static graph, enabling connected-component and class-membership checks through graph properties.For connected components, the corresponding node set must form a clique in the transitive-closure graph.
- Temporal Network Properties: Temporal analysis can redefine static concepts such as small-world behavior and fairness using journeys, temporal distance, and temporal eccentricities.Fairness can be defined as the standard deviation of nodes’ temporal eccentricities.
- Temporal Network Properties: Temporal ordering reveals asymmetries hidden by static topology: information travels from a to f in 5–11 days, but from f to a in about one month.Although the network is a line with diameter 5, node a is more temporally central than c and d.
- Evolution of Network Properties: Atemporal indicators can be tracked on static footprints that aggregate interactions within consecutive time windows.Footprints preserve which edges appeared during each window but discard their precise chronology.
- Evolution of Network Properties: Temporal indicators require sequences of shorter TVGs because aggregated footprints may show paths without preserving a journey’s interaction chronology.The paper proposes temporal subgraphs that retain the original interactions within selected windows.
7 Random TVGs
The paper introduces randomness into TVGs through probabilistic edge availability and reviews discrete-time, continuous-time, and Markovian models. These models support analysis of transitions between temporal disconnection and connectivity.
- Random TVG Models: Probabilistic TVGs assign each edge a time-dependent probability of being available, with mobility models providing an application-related source of randomness.The presence function maps edges and times to availability probabilities.
- Random TVG Models: Discrete-time random TVGs use sequences of Erdős–Rényi characteristic graphs in which each edge appears with probability p.The independently sampled characteristic graphs do not capture persistence between successive times.
- Random TVG Models: Edge-Markovian evolving graphs model temporal dependence by making edge presence in the next graph depend on its current state.Their transition parameters p and q are called birth and death rates, respectively.
- Random TVG Models: Continuous-time random TVGs model each edge’s appearances with a Poisson process parameterized by λ.This provides a continuous-time alternative to discrete-time characteristic-graph models.
- Applications: Random TVGs were used to characterize phase transitions between no connectivity and connectivity over time as network size, time-window duration, and journey constraints vary.
8 Research Problems and Directions
The paper identifies open directions for exploring, designing, analyzing, and visualizing dynamic networks. These directions reflect the distinct challenges introduced by temporal interactions and evolving topology.
- Research Directions: A long-term research goal is to map the universe of dynamic networks using TVG tools, identifying shared features and natural differences across modeled systems.
- Research Directions: Distributed TVG algorithm design remains open, with existing work covering routing, broadcasting, exploration, self-stabilization, community resilience, and viral marketing.
- Research Directions: TVG design and optimization includes minimizing temporal diameter and balancing node eccentricities when interactions or the underlying graph can be modified.In the illustrated redesign, the diameter decreases from 24–30 days to 14–20 days.
- Research Directions: Complexity analysis in dynamic networks depends not only on static network parameters but also on the number of topological events during execution.
- Research Directions: Pattern detection and visualization research aims to expose dynamic properties and interaction patterns through tools that represent temporal and spatial node and edge attributes.