Connectivity and inference problems for temporal networks

By David Kempe, Jon M. Kleinberg, Amit Kumar. Symposium on the Theory of Computing, 2000

579 citations recorded by the source corpus.

Many network problems are based on fundamental relationships involving time. Consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread of a disease through a population, or analyzing the reachability properties of an airline timetable. In such settings, a natural model is that of a graph in which each edge is annotated with a time label specifying the time at which its endpoints "communicated." We will call such a graph a temporal network. To model the notion that information in such a network "flows" only on paths whose labels respect the ordering of time, we call a path time-respecting if the time labels on its edges are non-decreasing. The central motivation for our work is the following question: how do the basic combinatorial and algorithmic properties of graphs change when we impose this additional temporal condition? The notion of a path is intrinsic to many of the most fundamental algorithmic problems on graphs; spanning trees, connectivity, flows, and cuts are some examples. When we focus on time-respecting paths in place of arbitrary paths, many of these problems acquire a character that is different from the traditional setting, but very rich in its own right. We provide results on two types of problems for temporal networks. First, we consider connectivity problems, in which we seek disjoint time-respecting paths between pairs of nodes. The natural analogue of Menger's Theorem for node-disjoint paths fails in general for time-respecting paths; we give a non-trivial characterization of those graphs for which the theorem does hold in terms of an excluded subdivision theorem, and provide a polynomial-time algorithm for connectivity on this class of graphs. (The problem on general graphs is NP-complete.) We then define and study the class of inference problems, in which we seek to reconstruct a partially specified time labeling of a network in a manner consistent with an observed history of information flow.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/78f1c5bacc50c5a768b95a704ed950445ddd7310

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Path Problems in Temporal Graphs (2014, methodology): “Temporal paths were applied to study the connectivity of a temporal network [10], for which disjoint temporal paths between any two vertices are computed.”
BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks (2008, methodology): “We propose an efficient data forwarding mechanism over time evolving grap hs of the PSN [3], that copes with dynamical, repeated disconne ction and re-wiring.”
Temporal Networks (2011, unknown): “[87] and other authors [88] call such paths ‘‘time-respecting’’.”
Spatial gossip and resource location protocols (2001, background): “A useful model for stating and proving properties of such communication histories is that of temporal networks and strictly time-respecting paths in them, proposed in [5, 11] as a means to describe how information spreads through a network over time.”
Causality-driven slow-down and speed-up of diffusion in non-Markovian temporal networks (2013, background): “…well as inter-event time distributions have been studied extensively [1, 2, 3, 4, 5, 6, 7, 8], non-Markovian properties in the contact sequences of temporal networks have been iden-tiﬁed only recently as an independent mechanism that signiﬁcantly aﬀects dynamical processes [9, 10, 11, 12, 13, 14].”
Time-varying graphs and dynamic networks (2010, background): “g, paths and reachability [10, 46], distance [15], diameter [23], or connected components [11] – to a temporal version.”
The structure of information pathways in a social communication network (2008, background): “The notion of a graph annotated with the times at which the nodes communicated has been studied at a theoretical level [5, 6, 14, 15].”